admin 管理员组

文章数量: 887021

tree, RB

  二叉树的意思是:任何节点最多只能有两个子节点的树。

  二叉搜索树可提供log(N)的元素插入和访问,它的节点旋转规则是:任何节点的键值一定大于其左子节点树中的每个节点的键值,并小于其右子树中的每个节点的键值。因此,从树节点一直往左走到底,即得最小元素;从根节点一直往右走到底,却得最大元素。

  但是,由于插入值无规律,二叉搜索树可能失去平衡,造成搜索效率低落的情况。解决办法就是尽量使树形左右“平衡”,对于何为“平衡”,没有一个绝对的定义,大致的意思就是“没有一个节点过深”。常见的平衡二叉树有AVL-tree, RB-tree, AA-tree,它们都比上面说的一般二叉树复杂,插入节点和删除节点时要做一些额外操作来维护树形平衡,但是它们可以避免极难应付的极不平衡的情况,而且由于它们总是保持某种程度的平衡,所以元素访问时间平均而言就比较少。

  SGI STL实现的搜索树是RB-tree,它在一般二叉树的基础上增加了以下必须满足的条件:

  1.每个节点不是红色就是黑色;

  2.根节点为黑色;

  3.如果节点为红,其子节点必须为黑,如果节点为黑,则随意;

  4.任一节点到树尾端的任何路径(比如从根节点到任意一个叶节点),所含的黑节点数量必须相同。

  根据规则4,新增节点必须为红色;根据规则3,新增节点的父节点必须为黑。当新节点根据一般二叉树搜索规则到达其插入点,却未能符合上述条件时,就必须调整节点颜色和旋转树形。注意经过调整后,叶节点可能为黑色。

  针对不同情况,调整和旋转操作可以分成以下四类,见图(取自侯捷《STL源码剖析》):

 

 

  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;	// 0
itree.insert_unique(10);	// __rb_tree_rebalance
itree.insert_unique(7);		// __rb_tree_rebalance
itree.insert_unique(8);		// __rb_tree_rebalance// __rb_tree_rotate_left// __rb_tree_rotate_right
itree.insert_unique(15);	// __rb_tree_rebalance
itree.insert_unique(5);		// __rb_tree_rebalance
itree.insert_unique(6);		// __rb_tree_rebalance// __rb_tree_rotate_left// __rb_tree_rotate_right
itree.insert_unique(11);	// __rb_tree_rebalance// __rb_tree_rotate_right// __rb_tree_rotate_left
itree.insert_unique(13);	// __rb_tree_rebalance
itree.insert_unique(12);	// __rb_tree_rebalance// __rb_tree_rotate_right
cout<<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 15
it = itree.find( 8);



itree.insert_unique(15);
itree.insert_unique(5);
itree.insert_unique(6);

本文标签: tree RB