排序二叉树

龍

---

红黑树是一种二叉排序树 也成为二叉查找树也算一种非严格的平衡树

排序二叉树的性质：

• 任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值；
• 如果排序二叉树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么它的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变BST树结构

（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

和二叉树不同的是： 在二叉树的基础上增加了着色和相关的性质是的红黑树相对平衡 使得查找删除插入的最坏时间复杂度为O(log n)

下面这五条性质保证了红黑树的高度始终保持在h = log n

1. 每个节点那么为红，要么为黑。
2. 根节点为黑
3. 每个叶节点为黑/所有的叶节点都是空节点（即 null，实际上是不存在的节点），并且是黑色的
4. 如果一个节点为红的， 那么他的两个儿子节点都为黑色
5. 对于任意一个节点而言，其到叶节点的每一条路径都包括相同数量的黑节点

平衡二叉树的性质:

• 又被称为AVL树（有别于AVL算法），且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等；
• 平衡树的的插入和删除操作很可能会打破平衡， 一旦平衡被破坏这时候需要通过左旋或者右旋的使得平衡树恢复平衡
• 平衡因子BF=左子树深度－右子树深度. 平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。

---

红黑树除了具有排序二叉树特性也属于平衡二叉树，但不是严格的平衡二叉树，说它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1，但红黑树高度依然是平均log(n)，且最坏情况高度不会超过2log(n)，这有数学证明。所以它算平衡树。(坑爹啊)

graph LR
红黑树-->排序二叉树
红黑树-->平衡二叉树

平衡二叉树和红黑树 的区别

平衡二叉树是一种严格的平衡，在插入和删除结点时根据不同的情况需要执行的旋转次数比红黑树要多。 红黑树是弱平衡的，使用这个不太严格的平衡换取在插入和删除的旋转次数降低。

所以 简单来说：查找次数要是远远大于删除和插入的次数，我要毫不犹豫的选择 AVL树；如果查找次数和删除插入次数差不多的话，选择红黑树是很必要的 —