前言

一.红黑树(RBT)的作用

本文介绍了红黑树(RBT)的基本概念与应用。红黑树作为二叉排序树的改进，通过颜色约束保持近似平衡，相比AVL树大幅降低了插入删除时的调整开销。文章详细阐述了红黑树的五大特性（根黑、叶黑、不红红、黑路同），并通过实例演示了特性验证方法。此外，讲解了黑高计算、路径长度性质等核心概念，以及红黑树与平衡二叉树的适用场景对比。最后指出红黑树在查找操作上与普通BST、AVL树相同，时间复杂度为O(logn)。该文为理解红黑树的核心特性与应用场景提供了系统性的介绍。

1.红黑树的优势

• 平衡二叉树AVL：插入/删除很容易破坏“平衡”特性，需要频繁调整树的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大）,再进行LL/RR/LR/RL调整
• 红黑树RBT：插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成

二.平衡二叉树与红黑树的比较

• 平衡二叉树：适用于以查为主、很少插入/删除的场景
• 红黑树：适用于频繁插入、删除的场景，实用性更强

二.红黑树大概会怎么考？

• 红黑树的定义、性质——选择题
  例:4.现有一棵无重复关键字的平衡二叉树(AVL树)，对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是_。
  A.根结点的度一定为2
  B.树中最小元素一定是叶结点
  C.最后插入的元素一定是叶结点
  D.树中最大元素一定是无左子树
• 红黑树的插入/删除——要能手绘插入过程（不太可能考代码，略复杂），删除操作也比较麻烦，也许不考
  例:3.若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是_。
  A.0 B.1 C.2 D.3

三.红黑树的定义

1.定义内容

• 红黑树是二叉排序树,左子树结点值≤根结点值≤右子树结点值
• 在二叉排序树的基础上,增加了以下要求:
  ①每个结点或是红色，或是黑色的
  ②根节点是黑色的
  ③叶结点（外部结点、NULL结点、失败结点）均是黑色的
  ④不存在两个相邻(邻接)的红结点（即红结点的父节点和孩子结点均是黑色）
  ⑤对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

口诀:左根右,根叶黑,不红红,黑路同

2.代码实现

struct RBnode {	//红果树的结点定义
	int key;	//关键字的值
	RBnode* parent;	//父节点指针
	RBnode* lChild;	//左孩子指针
	RBnode* rChild;	//右孩子指针
	int color;	//结点颜色，如：可用0/1表示黑/红，也可使用枚举enum表示颜色
}；

3.实例

四.练习

• 下面的树是否符合红黑树要求？
  

  • 不满足不红红这个特性,出现了邻接的红结点

• 下面的树是否符合红黑树要求？
  

  • 根叶黑这个特性,根节点不是黑结点

• 下面的树是否符合红黑树要求？
  

  • 不满足黑路通这个特性,每个节点所经过的黑结点个数不同

• 下面的树是否符合红黑树要求？
  

  • 不满足左根右的特性,即不是二叉排序树

五.补充概念：结点的“黑高”

1.定义

• 结点的黑高bh——从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数
• 如上图的15的黑高为2

六.红黑树的性质

• 性质1:从根节点到叶结点的最长路径不大于最短路径的2倍

由"不红红"和"黑路同"可知:从根节点出发,到达任意一个叶节点所经过的黑节点数量都是相同的,假设都是n.那么由于红结点不能连续出现,所以穿插到黑结点之间得到最长路径2n-1,当路径上全是黑结点时路径为最短路径n,其两倍也就是2n,最长路径2n-1<2n,得证

• 性质2:有n个内部节点的红黑树高度$h\le 2{\log }_2(n+1)$
  红黑树查找操作时间复杂度=$O(lo{g}_{2}n)$

七.红黑树的查找

• 与BST、AVL 相同，从根出发，左小右大，若查找到一个空叶节点，则查找失败

结语

一更😉

如果想查看更多章节,请点击:一、数据结构专栏导航页