红黑树
bst（binary search tree）：二叉搜索树，左子树节点的值小于根节点的值，右子树节点的值大于根节点的值。
查找时类似二分查找的思想，查找所需的最大次数等于二叉查找树的高度。一些情况下，会退化成链表。
avl树：二叉平衡搜索树，二叉搜索树，且左右子树的高度差不超过1。
为什么要有红黑树
AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。
STL中map和set，因为key是有序，所以底层实现用红黑树，红黑树形式存储的键值是有序的。同时红黑树可以在O(log n)时间内做插入，查找和删除。
什么是红黑树
红黑树（Red Black Tree） 是一种近似平衡二叉查找树，在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
红黑树特点
- 节点是红色或者黑色
- 根节点是黑色
- 每个叶子节点都是黑色的空节点（NULL节点）
- 每个红色节点的两个子节点都是黑色（从根到每个叶子节点的所有路径上不能有两个连续的红色节点）
- 从任一节点到每个叶子节点的路径都包含相同数目的黑色节点
这些约束强制了红黑树的关键性质: 红黑树从根到叶子的最长路径不会超过最短路径的两倍，所以红黑树只是近似的平衡二叉树，牺牲了些许平衡性换来的是增删操作的简单性。
平衡多路查找树，B树
B树的各种操作能使B树保持较低的高度，从而有效避免磁盘过于频繁的查找存取操作，达到有效提高查找效率的目的。
网友评论