二叉树的意思是：任何节点最多只能有两个子节点的树。
二叉搜索树可提供log(N)的元素插入和访问，它的节点旋转规则是：任何节点的键值一定大于其左子节点树中的每个节点的键值，并小于其右子树中的每个节点的键值。因此，从树节点一直往左走到底，即得最小元素；从根节点一直往右走到底，却得最大元素。
但是，由于插入值无规律，二叉搜索树可能失去平衡，造成搜索效率低落的情况。解决办法就是尽量使树形左右“平衡”，对于何为“平衡”，没有一个绝对的定义，大致的意思就是“没有一个节点过深”。常见的平衡二叉树有AVL-tree, RB-tree, AA-tree，它们都比上面说的一般二叉树复杂，插入节点和删除节点时要做一些额外操作来维护树形平衡，但是它们可以避免极难应付的极不平衡的情况，而且由于它们总是保持某种程度的平衡，所以元素访问时间平均而言就比较少。
SGI STL实现的搜索树是RB-tree，它在一般二叉树的基础上增加了以下必须满足的条件：
１.每个节点不是红色就是黑色；
２.根节点为黑色；
３.如果节点为红，其子节点必须为黑，如果节点为黑，则随意；
４.任一节点到树尾端的任何路径（比如从根节点到任意一个叶节点），所含的黑节点数量必须相同。
根据规则４，新增节点必须为红色；根据规则３，新增节点的父节点必须为黑。当新节点根据一般二叉树搜索规则到达其插入点，却未能符合上述条件时，就必须调整节点颜色和旋转树形。注意经过调整后，叶节点可能为黑色。
针对不同情况，调整和旋转操作可以分成以下四类，见图（取自侯捷《ＳＴＬ源码剖析》）：
RB-tree的用法：
begin()函数获取最左（最小）的节点处，end()获取的是根结点（由于使用了一个实现上的技巧，其实并不是真的根结点）；
empty(), size(), max_size()根据名字可知其意义；
insert_unique(const value_type& x)将x插入RB-tree中，保持节点值独一无二；
insert_equal(const value_type& x)将x插入RB-tree中，允许节点值重复。
rb_tree<int, int, identity<int>, less<int>> itree;cout<<itree.size()<<endl;// 0itree.insert_unique(10);// __rb_tree_rebalanceitree.insert_unique(7);// __rb_tree_rebalanceitree.insert_unique(8);// __rb_tree_rebalance// __rb_tree_rotate_left// __rb_tree_rotate_rightitree.insert_unique(15);// __rb_tree_rebalanceitree.insert_unique(5);// __rb_tree_rebalanceitree.insert_unique(6);// __rb_tree_rebalance// __rb_tree_rotate_left// __rb_tree_rotate_rightitree.insert_unique(11);// __rb_tree_rebalance// __rb_tree_rotate_right// __rb_tree_rotate_leftitree.insert_unique(13);// __rb_tree_rebalanceitree.insert_unique(12);// __rb_tree_rebalance// __rb_tree_rotate_rightcout<<itree.size()<<endl;// 9rb_tree<int, int, identity<int>, less<int>>::iterator it;for( it = itree.begin(); it != itree.end(); it++)cout<<*it<<' ';// 5 6 7 8 10 11 12 13 15it = itree.find( 8);
itree.insert_unique(15);
itree.insert_unique(5);
itree.insert_unique(6);
