平衡二叉树

高级树的总结

参考《邓俊辉的数据结构》

AVL(Adelson-Velskii 和Landis)树

AVL(Adelson-Velskii 和Landis)树是带有平衡条件的二叉查找树, 保证树的深度为O(logN);
左右子树具有相同的高度, 高度差最多差1, 用一次或两次旋转操作维持平衡状态;
理想平衡和适度平衡的概念: 二叉搜索树的性能主要取决于高度, 固在节点数目固定的前提下, 应尽可能地降低高度;
- n个结点, 高度不可能小于O(logn), 如果树高恰好等于logn, 称为理想平衡二叉树;
- 对于二叉树的所有可能的形态, 理想的平衡二叉树所占的比例极低;
- 在渐进意义下适当放松标准之后的平衡性, 称为适度的平衡;
  - AVL树, 伸展树, 红黑树, kd-树等, 都属于适度平衡, 可归纳于平衡二叉搜索树(balanced binary search tree, BBST);
  - 伸展树主要用于计算机的局部性原理;
单纯的二叉搜索树在最坏的情况下插入查找删除等操作时间复杂度会是O(N), AVL树就能避免单链表的情况，使得增删查改的时间复杂度为O(lgN);
AVL树的几个条件:
- 左子树和右子树的高度之差的绝对值不超过1;
- 树中的每个左子树和右子树都是AVL树;
- 每个节点都有一个平衡因子(balance factor--bf),任一节点的平衡因子是-1,0,1。(每个节点的平衡因子等于右子树的高度减去左子树的高度);
为了保证AVL的性质, 需要对AVL树进行相应的操作:
- 右单旋
- 左单旋
- 左右双旋
- 右左双旋
- 具体操作过程;
AVL树的特性让二叉搜索树的节点实现平衡(balance)：节点相对均匀分布，而不是偏向某一侧;
对于AVL树，可以证明，在新增一个节点时，总可以通过一次旋转恢复AVL树的性质;
- 容易理解;

伸展树(Splay tree)

它的主要特点是不会保证树一直是平衡的，但各种操作的平摊时间复杂度是O(log n)，因而，从平摊复杂度上看，二叉查找树也是一种平衡二叉树;
相比于其他树状数据结构（如红黑树，AVL树等），伸展树的空间要求与编程复杂度要小得多;
伸展树的出发点是这样的：考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。
- 这样，很容易得想到以下这个方案：每次查找节点之后对树进行重构，把被查找的节点搬移到树根，这种自调整形式的二叉查找树就是伸展树。
- 每次对伸展树进行操作后，它均会通过旋转的方法把被访问节点旋转到树根的位置。
为了将当前被访问节点旋转到树根，我们通常将节点自底向上旋转，直至该节点成为树根为止。
- “旋转”的巧妙之处就是在不打乱数列中数据大小关系（指中序遍历结果是全序的）情况下，所有基本操作的平摊复杂度仍为O（log n）;

平衡二叉树之B树

2-3树中, 一个节点最多有2个key, 而红黑树则使用染色的方式来标识这个key;
B树(B-tree)是一种树状数据结构, 它能够存储数据, 对其进行排序并允许以O(logn)的时间复杂度允许进行查找, 顺序读取, 插入和删除的数据结构;
B树概括起来就是一个节点可以拥有多于2个子节点的二叉查找树;
与平衡二叉查找树不同, B-树为系统最有化大数据的读和写操作, B-树减少定位记录锁经历的中间过程, 从而加快存取速度, 普遍应用在数据库和文件系统中;
B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点;
- 根节点至少有两个子节点;
- 每个节点有M-1个key，并且以升序排列;
- 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间;
- 其它节点至少有M/2个子节点;

B+树

B+树是对B树的一种变形树，它与B树的差异在于：
- 有k个子结点的结点必然有k个关键码;
- 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中;
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录;
B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历;
B+ 树的优点在于:
- 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key;
- 数据存放的更加紧密，具有更好的空间局部性;
- 因此访问叶子节点上关联的数据也具有更好的缓存命中率;
- B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可;
- 由于数据顺序排列并且相连，所以便于区间查找和搜索;
- B树则需要进行每一层的递归遍历, 相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好;
B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近, 访问也更迅速;

B-树

B-树用于多路平衡查找, 多路搜索树, 根据磁盘的存储特性决定, 即读取连续的几千个字节和读取几个字节的速度是一样的 ;
所谓B-树, 即m路平衡搜索树, 每个节点不超过m-1个关键码;
B-树也就是一般概念的B树;

红黑树

红黑树原理详细介绍;
清晰的讲解;
红黑树的特性:
- 每个节点是黑色或者是红色;
- 根节点是黑色;
- 每个叶子节点(NIL)是黑色(这里的叶子节点是指为空(NIL或NULL)的叶子节点);
- 如果一个叶子节点是红色的, 则它的子节点必须是黑色的;
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点;

有了AVL树为什么还要用红黑树?

实现比较;
红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能;
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高;
AVL树是最先发明的自平衡二叉查找树;
红黑树与AVL树;
红黑树比AVL树的优势;
- 红黑树的任何不平衡都会在三次旋转之内解决;
- 在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度;
红黑树删除和插入的时间复杂度都是O(1);
AVL的平衡条件可能更容易被破坏掉, 但AVL树的search(搜索)效率更高;
RB-tree总体的统计性能比AVL树高;
红黑树的查询性能略微逊色于AVL树，因为他比avl树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较，但是，红黑树在插入和删除上完爆avl树，avl树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于avl树为了维持平衡的开销要小得多;