红黑树的作用和用途图片大全_红黑树的作用和用途图片大全大图

二叉树
　　在讨论二叉树之前，我们需要知道，什么是树（结构）？

　　树结构是一类重要的非线性数据结构。直观来看，树是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用，如在操作系统中，用树来表示文件目录的组织结构，在编译系统中，用树来表示源程序的语法结构，在数据库系统中，树结构也是信息的重要组织形式之一。

　　树 Tree

　　树（Tree）是 n（n≥0）个节点的有限集合，它或为空树（n=0）；或为非空树，对于非空树 T:有且仅有一个称之为根的节点；除根节点以外的其余节点可分为 m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

　　树结构的定义是一个递归的定义，即在树的定义中又用到树的定义，这是树的固有特性。

　　基本术语

　　节点：树中的一个独立单元。节点的度：节点拥有的子树的个数称为节点的度。树的度：树的度是树内各节点度的最大值。叶子：度为 0 的节点称为叶子或终端节点。非终端节点：度不为 0 的节点称为非终端节点或分支节点。除了根节点之外，非终端节点也称为内部节点。双亲和孩子：节点的子树的根称为该节点的孩子，相应地，该节点称为孩子的双亲。兄弟：同一个双亲的孩子之间互称兄弟。祖先：从根到该节点所经分支上的所有节点。子孙：以某节点为根的子树中的任一节点都称为该节点的子孙。层次：节点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一节点的层次等于其双亲节点的层次加一。堂兄弟：双亲在同一层的节点互为堂兄弟。树的深度：树中节点的最大层次称为树的深度或高度。有序树和无序树：如果将树中节点的各个子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。森林：是 m（m≥0）棵互不相交的树的集合。对树中每个节点而言，其子树的集合即为森林。由此，也可以用森林和树相互递归的定义来描述树。

　　二叉树 Binary Tree

　　二叉树（Binary Tree）是 n（n≥0）个节点所构成的集合，它或为空树（n=0）；或为非空树，对于非空树 T：有且仅有一个称之为根的节点；除根节点以外的其余节点分为两个互相不相交的子集 T1 和 T2，分别称为 T 的左子树和右子树，且 T1 和 T2 本身又都是二叉树。

　　维基百科对于二叉树的定义：在计算机科学中，二元树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2 的节点）的树结构。通常分支被称作"左子树"或"右子树"。二元树的分支具有左右次序，不能随意颠倒。

　　从定义中可以看出，二叉树与树一样具有递归性质，也可以说，二叉树是树的一个子集，二叉树与树的区别主要有以下两点：二叉树的每个节点至多只有两颗子树（即二叉树中不存在度大于 2 的节点）；二叉树的子树有左右之分，其次序不能任意颠倒。

　　二叉树是计算机科学中最为常用的树形数据结构。

　　二叉树的存储

　　二叉树的存储有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

　　链式存储法：每个节点有三个字段，其中一个存储数据，另外两个是指向左右节点的指针。如下图：

　　顺序存储法：将节点按照一定的顺序存储在数组中。如下图：

　　二叉树的遍历

　　如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。前序遍历：指对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。中序遍历：指对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。后序遍历：指对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

　　实际上，二叉树的前、中、后序遍历就是一个递归的过程。

　　二叉查找树 Binary Search Tree

　　二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查找树；

　　二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为 O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、多重集、关联数组等。

　　查找

　　在二叉搜索树 T 中搜索关键字 k，搜索过程如下：

　　查找过程如下：若节点为空或等于我们要查找的数据，返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

　　可以看出，从树根开始递归，最终找到节点或返回，期间遇到的节点形成了一条向下的简单路径，所以 TREE-SEARCH 的运行时间为 O(h)，其中 h 是这棵树的高度。

　　插入

　　将一个新值 z 插入二叉搜索树 T 中，执行过程如下：

　　插入的过程和查找的过程类似，需要从根节点开始，依次比较要插入的数据和节点的大小关系。

　　如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

　　与搜索一样，过程 TREE-INSERT 在一棵高度为 h 的树上的运行时间为 O(h)。

　　删除

　　从一棵二叉搜索树 T 中删除一个节点 z 的整个策略分为三种基本情况：如果 z 没有孩子节点，那么只是简单地将它删除，并修改它的父节点，用 NIL 作为孩子来替换 z。如果 z 只有一个孩子，那么将这个孩子提升到树中 z 的位置上，并修改 z 的父节点，用 z 的孩子来替换 z。如果 z 有两个孩子，那么找 z 的后继 y（一定在 z 的右子树中），并让 y 占据树中 z 的位置。z 的原来右子树部分成为 y 的新的右子树，并且 z 的左子树成为 y 的新的左子树。

　　可以看出，在删除的过程中，需要移动子树，即用另一棵子树替换一棵子树并成为其双亲的孩子节点。移动的过程如下：

　　删除的过程如下：

