AA树—简单的红黑树

        AA树是Arne Andersson教授在他的论文"Balanced search trees made simple"中介绍的一个红黑树变种,设计的目的是减少RB树考虑的cases。AA树是一颗红黑树,但是规定红色结点不能作为任何结点的左孩子,也就是说红色结点只能作为右孩子。红黑树和 2-3-4树是等价的数据结构,那么只能有右红孩子结点的红黑树本质上就是 2-3树,所以AA-树的操作结果可以用对应的2-3树上操作的结果验证正确性。另外AA树为实现方便,不再使用红黑两种颜色,而是用level标记结点。level实际上就相当于RB树中的black height,叶子结点的level等于1(反过来,level等于1的不一定是叶子结点,因为等于1的结点可能有一个红色的右孩子),红色结点使用它的父结点的level,黑色结点比它的父结点的level小1。另外,下面两种情况是禁止出现的:

1)连续两个水平方向链(horizontal link),所谓horizontal link是指一个结点跟它的右孩子结点的level相同(左孩子结点永远比它的父结点level小1)。这个规定其实相当于RB树中不能出现两个连续的红色结点。

2)向左的水平方向链(left horizontal link),也就是说一个结点最多只能出现一次向右的水平方向链。这是因为left horizontal link相当于左孩子能为红色结点,这在AA树的定义中是不允许的。

        在插入和删除操作中,可能会出现上面两个禁止发生的情况,这时候就需要通过树的旋转操作来纠正。AA树中只有两个基本操作:skew和split。前者用于纠正出现向左的水平方向链,后者用于纠正出现连续两个水平方向链的情况。skew就是一个右旋转,split是一个左旋转,但两者不是互逆的。skew操作之后可能引起1)的发生(当skew之前已经有一个右孩子的level跟当前结点的level相同),这时需要配合使用split操作。split操作的特点是新的子树的根节点level增加1, 从而会在它的父结点中出现1)(当它作为父结点的左孩子)或者在它的父结点中出现2)(当它作为父结点的右孩子而且父结点跟祖父结点的level相同),这时需要通过skew和split操作纠正这两种情况。

 

 


 
由于split引起的新问题发生在parent一级局部结点,而skew引起的新问题只发生在当前局部结点,所以在实现时需要先skew,再split。

在下面的插入操作中使用递归,删除操作没有使用递归。新插入的结点level等于1。

因为AA树也是平衡BST,它的时间复杂度跟RB树一样,即O(logn),但是旋转次数相对多一些(RB树插入操作最多旋转两次,而且旋转完毕即结束rebalancing;删除操作最多旋转三次,也是旋转完毕即结束rebalancing)

一次实现代码:

#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>

using namespace std;

typedef struct AATreeNode * AATree;
typedef struct AATreeNode 
{
	int data;
	AATree lchild,rchild;
	int level;
} AATreeNode;

AATree NullNode = NULL;
AATree Initialize(void)
{
	if (NullNode == NULL)
	{
		NullNode = new AATreeNode;
		NullNode->lchild = NullNode->rchild = NullNode;
		NullNode->level = 0;
	}
	return NullNode;
}

AATree SingleRotateWithLeft(AATree x)
{
	AATree y = x->lchild;
	x->lchild = y->rchild;
	y->rchild = x;
	return y; 
}

AATree SingleRotateWithRight(AATree x)
{
	AATree y = x->rchild;
	x->rchild = y->lchild;
	y->lchild = x;
	return y; 
}


AATree Skew(AATree T)
{

	if (T->lchild->level == T->level) {
		T = SingleRotateWithLeft(T);
	}
	return T;
}

AATree Split(AATree T)
{
	
	if (T->rchild->rchild->level == T->level) 
	{
		T = SingleRotateWithRight(T);
		T->level++;
	}
	return T;
}

AATree AAInsert(int key, AATree T)
{
	/* work in a recursive way */
	NullNode = Initialize();
	if (T == NullNode) {
		/*create and return an one-node tree*/
		T = new AATreeNode; 
		T->lchild = T->rchild = NullNode;
		T->data = key;
		T->level = 1;
		return T;
	}
	else {
		if (key < T->data) {
			T->lchild = AAInsert(key,T->lchild);
		}
		else {
			if (key > T->data) {
				T->rchild = AAInsert(key,T->rchild);
			}
		}
		/* otherwise it's a duplicate; do nothing */

	}
	T = Skew(T);
	T = Split(T);
	return T;
}

