CLRS笔记12，二叉查找树/红黑树

二叉查找树
二叉查找树是一颗二叉树，并且每个节点x的左子树中所有节点都不大于x，节点x的右子树中所有节点都不小于x

对一颗高度为h的二叉查找树，动态集合操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR的运行时间均为O(h)

二叉查找树的INSERT操作为从root开始下降，根据大小比较决定左转还是右转，最后递归找到插入的地方
二叉查找树的DELETE操作分三种：1，x没有子女，则将父节点指向NIL；2，x有一个子女，则建立子女和父节点的链；3，x有两个子女，则先删除x的后继y，再用y来替代x

对高度为h的二叉查找树，动态集合操作INSERT和DELETE的运行时间为O(h)

红黑树
二叉查找树的SEARCH性能很好，但是当INSERT和DELETE操作之后很难保证高度的平衡，所以红黑树是一种改进
红黑树是一种自平衡二叉查找树，通过给每个节点着色来保证树的高度平均高度一致：
1）每个节点或者是红的或者是黑的
2）根节点是黑的
3）每个叶节点是黑的
4）红节点的两个儿子都是黑的
5）对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点

可以用数学归纳法证明一颗有n个内节点的红黑树的高度至多为2lg(n+1)
所以红黑树的INSERT、DELETE、SEARCH等动态集合操作的运行时间为O(lgn)