　　TREE-DELETE 处理过程如下：处理节点 z 没有左孩子的情况；处理节点 z 有一个左孩子没有右孩子的情况；处理剩下的两种情况，也就是 z 有两个孩子的情形； 找到 z 的后继，也就是 z 右子树的最小二叉树；如果 y 不是 z 的右孩子，用 y 的右孩子替换 y 并成为 y 的双亲的一个孩子，然后将 z 的右孩子转变为 y 的右孩子；如果 y 是 z 的右孩子，用 y 替换 z 并成为 z 的双亲的一个孩子，再用 z 的左孩子替换 y 的左孩子；

　　删除过程中，除了 TREE-MINIMUM 操作（此操作花费的时间取决于 z 的右子树的高度）外，TREE-DELETE 的每一行，包括 TRANSPLANT，都只花费常数时间，因此，在一棵高度为 h 的树上，TREE-DELETE 的运行时间为 O(h)。

　　平衡二叉树 Balance Binary Tree

　　平衡二叉树本质上是特殊的二叉搜索树（二叉排序树），它具有二叉搜索树所有的特点，此外它有自己的特别的性质，如下：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1；平衡二叉树的左右两个子树都是一棵平衡二叉树。

　　因为平衡二叉树的这些性质，解决了二叉搜索树在特殊情况下（比如，插入的数据是有序的）退化成链表，从而导致性能从 O(log n) 退化为 O(n) 的问题。

　　平衡因子

　　某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。

　　根据平衡二叉树的性质，其平衡因子只能等于 -1、0 或 1，当平衡因子不是这三个值时，就认为该节点已经失衡了，需要通过旋转来维持平衡。

　　旋转

　　旋转在几何和线性代数中是描述刚体围绕一个固定点的运动的在平面或空间中的变换。旋转不同于没有固定点的平移，和翻转变换的形体的反射。旋转和上面提及的变换是等距的，它们保留在任何两点之间的距离在变换之后不变。

　　在平衡二叉树中，旋转指在插入和删除时通过移动节点来维持平衡的操作。旋转分四种情形：左旋转右旋转左右旋转右左旋转

　　假设 x.right ≠ T.nil 且根节点的父节点为 T.nil，左旋转的伪代码如下：

　　可以看出，左旋转的时间复杂度为 O(1)。在旋转操作中只有指针改变，其他所有属性都保持不变。

　　平衡二叉树的优缺点

　　优点：通过严格的平衡性保证，其搜索性能在最差的情况下的也得达到 O(log n) 。缺点：为了严格保证其均衡性，插入和删除操作需要额外花费时间，通过旋转来调整平衡度，导致其插入和删除操作性能较差，在插入后删除频繁的场景中，性能不尽人意。

　　平衡二叉查找树 Balanced Binary Search Tree

　　平衡二叉查找树为改进的二叉查找树，其设计原则能够保证在最坏的情况下，其插入、删除和查找操作也可以实现渐进运行时间为 O(log n) 。

　　平衡二叉查找树，可以理解为是一种不太严格的平衡树。常见的平衡二叉搜索树有 AVL 树（Adelson-Velsky and Landis Tree）、红黑树（Red-Black Tree）、树堆（Treap）、伸展树（Splay Tree）等。

　　AVL 树 Adelson-Velsky and Landis Tree

　　AVL树（Adelson-Velsky and Landis Tree）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为 1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(log n)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL 树得名于它的发明者G. M. Adelson-Velsky 和 Evgenii Landis，他们在 1962 年的论文《An algorithm for the organization of information》中公开了这一数据结构。

　　性质

　　AVL 树本质上是一棵二叉搜索树，因此，它需要满足：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；每个结点的左右子树的高度之差的绝对值（平衡因子）最多为 1。任意节点的左、右子树都是一棵 AVL 树；

　　也就是说 AVL 树是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。

　　优点和用途

　　AVL 树是平衡条件非常严格的二叉查找树，适用于查找多，删除和新增少的场景。windows 对进程地址空间的管理用到了AVL树。

　　红黑树 Red–black tree

　　红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 O(log n) 时间内完成查找、插入和删除，这里的 n 是树中元素的数目。

　　性质

　　红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：节点是红色或黑色。根是黑色。所有叶子都是黑色（叶子是NIL节点）。每个红色节点必须有两个黑色的子节点。（或者说从每个叶子到根的所有路径上不能有两个连续的红色节点。）（或者说不存在两个相邻的红色节点，相邻指两个节点是父子关系。）（或者说红色节点的父节点和子节点均是黑色的。）从任一节点到其每个叶子的所有简单路径（没有重复顶点的路径）都包含相同数目的黑色节点。

　　这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

　　红黑树的优点和用途

　　红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用，如实时应用（real time application）中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为基础模板的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树实现，在 Java 的集合框架 (HashMap、TreeMap、TreeSet)、Nginx 的 Timer 管理、Linux 虚拟内存管理以及 C++ 的 STL 等等都能看到它的应用。

　　红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构（persistent data structure）之一，它们用来构造关联数组和集合，每次插入、删除之后它们能保持为以前的版本。除了 O(log n) 的时间之外，红黑树的持久版本对每次插入或删除需要 O(log n) 的空间。

　　红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

