数据结构之红黑树

原创
2020/07/11 17:15
阅读数 36

概念:

红黑树是一种平衡二叉树,与AVL数相似,都是在插入或者删除时通过特定的操作来保证二叉查找树的平衡,从而获得较高的查找性能。

红黑树与AVL树的区别在于它使用颜色来标识节点的高度。它追求的是局部的平衡而不是AVL树中非常严格的平衡。

红黑树是变态级数据结构。

性质:

红黑树首先是一棵二叉查找树,它的每个节点都被标上了颜色。

  1. 每个节点的颜色只能是红色或黑色。
  2. 根节点是黑色的。
  3. 每个叶子节点都带有两个空的黑色节点(黑哨兵),如果一个节点n只有一个左孩子,那么n的右孩子是一个黑哨兵。如果节点n只有一个右孩子,那么节点n的左孩子是一个黑哨兵。
  4. 如果一个节点是红的,那么他的两个孩子都是黑的。也就是说在一条路径上不能出现两个相邻的红色节点。
  5. 对于每个节点来说,从该节点到其子孙叶节点的所有路径上包含相同数目的黑节点。、

旋转变色规则:

当前节点的父节点是红色,且其祖父节点的另一个子节点也是红色,祖父节点不是根节点。
  1. 将父节点和叔叔节点设为黑色。
  2. 将祖父节点设为红色。
  3. 将祖父节点设为新的当前节点。
当前节点是红色,叔叔节点也是红色,且当前节点在最边上,祖父节点是根节点。
  1. 将根节点作为新的当前节点,以根节点为支点进行左旋(右孩子)或者右旋(左孩子)。
  2. 旋转后将新的根节点变黑色,其他节点根据需要变色,只要保证不出先红红连续节点即可。
  3. 判断性质5是否已满足,不满足以当前节点为支点进行一次左旋或者右旋,旋转后依旧要保证不出现红红连续节点,否则进行变色。
其他所有情况,前提是当前节点的父节点是红色。
  1. 将父节点作为新的当前节点。
  2. 以新的当前节点为支点进行左旋(右孩子)或者右旋(左孩子)。

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部