数据结构-03-红黑树

参考博客 ： https://www.cnblogs.com/skywang12345/p/3603935.html

数据结构在线生成工具 ： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

1. 简介

二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 左、右子树也分别为二叉排序树；
4. 没有键值相等的节点

关于红黑树

• 红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

• 因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后，则这些操作最坏情况运行时间为O(n)。

• 红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)，为了保证这个性质，所以红黑树有以下几个特性：

1. 一个节点要么是红的要么就是黑的
2. 根节点一定是黑色的
3. 从叶子节点到根节点 黑色节点一定是一致的（黑高）
4. 不能有两个红色节点相连（叶子节点一定是黑色的）
5. 一般采用红插法，这样可以保证树不会失衡

2. 红黑树的旋转

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。旋转包括两种：左旋和右旋。如下图所示：