红黑树详解_高度最高的孩子结点

在记录红黑树结构之前，先了解一下平衡二叉树

满二叉树

满二叉树：除了叶子结点外其他节点均有左右孩子节点

avl树对中平衡二叉树的要求

avl中的二叉树，对于任意一个节点，其左子树和右子树的高度差不能超过一

堆中的完全二叉树

完全二叉树：将节点按照从左到右一层一层的结构全部铺开即为满二叉树，完全二叉树的空缺部分一定在二叉树的右下部分，且整个树的叶子节点，最大深度值和最下深度值相差不超过一

 

平衡二叉树的定义

平衡二叉树：对于任意一个节点，其左子树和右子树的高度差不能超过一，可以通过平衡因子（平衡因子：即当前节点的左右孩子节点的高度差）来判断该二叉树是否为平衡二叉树（当前节点的高度计算：左右孩子节点中高度高的一方的高度+1即为当前节点高度）

 

平衡二叉树的定义

红黑树定义

红黑树也是二分搜索树，同时是平衡二叉树

红黑树定义

 

在说红黑树前，先来了解一下2-3树

 

2-3树

 

2-3树满足二分搜索树的性质（对于2节点来说，左节点小于当前节点，右节点大于当前节点，而对于3节点来说，左节点小于当前节点所有的值，中节点的值介于当前节点中的两个节点值之间，右节点大于当前节点所有的值），但不是二叉树

2-3树是绝对平衡的二叉树（从根节点到任意叶子节点所经过的节点数一定是相同的）这其中涉及到节点融合，在此不做详述

 

那么2-3树是如何和红黑树等价的呢？

对于2节点来说，没什么区别，但是对于三节点来说，在红黑树中我们将b单独作为一个节点，作为c的子节点，并且b节点中保存有它和c节点在2-3树中的关系

 

2-3树转化成红黑树

 

红黑树是一个保持黑平衡的二叉树

• 红黑树添加节点左旋转

   

  

  旋转前

   

  

  旋转后

   

  

  左旋转代码

• 红黑树添加节点-颜色翻转

  

  颜色翻转

  
  因中间节点仍需向上融合，所以给它赋值成红色

  

  代码实现

• 红黑树添加节点-右旋转

   

  

  旋转前

   

  

  旋转后

   

  

  旋转后进行颜色翻转

   

  

  翻转后

   

  

  代码

• 红黑树添加节点-另一种情况

   

  

  添加的节点值大小介于三节点的两个值之间

   

  

  复用之前定义的子过程，先对37-40进行左旋转，然后对40-42进行右旋转，最后整理做颜色翻转

• 性能总结

  

  性能总结

  
  红黑树在维持树平衡上的开销小于avl树，avl在添加或删除数据时，为了保持其本身的平衡二叉树的特性，需要不停地做左旋转或者右旋转操作；至于普通的二分搜索树，当数据的随机性较高时，它的添加性能很好，但是当添加的数据高度有序时，那么他就完了

左倾红黑树是较为常见的红黑树实现方式

左倾红黑树

另一种统计性能优秀的树结构

伸展树

小结：这里记录的只是红黑树等价于2-3树，并且按照左倾的原则进行的实现，实际上红黑树还可以等价于2-4树进行实现，不管是哪种实现方式，只要最后的树结构满足红黑树的五个特性，那么我们就可以称它为红黑树