　　红黑树的实现

　　因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量 O(log n) 的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。这是怎么做到的呢？

　　插入

　　首先，假设插入节点是红色的（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的），因为二叉查找树中新增的节点都是放在叶子节点上。因此，关于插入操作的平衡调整，有这样几种情况：如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。如果违背红黑树的定义，就进行调整，调整的过程包含两种操作： 左右旋转改变颜色

　　红黑树的平衡调整过程是一个迭代的过程。我们把正在处理的节点叫做节点。节点会随着不停地迭代处理，而不断发生变化。最开始的节点就是新插入的节点。新节点插入之后，如果红黑树的平衡被打破，那一般会有下面三种情况：情况一：当节点的父节点的兄弟节点是红色时 将节点的父节点、父节点的兄弟节点都设置成黑色；将节点的祖父节点设置成红色；将节点切换为祖父节点；切换至情况二或情况三；情况二：当节点的父节点的兄弟节点是黑色，且节点是父节点的右子树时 切换节点至父节点；围绕新的节点左旋；切换至情况三；情况三：当节点的父节点的兄弟节点是黑色，且节点是父节点的左子树时 围绕节点的祖父节点右旋；节点的父节点、节点的兄弟节点颜色互换；调整结束。

　　分析

　　由于一棵有 n 个节点的红黑树的高度为 O(log n)，在不进行调整时，花费的时间是 O(log n)，当且仅当情况一发生且节点沿着树循环上升时，执行的总次数为 O(log n)，此外，程序执行的旋转从不超过 2 次，因此，插入操作的时间复杂度为 O(log n)。

　　删除

　　删除操作的平衡调整分为两步：针对删除节点初步调整：初步调整只是保证整棵红黑树在一个节点删除之后，仍然满足性质 5，即从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。针对节点进行二次调整：二次调整使得红黑树满足性质 4，即每个红色节点必须有两个黑色的子节点，不存在相邻的两个红色节点。

　　针对删除节点的初步调整，有三种不同的情况：情况一：当要删除的节点只有一个子节点时： 删除节点，并将其子节点替换到对应位置上；将子节点的颜色变为黑色；调整结束，不需要进行二次调整。情况二：当要删除的节点有两个非空的子节点，并且其后继节点就是其右子节点时： 删除节点，并将其后继节点替换到对应位置上；将其后继节点颜色变更为要删除节点的颜色；进行二次调整，将节点切换为后继节点的右子节点。情况三：当要删除的节点有两个非空的子节点，并且其后继节点不是其右子节点时： 找到后继节点，并将其删除，删除过程参考情况一；将要删除的节点替换为后继节点；将后继节点的颜色替换为要删除的节点的颜色；进行二次调整，将节点切换为后继节点的右子节点。

　　针对节点的二次调整，有四种情况：情况一：当节点的兄弟节点是红色： 围绕节点的父节点左旋；节点父节点和祖父节点交换颜色；节点不变，继续从四种情况中选择合适的规则来调整；情况二：当节点的兄弟节点是黑色，并且兄弟节点的左右子节点也都是黑色： 将节点的兄弟节点的颜色改变为红色；将节点变为红色；节点切换为其父节点；继续从四种情况中选择合适的规则进行调整；情况三：当节点的兄弟节点是黑色，并且兄弟节点的左子节点是红色，右子节点是黑色： 围绕节点的兄弟节点右旋；将节点和兄弟节点和其右子节点的颜色互换；节点保持不变，跳转至情况四；情况四：当节点的兄弟节点是黑色，并且兄弟节点的右子节点是红色： 围绕节点的父节点左旋；将节点的兄弟节点和节点的父节点设置为相同的颜色；将节点的父节点设置为黑色；根据规则，将节点变为红色或黑色；将节点的父节点的兄弟节点设置为黑色；调整结束。

　　可以看出，红黑树的实现过程比较复杂。但具体来说，就三点：红黑树的平衡调整的过程类似于魔方复原，即按照固定的操作步骤，保持插入、删除的过程，不破坏平衡树的定义。找准节点。每种基本规则，都是基于节点来做的，在迭代调整的过程中，节点在不停地改变，只有找对了关键节点，才能对应正确的操作规则，最终得到正确的结果。操作复杂度：删除 > 插入 > 搜索，但无论何时，核心要点就是确保最终结果符合定义。

　　分析

　　因为含有 n 个节点的红黑树的高度为 O(log n)，不进行调整时该过程的总时间代价为 O(log n)。在调整的过程中，旋转的时间复杂度为 O(1)，指针变化的次数为红黑树的高度 O(log n)，因此，删除的时间复杂度为 O(log n)。

　　完全二叉树 Complete Binary Tree

　　定义：若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

　　满二叉树 Full Binary Tree

　　定义：满二叉树的结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为 1 的结点。

　　参考资料

　　维基百科《数据结构》（C 语言第二版）严蔚敏 等编著《算法导论》第三版 殷建平 等译极客时间《数据结构与算法之美》王争什么是平衡二叉树通俗易懂的红黑树Full v.s. Complete Binary Trees