一开始就接触这五点，会让人云里雾里，不利于了解这个数据结构。因为这种先给定义在推导的方式并不适合学习。它没有介绍红黑树的来源，而只是给你生硬的定义。 而学习红黑树的最好学习资料就是大名鼎鼎的《算法4》，如下： Robert Sedgewick  罗伯特 塞奇威克  高德纳的学生。 Donald  Knuth  高德纳 :  算法和程序设计技术的先驱者。 2 - 3树和红黑树具有等价

AVL树和红黑树 1. 背景2. AVL树的概念3. AVL树节点的定义4. AVL树的插入5. AVL树的旋转5.1. 左单旋5.2. 右单旋5.3. 左右单旋5.4. 右左单旋5.5. 旋转总结 6. AVL树的验证7. AVL树的性能8. 红黑树的概念9. 红黑树的节点的定义10. 红黑树的插入10.1. 情况一10.2.情况二 11. 红黑树的验证12. 红黑树与AVL树的比较

一、AVL树 1.1 AVL树的概念         二叉搜索树（BST）虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不

1.红黑树并不追求“完全的平衡”，它只要求达到部分的平衡，降低了对旋转的要求，从而提高了性能。 2.红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作，由于它的设计，任何不平衡都会在三次旋转之内解决。 3.还有一些更好的，但实现起来更复杂的数据结构 能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AV