[算法]红黑树

一.《算法导论》 chapter 13

1.总述

一种很好的“平衡”二叉搜索树；

近乎平衡，没有一条路径的长度是其他路径的2倍；

最坏情况下，基本动态集合操作(search,insert,delete等)的时间复杂度是O(lgn)

2.红黑树满足条件 --定义

 红色r,黑色b

1.每个节点r/b；

2.根节点b;

3.所有叶子b;

4.若一个节点r,则其2各子节点b;

5.从每个节点到叶子节点，路径上包含相同数量的b

3.高度

黑高（black-height）;

一棵有n个内部节点的红黑树，高度至多为2lg(n+1)

4.基本动态操作

略，详见书

二.在C++ STL的应用

set、map、multiset、multimap的内部都是由红黑树实现，默认是从小到达排序。

例如：

set<int> leastNumbers; //小顶堆

set<int, greater<int>> largeNumbers; //大顶堆

三.题目：《剑指offer》最小的k个数