红⿊树与平衡⼆叉树
红⿊树的性质
性质1.节点是红⾊或⿊⾊。
性质2.根节点是⿊⾊。
性质3.每个叶⼦节点都是⿊⾊的空节点（NIL节点）。
性质4 每个红⾊节点的两个⼦节点都是⿊⾊。(从每个叶⼦到根的所有路径上不能有两个连续的红⾊节点)
二叉树的基本性质
性质5.从任⼀节点到其每个叶⼦的所有路径都包含相同数⽬的⿊⾊节点。
这些约束强制了红⿊树的关键性质: 从根到叶⼦的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树⼤致上是平衡的。因为操作⽐如插⼊、删除和查某个值的最坏情况时间都要求与树的⾼度成⽐例，这个在⾼度上的理论上限允许红⿊树在最坏情况下都是⾼效的，⽽不同于普通的⼆叉查树。
旋转和颜⾊变化规则
1、添加的节点必须为红⾊
2、变⾊的情况：当前结点的⽗亲是红⾊，且它的叔结点也是红⾊：
  2.1 把⽗节点设置为⿊⾊
  2.2 把叔节点设置为⿊⾊
  2.3 把祖⽗节点设置为红⾊
  2.4 把当前指针定义到祖⽗节点，设为当前要操作的
3、左旋的情况：当前⽗节点是红⾊，叔节点是⿊⾊，且当前的节点是右⼦树。
  3.1 以⽗节点作为左旋。
4、右旋的情况：当前⽗节点是红⾊，叔节点是⿊⾊，且当前的节点是左⼦树。
  4.1 把⽗节点变成⿊⾊
  4.2 把祖⽗节点变为红⾊
  4.3 以祖⽗节点右旋转
平衡⼆叉树(AVL)的性质
它是⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡⼆叉树。这个⽅案很好的解决了⼆叉查树退化成链表的问题，把插⼊，查，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插⼊和删除牺牲掉O(logN)左右的时间，不过相对⼆叉查树来说，时间上稳定了很多。
区别：
1、红⿊树放弃了追求完全平衡，追求⼤致平衡，在与平衡⼆叉树的时间复杂度相差不⼤的情况下，保证每次插⼊最多只需要三次旋转就能达到平衡，实现起来也更为简单。
2、平衡⼆叉树追求绝对平衡，条件⽐较苛刻，实现起来⽐较⿇烦，每次插⼊新节点之后需要旋转的次数不能预知。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。