数据结构与算法-红黑树

二叉搜索树在极限情况下会退化成链表，为了保证查找的稳定性，引入了平衡二叉搜索树，其中最有名的就是红黑树。

平衡二叉树定义

整棵树里左子树和右子树的高度不能相差1。类似的数据结构有：AVL树、伸展树、树堆、红黑树。

红黑树将节点标记为红节点或者黑节点，它的特点：

1. 所有根节点都是黑节点;
2. 子节点都是黑节点，且值为nil;
3. 红节点不能相邻
4. 每个节点到其叶子节点的所有路径经历的黑节点数都一样。

如何实现平衡

红黑树将所有红色节点去掉会变成四叉树，如图，在将四叉树的节点挂在子节点下，会变成完全二叉树。

红黑树的复杂度

如上所说,完全二叉树的事件复杂度【log2(N-1)~~log2N】,在把红色家进度复杂度不会超过2log2N。