AATree AADelete(int key, AATree T)
{
	static AATree delptr,lastptr;
	if (T != NullNode) 
	{
		/* Step 1: Search down tree */
		/* set delptr and lastptr */
		lastptr = T;
		if (key < T->data) {
			T->lchild = AADelete(key,T->lchild); 
		}
		else {
			delptr = T;
			T->rchild = AADelete(key,T->rchild);
		}
		/* Step 2: If at the bottom of the tree and 
		key is present , delete it  */
		if (T == lastptr) {
			if (delptr != NullNode && key == delptr->data ) {
				/*cout<<"Deleting sub : T ->data = "<<T->data;
				cout<<" lastptr->data = "<<lastptr->data;
				cout<<" delptr->data = "<<delptr->data<<"[1]"<<endl;*/
				delptr->data = T->data;
				delptr = NullNode;
				T = T->rchild;
				delete lastptr;
			}
		}
		/* Step 3 : Otherwise, we are not at the bottom, rebalance */
		else {
			/*cout<<"Deleting sub : T ->data = "<<T->data;
			cout<<" last->data = "<<lastptr->data;
			cout<<" delptr->data = "<<delptr->data<<"[2]"<<endl;*/
			if ( T->lchild->level < T->level - 1 ||			    
				 T->rchild->level < T->level - 1)
			{
				if (T->rchild->level > --T->level)
					T->rchild->level = T->level;
				T = Skew(T);
				T->rchild = Skew(T->rchild);
				T->rchild->rchild = Skew(T->rchild->rchild);
				
				T = Split(T);
				T->rchild = Split(T->rchild);
			} 	 
		} 
	}	
	return T;
}
/* ------------------------about tree build and display-----------------------*/
inline int max(int a,int b)
{
	return a>b?a:b;
}
int Height(AATree T)
{
	if (T == NullNode)
		return 0;
	else
		return 1 + max(Height(T->lchild), Height(T->rchild));
}
void MakeMat(AATree T,int root_x,int root_y,int step,int **m)
{
	int lChildPos,rChildPos;
	lChildPos = root_x - step;
	rChildPos = root_x + step;
	if (T == NullNode) 
		return;
	else
	{
		m[root_y][root_x] = 1;
		MakeMat(T->lchild,lChildPos,root_y+1,step>>1,m);
		MakeMat(T->rchild,rChildPos,root_y+1,step>>1,m);
	}
}

void AATreeDisplay(AATree T)
{
	if(T == NullNode)
		return;
	/* init placehold flags m[h][len] */
	int h = Height(T);
	int len = (1<<h) - 1;
	int row = h; 
	int **m = new int*[row];
	for(int i= 0;i<row;i++){
		m[i] = new int[len];
		memset(m[i],0,len*sizeof(int));	
	}
	/* get level order traversal sequence */
	vector<AATree> v;
	queue<AATree> q;
	queue<AATree> qt;
	q.push(T);
	AATree pt;
	while(!q.empty())
	{
		pt = q.front();
		if (pt->lchild != NullNode)
			q.push(pt->lchild);
		if(pt->rchild != NullNode)
			q.push(pt->rchild);
		v.push_back(pt);		
		q.pop();
	}
	/* generate output matrix  plus '/' and '\\' m[2*h-1][len] */
	MakeMat(T,len>>1,0,len+1>>2,m);
	/* generate output */
	int cnt = 0;
	int width = 3;
	for(int i = 0; i < row; i++)
	{
		for(int j = 0; j < len; j++)
		{
			if(m[i][j])
			{
//				if (i & 1) 
//					cout<<setw(width)<<char(m[i][j]);
//				else
//					cout<<setw(width)<<char(m[i][j]);
//					cout<<setw(width)<<m[i][j];
				cout<<(v[cnt])->level<<':'<<(v[cnt])->data;
				cnt++;
			}
			else
				cout<<setw(width)<<' ';		
		}
		cout<<endl;
	}
	
}
int main()
{
	NullNode = Initialize();
	AATree T = NullNode; 
	int i;
	for(i = 1; i < 7; i++)
	{
		cout<<"Key = "<<i<<" inserting:"<<endl;
		T = AAInsert(i,T);
		AATreeDisplay(T);
		cout<<"---------------------------------------"
			"-------------"<<endl;
	} 
	
	cout<<"Key = "<<8<<" inserting:"<<endl;
	T = AAInsert(8,T);
	AATreeDisplay(T);
	cout<<"---------------------------------------"
	"-------------"<<endl;
	
	cout<<"Key = "<<0<<" inserting:"<<endl;
	T = AAInsert(0,T);
	AATreeDisplay(T);
	cout<<"---------------------------------------"
	"-------------"<<endl;
	
	for(i = 1; i < 7; i++)
	{
		
		cout<<"Key = "<<i<<" deleting:"<<endl;
		T = AADelete(i,T);
		AATreeDisplay(T);
		cout<<"---------------------------------------"
			"-------------"<<endl;
	} 
	
} 

代码输出结果:

Key = 1 inserting:
1:1
----------------------------------------------------
Key = 2 inserting:
   1:1   
      1:2
----------------------------------------------------
Key = 3 inserting:
   2:2   
1:1   1:3
----------------------------------------------------
Key = 4 inserting:
         2:2         
   1:1         1:3   
                  1:4
----------------------------------------------------
Key = 5 inserting:
         2:2         
   1:1         2:4   
            1:3   1:5
----------------------------------------------------
Key = 6 inserting:
                     2:2                     
         1:1                     2:4         
                           1:3         1:5   
                                          1:6
----------------------------------------------------
Key = 8 inserting:
         3:4         
   2:2         2:6   
1:1   1:3   1:5   1:8
----------------------------------------------------
Key = 0 inserting:
                     3:4                     
         2:2                     2:6         
   1:0         1:3         1:5         1:8   
      1:1                                    
----------------------------------------------------
Key = 1 deleting:
         3:4         
   2:2         2:6   
1:0   1:3   1:5   1:8
----------------------------------------------------
Key = 2 deleting:
         2:4         
   1:0         2:6   
      1:3   1:5   1:8
----------------------------------------------------
Key = 3 deleting:
         2:4         
   1:0         2:6   
            1:5   1:8
----------------------------------------------------
Key = 4 deleting:
         2:5         
   1:0         1:6   
                  1:8
----------------------------------------------------
Key = 5 deleting:
   2:6   
1:0   1:8
----------------------------------------------------
Key = 6 deleting:
   1:0   
      1:8
----------------------------------------------------

REF:

1,数据结构与算法分析 --C语言描述  原书第二版

2,http://blog.csdn.net/ljsspace/article/details/6547450

相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
公众号推荐
   一个历史类的公众号,欢迎关注
一两拨千金