2019-06-02

 二叉树和红黑二叉树


二叉树的定义

二叉树是树形结构的一个重要类型。 许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。

二叉速树的特点:

1)树是由一个集合以及在该集合上定义的一种关系构成的。

集合中的元素称为树的结点,所定义的关系称为父子关系。

2) 父子关系在树的结点之间建立了一个层次结构。

3) 树的结点包含一个数据元素及若干指向其子树的若干分

支。

4) 在这种层次结构中有一个结点具有特殊的地位,这个结点

称为该树的根结点,或简称为树根。

平衡二叉树

在平衡二叉树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。 增加和删除节点可能需要通过一次或多次树旋转来重新平衡这个树。


 平衡二叉树示意图

 红黑二叉树

红黑二叉树(简称:红黑树),它首先是一棵二叉树,同时也是一棵自平衡的排序二叉树。

      红黑树在原有的排序二叉树增加了如下几个要求:

      1. 每个节点要么是红色,要么是黑色。

      2. 根节点永远是黑色的。

      3. 所有的叶节点都是空节点(即 null),并且是黑色的。

      4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点)

      5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

      这些约束强化了红黑树的关键性质:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。这样就让树大致上是平衡的。

      红黑树是一个更高效的检索二叉树,JDK 提供的集合类 TreeMap、TreeSet 本身就是一个红黑树的实现。


红黑树示意图

TreeMap的使用和底层实现

TreeMap和HashMap实现了同样的接口Map,因此,用法对于调用者来说没有区别。HashMap效率高于TreeMap;在需要排序的Map时才选用TreeMap。

HashSet

其特点为:是无序、不可重复

HashSet与HashMap的关系?

 HashSet是采用哈希算法实现,底层实际是用HashMap实现的(HashSet本质就是一个简化版的HashMap),因此,查询效率和增删效率都比较高。


TreeSet的底层数据结构是:红黑树,通过内部比较器和外部比较器去掉重复元素。


Hashset自定义对象时,必须重写hashcode()方法和equals()方法,以下为课堂代码




TreeSet的使用和底层实现

TreeSet底层实际是用TreeMap实现的,内部维持了一个简化版的TreeMap,通过key来存储Set的元素。 TreeSet内部需要对存储的元素进行排序,因此,我们对应的类需要实现Comparable接口。这样,才能根据compareTo()方法比较对象之间的大小,才能进行内部排序。

TreeSet的使用

运行结果为:



遍历集合的方法总结


遍历List方法一:普通for循环 

 


遍历List方法二:增强for循环(使用泛型!)


遍历List方法三:使用Iterator迭代器(1)


遍历List方法四:使用Iterator迭代器(2)


遍历Set方法一:增强for循环


遍历Set方法二:使用Iterator迭代器


遍历Map方法一:根据key获取value


遍历Map方法二:使用entrySet


集合体系框架总结表如下:

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一、基本数据类型 注释 单行注释:// 区域注释:/* */ 文档注释:/** */ 数值 对于byte类型而言...
    龙猫小爷阅读 4,291评论 0 16
  • Java集合类可用于存储数量不等的对象,并可以实现常用的数据结构如栈,队列等,Java集合还可以用于保存具有映射关...
    小徐andorid阅读 1,976评论 0 13
  • hashmap实现的数据结构,数组、桶等。 如图所示 JDK 1.7,是以数组+链表组成的,链表为相同hash的键...
    不需要任何阅读 850评论 0 1
  • 写在前面 当在10亿数据进行不到30次比较就能查找到目标时,不禁感叹编程之魅力!人类之伟大呀! —— 学红黑树有感...
    安卓大叔阅读 660,524评论 262 1,258
  • 终于出院。这酸爽…… 今夜风大雨急。笑妹说,妈妈,我给你讲个秘密:你是美女,我爸是帅哥!这是秘密,...
    晴子__阅读 355评论 5 4