易懂"/>
红黑树 完整原理解析（搜索、插入、删除、黑三角处理），通俗易懂
目录
- 前言
- 树的基础概念
- 结点
- 树
- 平衡二叉树（AVL树）
- 定义（规则）
- 性质
- 红黑树
- 定义（规则）
- 结点术语
- 检索
- 基础操作
- 变色
- 旋转
- 插入元素
- 删除元素
- 位置转移
- 向下删除
- 向上删除
- 可视化工具
- 参考文章
前言
最近做游戏开发，遇到了一个有大量数据存取需要的情况，得用一个容器来装。
首先考虑常用的动态数组，但发现有频繁插入与删除操作，又要维持顺序，显然不合适。
转而考虑链表，又发现有随机存取的需求，所以也不合适。
于是考虑使用一种更加折中，读取，插入，删除速度都还不错的容器 “二叉树”，
这里选择红黑树，其他种类二叉树不考虑使用也不在讨论范围。
由于此前并没有过多的了解过二叉树所以趁此机会顺便学习一下，因为网上难以找到完整的红黑树原理文章，所以特此亲自来写，欢迎指正错误~
这篇文章适合那些想完全没有二叉树基础，并且想自己实现或了解红黑树的人
顺便红黑树长这样：
树的基础概念
-
结点
结点是树的基本构成单位，也是单个数据的基本容器，下图是一个结点，用字母N表示
-
每一个结点向下指向0或多个子节点，下图中N结点有两个子节点，用字母C表示
-
每一个结点向上指向可能存在的唯一父节点，下图中N有一个父节点，用字母P表示
-
如果一个结点不存在父节点，那么这是一个根节点，下图中Root是根节点
-
如果一个结点不存在子结点，那么它是
叶子结点，否则它是分支结点，下图中红框框是叶子，其他是分支
-
一个结点的子节点数量称为度数
-
树
树是多个结点的集合，结点的个数 n > = 0 n>=0 n>=0，下图中是多个结点的集合
T r e e R o o t = [ R o o t , N , B , C 1 , C 2 , C 4 , C 5 , g 1 , g 2 , g 3 , g 4 , g 5 , g 6 , g 7 , g 8 ] Tree_{Root} = [Root, N, B, C1, C2, C4, C5, g1, g2, g3, g4, g5, g6, g7, g8] TreeRoot=[Root,N,B,C1,C2,C4,C5,g1,g2,g3,g4,g5,g6,g7,g8]
任何一个结点与它的所有子结点构成了另一颗完整的树，被称为子树，下图中 N N N及其所有子节点构成了 R o o t Root Root的左子树 T r e e N = [ N , C 1 , C 2 , g 1 , g 2 , g 3 , g 4 ] Tree_N = [N, C1, C2, g1, g2, g3, g4] TreeN=[N,C1,C2,g1,g2,g3,g4]，这也意味着 T r e e R o o t ⊃ T r e e N Tree_{Root} \supset Tree_N TreeRoot⊃TreeN（ T r e e N Tree_N TreeN是 T r e e R o o t Tree_{Root} TreeRoot的子集)
- 按照层次划分，一棵树从上至下层数逐一增加，值从0开始
平衡二叉树（AVL树）
平衡二叉树，又称AVL树，解决了二叉排序树高度不确定从而导致访问时间复杂度不稳定的情况，如果二叉排序树的子树间的高度相差太大，就会让二叉排序树操作的时间复杂度t提升，最坏的情况为O(n)，为了避免这种情况，平衡二叉树被发明，使树的任意结点左右子树高度差最小化，其本质还是一棵二叉搜索树。
-
定义（规则）
-
每个结点最多有两个子结点（子树），如果都存在则分别为左子结点（子树）和右子结点（子树） -
除根节点外，每个结点必须区分左右 -
对于任意节点N，N的左子树任意结点值 < N结点值 < N的右子树任意结点值，等值的结点必须划分到大于或小于分支中 -
任意结点的左右子树高度差的绝对值<=1 -
下图是一个正常的平衡二叉树
-
-
性质
- 第 i i i 层上最多有 2 i 2^i 2i 个结点
- 一颗层数为 l l l 的树最多有 2 l + 1 − 1 2^{l+1}-1 2l+1−1个结点
- 0度结点（叶子结点）的个数为 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1
- 如果一棵树的结点个数为 n n n，则树的最大层数为 l = ⌊ l o g 2 ( n ) ⌋ l=\lfloor log_2(n) \rfloor l=⌊log2(n)⌋
红黑树
红黑树，另一种自平衡树，是在1972年由Rudolf Bayer发明，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树是一种并没有那么平衡的平衡二叉树，但又是一个相对平衡的二叉树，插入，删除，查找性能都不错。
与AVL树相比，相同元素的情况下，AVL树的查找性能稍微好点，假设 n n n是结点个数，最坏情况下时间复杂度能维持在 O ( l o g 2 ( n ) ) O(log_2(n)) O(log2(n))以内，但红黑树由于不那么平衡，它的遍历深度会比AVL树最多多1层。好在它的时间复杂度能维持在 O ( l o g 2 ( n ) 2 ) O(\frac{log_2(n)}{2}) O(2log2(n))到 O ( l o g 2 ( n ) ) O(log_2(n)) O(log2(n))之间，也就是说在这种不稳定的情况下，有一半的机会速度比AVL树更快
红黑树的插入与删除由于少了一些旋转次数，所以插入与删除性能比AVL树好
-
定义（规则）
红黑树除了要满足普通二叉树的规则外，还有五条自己的规则，对树做任何操作都必须维持这些规则：结点是红色或黑色根结点是黑色nil节点都是黑色（ n i l nil nil结点也叫外部结点，也就是无值或非任何数值的结点，所有叶子结点用 n i l nil nil结点填充其左右子节点，空树用 n i l l nill nill替代根节点）我这篇文章对 n i l nil nil结点的定义与其他文章略微不同，但目标都一样红色结点的父结点和子结点都是黑色，换言之就是同一路径上不能连续出现两个红色结点从任意结点到它的任意叶子结点的所有路径上，黑结点数目相同，如下图：
这是一颗正常的满红黑树，它满足上述所有规则
====================================================
-
结点术语
为了清晰的描述元素的插入和删除操作，我们需要一些术语来描述结点间的关系，假设以第一人称代入结点 N N N，那么：- N N N：自己
- C L CL CL：左孩子（孩子的孩子就是左孙右孙）
- C R CR CR：右孩子
- P P P：父
- B B B：兄
- n e p L nepL nepL：左侄（远侄，离自己较远的那一个）
- n e p R nepR nepR：右侄（近侄，离自己较近的那一个）
- G P GP GP：爷
- U U U：叔
- c o u L couL couL：左表兄（近表兄，离自己较近的那一个）
- c o u R couR couR：右表兄（远表兄，离自己较远的那一个）
- c n L L cnLL cnLL：左-左表侄（左表兄的左孩子）
- c n L R cnLR cnLR：左-右表侄（左表兄的右孩子）
- c n R L cnRL cnRL：右-左表侄（右表兄的左孩子）
- c n R R cnRR cnRR：右-右表侄（右表兄的右孩子）
- 类似的其他称呼还有左内孙，左外孙，右内孙，右外孙等，在后续的文章中将提到
====================================================
-
检索
学习插入与删除操作前必须学会如何查找，当我们知道如何查找后才能进行准确的定位。
给定一个数值 a a a，我们按照如下过程进行搜索- 从根节点开始
- 拿 a a a与该结点比较
- a > a > a> 结点值，进入右子结点（若结点存在），回到2重复过程
- a < a< a< 结点值，进入左子结点（若结点存在），回到2重复过程
- a = = a== a==结点值，我们找到了要找的结点
- 检索结束
例：如下图，我们要搜索
1100，只需要进行一系列结点值的大小比较就能找到，从根节点开始1100 > 1000，进入右子结点1100 < 1500，进入左子结点1100 > 1050，进入右子结点1100 < 1250，进入左子结点1100 == 1100，我们找到了1100所在的准确位置~
如果我们不进行逻辑判等，检索最终会遇到 n i l nil nil 结点，插入和删除操作基于此方法
====================================================
-
基础操作
红黑树的插入与删除需要用到两种操作来维持规则，旋转与变色-
变色
维持树平衡的有效手段之一，对结点当前颜色进行
反转-
变黑：把红结点变黑结点，所在的所有路径黑结点数量 +1
-
变红：把黑结点变红结点，所在的所有路径黑结点数量 -1
-
-
旋转
其目的同样是增加或减少路径上黑结点数量，以满足规则，事实上你可以仅凭下图而不需要文字就能窥探旋转细节
-
左旋：以结点 N N N为基础，右孩子（ C R CR CR）跑到自己（ N N N）这，而自己跑到左孩子（ C L CL CL）的位置同时继承右内孙（ g d R L gdRL gdRL）
-
右旋：以结点 N N N为基础，左孩子（ C L CL CL）跑到自己（ N N N）这，而自己跑到右孩子（ C R CR CR）的位置同时继承左内孙（ g d L R gdLR gdLR）
-
-
====================================================
-
插入元素
假设即将插入的结点为 I I I，我们可以按照如下步骤完成结点的插入操作
(检索方法在文章上面，如果不明白可倒回去看)- 新插入结点是红色
- 在树中检索 I I I的值，直到遇到 n i l nil nil 结点，用 I I I 替换 n i l nil nil 结点
- 插入结点 I I I后引发三种情况
-
情况1： I I I没有父结点，现在 I I I是根节点，直接变黑，插入结束~
-
情况2： I I I有一个黑父（ P P P），没破坏任何规则，插入结束~
-
情况3： I I I有一个红父（ P P P），我们只需以叔（ U U U）的颜色区分情况调整（如果图是翻转的，那么反方向旋转即可）
此时规则4被破坏，连续出现俩红结点，需要调整树以满足规则。爷（ G P GP GP）不用看，必黑黑叔（ U U U）：-
I I I与父（ P P P）在同一侧：父（ P P P）、爷（ G P GP GP）变色，基于爷（ G P GP GP）右旋，
插入结束~
-
I I I与父（ P P P）不在同一侧： I I I、爷（ G P GP GP）变色，基于父（ P P P）左旋，基于爷（ G P GP GP）右旋，
插入结束~
-
红叔（ U U U）：无需旋转，父（ P P P）、叔（ U U U）、爷（ G P GP GP）全部变色
然后重点来了！！！现在我们把爷（GP）结点当作刚插入的结点往上看，回到步骤3再来一遍，这个过程在遇到根的时候总会结束。
-
- 如果到这里，整个插入的过程就结束了，相比之下，插入比删除操作简单很多，而且过程也比较少，很容易掌握
====================================================
-
删除元素
删除元素是红黑树中比较难的部分了，网上有很多文章都没有讲清楚，模棱两可，特别是黑三角的情况，下面的文章会基于图片进行描述，如果实际情况与图片是翻转的，那么旋转方向反过来即可-
位置转移
把要删除的结点转移到叶子结点附近，假设要删除的结点为 R R R，找到结点R R R左子树中的最大值结点
（我们无法直接从树的分支删除结点，那必然会产生额外的结点无处安放，当然，你也可以找右子树中最小的，其思路都一样）-
先进入 R R R的左子结点，然后不断进入右子结点
-
第一步的过程无法再继续时停下，假设我们悬停的结点为 r e p rep rep
-
将 R R R结点与 r e p rep rep结点位置互换，此时我们再考虑 R R R结点的删除操作即可
-
如果结点 R R R没有左子树或者是叶子结点，直接进入删除操作
位置转移之后，我们就将所有的删除情况统一转化成了以下两种，接下来逐一分析删除方案
-
-
向下删除
仅利用父结点（待删除结点的父）以下的结点就能完成删除的方法
情况1：当待删除结点 R R R只有一个子结点时，必然是红色。假设 R R R有一个左子（ C L CL CL）结点，只需以下三步即可完成删除（如果是右子结点，方法一样）
-
互换 R R R与 C L CL CL的位置（程序实现时只需 C L CL CL的值覆盖 R R R即可）
-
C L CL CL结点变黑（维持路径上的黑结点数量）
-
删除 R R R结点，
完成~
情况2：当待删除结点 R R R没有任何子结点时，我们以 R R R的颜色来区分情况R结点是红色：红色的叶子结点直接删除即可，所在路径黑结点既不会多也不会少，完成~
R结点是黑色：此时再以 R R R的父（ P P P）结点的颜色分别处理-
红父：以 R R R结点是否存在近侄（下图中是 n e p L nepL nepL）结点来区分情况-
无近侄：基于父（ P P P）结点左旋，删除 R R R，完成~
-
有近侄：父（ P P P）结点变色，然后基于兄弟（ B B B）右旋，再基于父（ P P P）左旋，删除 R R R，完成~
-
-
黑父：以兄弟（ B B B）结点的颜色区分进行处理-
红兄：以兄弟的孙子结点为依据，再次分成以下三种情况-
兄弟（ B B B）结点有一个左内孙（ n g d R ngdR ngdR），操作如下，随后删除
结束~（白色节点表示有没有无所谓）
-
兄弟（ B B B）结点有一个左外孙（ n g d L ngdL ngdL）但没有左内孙（ n g d R ngdR ngdR），操作如下，随后删除
结束~
-
兄弟（ B B B）结点没有孙子结点，操作如下，随后删除
结束~
-
-
黑兄：以侄子的情况来区分-
R R R有一个远侄：下图中远侄是（ n e p R nepR nepR），操作如图，然后删除
结束~
-
R R R有一个近侄，没有远侄：下图中近侄是（ n e p L nepL nepL），操作如图，然后删除
结束~
-
R R R没有侄子结点：此时已经形成了一个黑色三角，必须通过另一种方法
向上删除才能完成删除
-
-
-
-
-
向上删除
- 将待删除结点暂时命名为 N N N
- 现在以第一人称视角代入结点 N N N来调整树
- 以 N N N的父（ P P P）结点颜色来区分情况进行处理
-
黑父：此时 N N N的兄（ B B B）可能为红可能为黑，再以兄（ B B B）的颜色再区分情况-
黑兄：再按照如下三种情况处理
-
N N N有两个黑色侄子结点（这里就是第一次调整时必达的步骤），兄（ B B B）变红，
把父（ P P P）结点暂时命名为N N N，回到步骤2再来一次
-
N N N的远侄（ n e p R nepR nepR）是红色，如下操作，移除待删除结点，
结束~
-
N N N的近侄（ n e p L nepL nepL）是红色，远侄（ n e p R nepR nepR）是黑色，如下操作，移除待删除结点，
结束~
-
-
红兄：如下操作，
回到步骤2再来一次（还是刚才的 N N N结点）
-
-
红父：此时兄（ B B B）结点必然是黑色，按照以下三种情况处理-
N N N有两个黑色侄子结点，如下操作，移除待删除结点，
结束~
-
N N N的远侄（ n e p R nepR nepR）是红色，如下操作，移除待删除结点，
结束~
-
N N N的近侄（ n e p L nepL nepL）是红色，远侄（ n e p R nepR nepR）是黑色，如下操作，删除待删除结点，
结束~
-
-
-
可视化工具
这是一个很不错的在线红黑树可视化工具，支持插入，删除，查找等操作并且还可以逐过程操作，非常适合用来学习
.html
参考文章
红黑树详解
深入理解数据结构之树
红黑树与平衡二叉树（AVL数）区别
红黑树删除操作
.html
.html#sc=1016
平衡二叉树
更多推荐
红黑树 完整原理解析（搜索、插入、删除、黑三角处理）,通俗易懂
发布评论