| layout | title | gh-repo | gh-badge | tags | |||||
|---|---|---|---|---|---|---|---|---|---|
post |
浅谈红黑树 |
youcoding98/youcoding98.github.io |
|
|
本文主要谈一下自己的红黑树的认识，有些浅显。对于红黑树有的知识内容如删除、修复等还有待加深
二叉查找树(Binary Search Tree)是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。
T key = a search key
Node root = point to the root of a BST
while(true){
if(root==null){
break;
}
if(root.value.equals(key)){
return root;
}
else if(key.compareTo(root.value)<0){
root = root.left;
}
else{
root = root.right;
}
}
return null;
数在插入的时候会导致树倾斜，不同的插入顺序会导致树的高度不一样，而树的高度直接的影响了树的查找效率。理想的高度是logN，最坏的情况是所有的节点都在一条斜线上，这样的树的高度为N。
基于BST存在的问题，一种新的树——平衡二叉查找树(Balanced BST)产生了。平衡树在插入和删除的时候，会通过旋转操作将高度保持在logN。其中两款具有代表性的平衡树分别为AVL树和红黑树。
-
AVL树是严格的平衡二叉树，平衡条件必须满足左右子树高度差的绝对值不超过1.只要不满足该条件，就要通过旋转来保持平衡。
红黑树不追求“完全平衡”，它只要求部分达到平衡，引入了颜色的概念，通过颜色这个约束条件的使用来保持树的高度平衡；任何不平衡都会在三次旋转之内解决。 -
对于查找来说，AVL树要比红黑树更平衡，查找效率会更高一些。
对于插入来说，AVL树和红黑树都是最多两次树旋转来实现复衡，旋转的量级为O(1),而AVL树每次插入都要更新从根节点到被修改节点这条路径上的平衡因子，最差情况需要O(N), 而红黑树只有在极端条件下才会修改整条路径，所以红黑树的插入操作要比AVL树要好。
对于删除来说，AVL树需要维护从被删节点到根节点这条路径上所有节点的平衡，旋转的量级为O(N)，而红黑树最多需要旋转3次实现复衡，旋转量级为O(1)，效率更高。 -
红黑树是功能、性能、空间开销折中的结果；红黑树的复衡效率更高，维护强于AVL树，读取略逊于AVL树。
- 任何一个节点都有颜色，黑色或者红色。
- 根节点是黑色的。
- 父子节点之间不能出现两个连续的红节点。
- 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等。
- 空节点被认为是黑色的。
红黑树在插入、删除操作时会维持树的平衡，保证树的高度在
[logN,logN+1]
整个红黑树的查找，插入和删除都是O(logN)的，原因就是整个红黑树的高度是logN，查找从根到叶，走过的路径是树的高度，删除和插入操作是从叶到根的，所以经过的路径都是logN。
旋转操作(Rotate)的目的是使节点颜色符合定义，让RBTree的高度达到平衡。
Rotate分为left-rotate（左旋）和right-rotate（右旋），区分左旋和右旋的方法是：待旋转的节点从左边上升到父节点就是右旋，待旋转的节点从右边上升到父节点就是左旋。
红黑树的查找和二分查找树的查找操作是一致的。
插入与BST的插入方式是一致的，只不过是在插入过后，可能会导致树的不平衡，这时就需要对树进行旋转操作和颜色修复。
只有在父节点为红色节点的时候是需要插入修复操作的。
插入修复操作分为以下的三种情况，而且新插入的节点的父节点都是红色的：
- 叔叔节点也为红色：将（父节点和叔叔节点）与祖父节点的颜色互换
- 叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上：将父节点进行右旋操作，并且和祖父节点互换颜色。
- 叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上：将子节点进行左旋操作，变成case2情况操作。
如果是叶子节点就直接删除，如果是非叶子节点，会用对应的中序遍历的后继节点来顶替要删除节点的位置。删除后就需要做删除修复操作，使的树符合红黑树的定义。
删除修复操作在遇到被删除的节点是红色节点或者到达root节点时，修复操作完毕。
删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。
需要从兄弟节点借调黑色节点使树保持局部的平衡，如果局部的平衡达到了，就看整体的树是否是平衡的，如果不平衡就接着向上追溯调整。
B+树是为了磁盘或者其他存储设备而设计的一种多路平衡查找树。
B+树的高度一般控制在3~5层，主要是为了避免磁盘的读取次数过多，非叶子节点不存数据，数据都在叶子结点保存。并且叶子结点间通过一个指针连接。
二叉查找树/红黑树的结构不适合数据库，因为它的查找效率与层数有关，越处在下层的数据，就需要越多次的比较。对于数据库来说，每进入一层，就要从硬盘中读取
一次数据，这会造成磁盘I/O读写过于频繁，效率低效。而根据空间局部性原理，需要的数据它周边的数据也可能读取到，因此使用B+树更好。