java 集合Map-树及红黑树_map 红黑树

Map预备知识–树及红黑树

树（Tree）

树跟数组、链表、堆栈一样，是一种数据结构。它由有限个节点，组成具有层次关系的集合。因为它看起来像一棵树，所以得其名。一颗普通的树如下:

树是包含n（n为整数，大于0）个结点， n-1条边的有穷集，它有以下特点：

• 每个结点或者无子结点或者只有有限个子结点；
• 有一个特殊的结点,它没有父结点，称为根结点；
• 每一个非根节点有且只有一个父节点；
• 树里面没有环路

一些有关于树的概念：

• 结点的度：一个结点含有的子结点个数称为该结点的度；
• 树的度：一棵树中，最大结点的度称为树的度；
• 父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
• 深度：对于任意结点n,n的深度为从根到n的唯一路径长，根结点的深度为0；
• 高度：对于任意结点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；

一：二叉树

特性：
二叉树是每个节点最多有两个子节点的树。
二叉树的叶子节点有0个字节点，二叉树的根节点或者内部节点有一个或者两个字节点。

二：二叉搜索树（Binary Search Tree）

二叉搜索树， 又叫 二叉查找树，可以为空树，或者是具备如下性质：
若它的左子树不空，则左子树上的所有结点的值均小于根节点的值；
若它的右子树不空，则右子树上的所有结点的值均大于根节点的值，
它的左、右子树也分别为二叉搜索树。
理论上是二分查找，二叉搜索树的查询、插入、和删除一个节点的时间复杂度均为O(log(n))。

但是有一种极端特殊情况：

这种情况下，二叉搜索树已经退化为链表，搜索一个元素的时间复杂度也变成了O(n)，出现这种情况的原因是二叉搜索树没有自平衡的机制，所以就有了平衡二叉树。

三：平衡二叉树（AVL Tree）
平衡二叉树 全称叫做 平衡二叉搜索（排序）树，简称 AVL树。
特性：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，
左右两个子树 也都是一棵平衡二叉树。

当AVL树插入一个节点时，如果平衡因子已经大于1了，这个时候就要进行左旋、右旋使之平衡因子恢复为1。

平衡二叉树是一种概念（它有几种实现方式：AVL树、红黑树）

四：红黑树（Red-Black Tree）
红黑树是一种含有红、黑结点，并能自平衡的二叉查找树，其性质如下：

1、每个结点或是红色的，或是黑色的
2、根节点是黑色的
3、每个叶结点（NIL）是黑色的
4、如果一个节点是红色的，则它的两个儿子都是黑色的，即红色节点不能连续。
5、对于每个结点，从该结点到其叶子结点构成的所有路径上的黑结点个数相同。

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行rebalance平衡的代价较低， 其平均统计性能要强于 AVL 。

红黑树和AVL树的区别：
1、红黑树不追求"完全平衡"，即不像AVL那样要求节点的 |balFact| <= 1，它只要求部分达到平衡，但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低。
2、针对插入和删除节点导致失衡后的rebalance操作，红黑树能够提供一个比较"便宜"的解决方案–变色，降低开销，是对search，insert ，以及delete效率的折衷，总体来说，RB-Tree的统计性能高于AVL.，由于AVL高度平衡，因此AVL的Search效率更高。

故引入RB-Tree是功能、性能、空间开销的折中结果。

• AVL更平衡，结构上更加直观，时间效能针对读取而言更高；维护稍慢，空间开销较大。
• 红黑树，读取略逊于AVL，维护强于AVL，空间开销与AVL类似，内容极多时略优于AVL，维护优于AVL。

当树的结构发生改变时，红黑树的约束条件可能被破坏，需要通过调整使得查找树重新满足红黑树的约束条件。调整可以分为两类: 一类是颜色调整-变色，即改变某个节点的颜色；另一类是结构调整，集改变检索树的结构关系。结构调整过程包含两个基本操作** : 左旋(Rotate Left)，右旋(RotateRight)**。

左旋

左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

右旋
右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

总结：实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB-Tree。

五：B树（Balance tree）
B树，也叫 B tree、B-树，B树是一种平衡的多路查找树、m阶树 (m>=3)它比较适用于对外查找。它有几个概念：

• 阶数：一个节点最多有多少个孩子节点。（一般用字母m表示）

• 关键字：节点上的数值就是关键字

• 度：一个节点拥有的子节点的数量。
  

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：⌈m/2⌉ - 1 <= j <= m - 1.(⌈⌉表示向上取整)。
3、有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。
4、所有的叶子结点都位于同一层。

简单理解为：平衡多叉树为B树（每一个子节点上都是有数据的），叶子节点之间无指针相邻

六：B+树（B+ tree）

B+树是B-树的变体，也是一颗多路搜索树。一棵m阶的B+树主要有这些特点：

• 每个结点至多有m个子女;
• 非根节点关键值个数范围：[m/2]<= k <= m-1
• 相邻叶子节点是通过指针连起来的，并且是关键字大小排序的。

一颗3阶的B+树如下：

B+树和B-树的主要区别如下：

• B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
• B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
• 查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束。
• B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。

简单理解B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更矮壮，也是就说，相同的数据量，B+树数据结构，查询磁盘的次数会更少。

七：索引结构总结
B+树，B-Tree，Hash哈希，二叉树，红黑树区别：

• Hash哈希，只适合等值查询，不适合范围查询。
• 一般二叉树，可能会特殊化为一个链表，相当于全表扫描。
• 红黑树，是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘的次数就多了。
• B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更矮壮，也是就说，相同的数据量，B+树数据结构，查询磁盘的次数会更少。