红黑树

基本概念

红黑树是一棵二叉搜索树。新插入的结点是红色的（为了不破坏黑高相同特性），如果插入后不符合定义可再进行旋转变色。

黑高：从某结点出发（不包含该结点）到达任意一个叶结点（包含该叶结点）的路径上黑结点的数量。

每个结点要么是红色，要么是黑色
根结点和叶结点（NIL）是黑色的
每个红色结点必须有两个黑色子结点
任意结点到叶结点的简单路径中包含相同数量的黑结点

口诀：根黑叶黑，不能连续红，必须相同黑。

1、从根结点到叶结点的最长路径不大于最短路径2倍。

2、有n个内部结点的红黑树高度$h\leq2log_2 (n+1)$

红黑树本身是一棵BST，所以查找和BST相同。

旋转操作不会改变树中序遍历的顺序

旋转操作通过降低高度高的子树的高度，增加高度低的子树的高度来维护二叉树的平衡

旋转操作和平衡二叉树相同。