在插入和删除操作中,可能会出现上面两个禁止发生的情况,这时候就需要通过树的旋转操作来纠正。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 ----------------------------------------------------
1,数据结构与算法分析 --C语言描述 原书第二版
2,http://blog.csdn.net/ljsspace/article/details/6547450