共有回帖数 0 个
-
Arne Andersson tree（AA Tree） 是一种平衡二叉搜索树，它其实是如下附加条件的 Red-Black Tree，红色结点必须是其 parent 的 right child。
template typename T
class AATree
{
public:
AATree()
{
nullnode = new node;
nullnode-lchild = nullnode;
nullnode-rchild = nullnode;
root = nullnode;
}
~AATree()
{
Clear();
delete nullnode;
}
void Clear()
{
Clear(root);
}
void Delete(const T &key)
{
Delete(root, key);
}
void Insert(const T &key)
{
Insert(root, key);
}
private:
struct node
{
T key;
int level;
node *lchild, *rchild;
node() : level(0) {}
node(const T &key) : key(key), level(1) {}
}*nullnode, *root;
void Clear(node *root);
void Delete(node *&root, const T &key);
void Insert(node *&root, const T&key);
void LeftRotate(node *&root)
{
node *p = root-rchild;
root-rchild = p-lchild;
p-lchild = root;
root = p;
}
void RightRotate(node *&root)
{
node *p = root-lchild;
root-lchild = p-rchild;
p-rchild = root;
root = p;
}
void Skew(node *&root)
{
if (root-lchild-level == root-level)
RightRotate(root);
}
void Split(node *&root)
{
if (root-rchild-rchild-level == root-level)
{
LeftRotate(root);
++root-level;
}
}
};
template typename T
void AATreeT::Clear(node *root)
{
if (root != nullnode)
{
Clear(root-lchild);
Clear(root-rchild);
delete root;
}
}
template typename T
void AATreeT::Delete(node *&root, const T &key)
{
static node *deletednode = nullnode, *lastnode;
if (root == nullnode)
return;
lastnode = root;
if (key root-key)
Delete(root-lchild, key);
else
{
deletednode = root;
Delete(root-rchild, key);
}
if (root == lastnode)
{
if (deletednode == nullnode || deletednode-key != key)
return;
deletednode-key = root-key;
deletednode = nullnode;
root = root-rchild;
delete lastnode;
}
else if (root-lchild-level root-level-1 || root-rchild-level root-level-1)
{
if (root-rchild-level --root-level)
root-rchild-level = root-level;
Skew(root);
Skew(root-rchild);
Skew(root-rchild-rchild);
Split(root);
Split(root-rchild);
}
}
template typename T
void AATreeT::Insert(node *&root, const T &key)
{
if (root == nullnode)
{
root = new node(key);
root-lchild = nullnode;
root-rchild = nullnode;
return;
}
Insert(key root-key ? root-lchild : root-rchild, key);
Skew(root);
Split(root);
}
楼主 2016-06-09 09:20 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
