数据结构-红黑树

便于理解的演化进程

二分查找(有序条件下 Binary Search)

–> 二叉查找树（BST）查询次数等于高度

–> 二叉平衡树，平衡因子不超1 h= L log2n 」 +1 O(log2N)

查找和二叉查找一样的 删除和插入比较复杂

二叉查找树

四种失去平衡的解决方法

LR 两步

RL 两步

不断旋转比较耗时 进一步改进：

红黑树RBT

调整的次数少 平衡性不如二叉平衡树 ，

插入删除频繁的使用红黑树，不频繁的使用二叉平衡树。

---

（这里的空节点是叶子节点，与以往太不一样）

1.结点是红色或黑色。

2.根结点是黑色。

3.每个叶子结点都是黑色的空结点（NIL结点）。

4.红属性 ：每个红色结点的两个子结点都是黑色。

5.黑属性：每一个结点到其每个叶子的所有路径都包含相同数目的黑色结点。

The height of the red-black tree is at most：
2 log2(n+ 1)

新插入的是红色

• 父红，父兄弟红 那么 父亲和父亲兄弟 变黑，爷爷变红（这个是一直向上重复的，如果爷爷是根结点不用变 ）

• 父红，父无兄弟或者父兄弟是黑 那么 先旋转（ll或者rr或者lr或者rl应该是） 后重新上色

给定下面这颗红黑树，新插入的结点是21：

显然，新结点21和它的父结点22是连续的红色结点，违背了规则4，我们应该如何调整呢？

新结点的父结点和叔叔结点都是红色。

于是我们经过三次变色，22变为黑色，25变为红色，27变为黑色：

经过上面的调整，以结点25为根的子树符合了红黑树规则，但结点25和结点17成为了连续的红色结点

于是，我们把结点25看做一个新结点，正好符合：

“新结点的父结点是红色，叔叔结点是黑色或者没有叔叔，且新结点是父结点的右孩子，父结点是祖父结点的右孩子”

于是我们以根结点13为轴进行左旋转，使得结点17成为了新的根结点：

接下来，让结点17变为黑色，结点13变为红色：

如此一来，我们的红黑树变得重新符合规则。

删除比插入更复杂

java中的BRT

JDK 7及以前版本：HashMap是数组+链表结构(即为链地址法)
JDK 8版本发布以后：HashMap是数组+链表+红黑树实现。

B树（b-树）

删除终端结点：3种情况

够借:左右兄弟结点都可以

左右兄弟不够借：从父结点搞一个下来

删除非终端结点：3种情况

交换然后删除

左右子结点加起来不超额，合并左右子结点，删除23

B+树

总结：

B+树查询与B-数据对比：

B+树的中间节点没有卫星数据，所以同样大小的磁盘可以容纳更多的节点元素；
在数据量相同的情况下，B+树的结构比B-树更加“矮胖”，因此查询的IO次数也更少；
B+树的查询必须最终查找到叶子节点，而B-树只要查找匹配的元素即可，无论匹配的元素处于中间节点还是叶子节点。
B-树的查找性能并不稳定（最好情况只查询根节点，最坏情况是查找叶子节点）。而B+树的每一次查找都是稳定的。
原文链接：https://blog.csdn.net/jiang_wang01/article/details/113739230
1
2
3
4
5

B+树比B-树的优势三个：

1. 单一节点存储更多的元素，使得查询的IO次数更少。
2. 所有查询都要查找到叶子节点，查询性能稳定。
3. 所有叶子节点形成有序链表，便于范围查询。

数据库为什么不用红黑树而用B+树？

1）B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了；

2）B+树查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；

3）B+树便于范围查询（最重要的原因，范围查找是数据库的常态）

B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低；