红黑树
- 什么是二叉排序（BST）树？
二叉树是空树或者满足一下条件：
- 若它的左子树不为空，则左子树上的左节点的关键字的值均小于根节点关键字的值。
- 若它的右子树不为空，则右子树上的左节点的关键字的值均大于根节点关键字的值。
- 左右子树又分别是一颗二叉排序树
-
什么是平衡二叉（AVL）树？
平衡二叉树首先是二叉查找树，由于树越矮查找效率越高，就有了二叉查找树。二叉平衡树中所有平衡因子只能是-1，0，1三个值 -
什么是平衡因子？
一个结点的平衡因子为其左子树的高度减去右子树高度的差。 -
什么是红黑树？
-
漫画讲解
-
link
-
红黑树是一颗二叉搜索树，它相对二叉搜索树增加了一个存储位来标识结点颜色，可以使 Red 或 Black。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，确保没有一条路径会比其他路径长出两倍。
-
红黑树有什么特点？
-
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
简单来说：
- 根节点和叶子节点是黑色的；
- 从每个叶子到根的所有路径上不能有两个连续的红色节点；
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点；
-
红黑树什么时候调整？
-
什么情况下会破坏红黑树的规则，什么情况下不会破坏规则呢？我们举两个简单的栗子：
在举例子之前，我们做一点小小的补充！
插入之前所有根至外部节点的路径上黑色节点数目都相同，所以如果插入的节点是黑色肯定错误（黑色节点数目不相同），
而相对的插入红节点可能会也可能不会违反“没有连续两个节点是红色”这一条件，所以插入的节点为红色，如果违反条件再调整
-
红黑树如何调整？
-
变色：
为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。
-
左旋转：
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子
右旋转：
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子