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树的定义中是不允许的。
代码输出结果：
REF：
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
相关文章
- 1. AA树 - 红黑树的变种
- 2. 红黑树简单总结
- 3. 红黑树简单实现
- 4. 红黑树简介
- 5. B树、红黑树简单概念
- 6. 二叉排序树、红黑树、AVL树最简单的理解
- 7. 红黑树简介
- 8. 手写红黑树的简单实现
- 9. 红-黑树简介
- 10. STL 简单红黑树的实现
- 更多相关文章...
相关标签/搜索
每日一句
-
每一个你不满意的现在，都有一个你没有努力的曾经。
最新文章
一个历史类的公众号，欢迎关注
欢迎关注本站公众号,获取更多程序园信息
相关文章
- 1. AA树 - 红黑树的变种
- 2. 红黑树简单总结
- 3. 红黑树简单实现
- 4. 红黑树简介
- 5. B树、红黑树简单概念
- 6. 二叉排序树、红黑树、AVL树最简单的理解
- 7. 红黑树简介
- 8. 手写红黑树的简单实现
- 9. 红-黑树简介
- 10. STL 简单红黑树的实现