首页 > 代码库 > 20120920-AVL树定义《数据结构与算法分析》
20120920-AVL树定义《数据结构与算法分析》
AVL树节点声明：
1 struct AvlNode
2 {
3 Comparable element;
4 AvlNode *left;
5 AvlNode *right;
6 int height;
7
8 AvlNode( const Comparable & theElement,AvlNode *lt,AvlNode *rt,int h=0):element ( theElement),left(lt),right(rt),height(t)
9 };
计算节点高度：
1 int height( AvlNode * t) const
2 {
3 return t == NULL ? -1 : t->height;
4 }
向AVL中插入操作：
void insert( const Comparable & x,AvlNode * & t)
{
if(t == NULL)
t = new AvlNode ( x,NULL,NULL);
else if (x < t->element);
{
insert( x ,t->left);
if(height(t->left)-height(t->right) == 2)
if(x < t->element)
rotateWithLeftChild(t);
else
doubleWithLeftChild(t);
}
else if (t->element < x)
{
insert(x,t->right);
if(height(t->right) - height(t->left) == 2)
if(t->right->element < x)
rotateWithLeftChild(t);
else
doubleWithLeftChild(t);
}
else
;
t->height = max(height(t->left),height(t->right))+1;
}
执行单旋转过程：
1 void rotateWithLeftChild(AvlNode * & k2)
2 {
3 AvlNode *k1 = k2->left;
4 k2->left = k1->right;
5 k1->right = k2;
6 k2->height = max(height(k2->left),height(k2->right))+1;
7 k1->height = max(height(k1->left),height(k1->right))+1;
8 k2=k1;
9 }
执行双旋转过程：
void doubleWithLeftChild( AvlNode * & k3)
{
rotateWithLeftChild(k3->left);
rotateWithLeftChild(k3);
}
20120920-AVL树定义《数据结构与算法分析》
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。