AVL树的研究

3 实现算法

 3.1 数据结构

template<typename T>struct BSTNode//平衡二叉树的结点类型结构体

{

       T data;//结点数据类型

       int bf;//结点的平衡因子,比二叉链表结点多此项

       BSTNode<T>*lchild,*rchild;//左右孩子指针

};

 

3.2 算法

  3.21 递归法

递归实现AVL树的节点删除的思想如下。

   AVLT上删除值为E的节点步骤如下:

(1)       若树T为空,返回0退出否则到(2;

(2)       比较T的数据和E,若相等跳到(3),若E小于T->data跳到(4),若E大于T->data则跳到(5

(3)       分析T节点的类型

(3.1)T是叶子节点则直接删除,树变矮即lower=1

(3.2)T只有右子树TR则将右子树节点的值赋给T,删除TR节点将T->rchild=NULLlower=1;

(3.3)T有左子树,则找到其中序遍历的前驱节点P,将P节点值用临时变量temp保存,并且用指针Tptr保存T;递归删除节点P;将Tptr所指节点即原T节点的值更新为temp

  4)在左子树T->lchild中递归删除值为E的节点,若删除成功检查左子树是否变矮即lower的值是否为1;若lower=0返回0退出;若lower=1则进行失衡调整各种情况上文有分析

  5)在右子树T->rchild中递归删除值为E的节点,若删除成功检查左子树是否变矮即lower的值是否为1;若lower=0返回0退出;若lower=1则进行失衡调整,各种情况上文有分析

 

3.2.2       非递归法

非递归的算法思想如下。

AVLT上删除值为E的节点的步骤如下:

初始化一个栈s ;

 1 若树T为空则返回0退出否则跳到(2);

 2 p为工作指针p=T;比较p的数据和E,若相等则跳到(3),若E小于p->data则跳到(4),若E大于p->data则跳到(5

 3 分析p节点的类型

           3.1)若p是叶子节点则直接删除,树变矮,

3.1.1)若p是其父节点的左子树则lower=1;

3.1.2)若p是其父节点的右子树则lower=2

           3.2 p只有右子树pR则将右子树节点的值赋给p然后删除删除pR,树变矮,lower的值 和(3.1)一样分析,之后不再特别说明则都和(3.1)处理一样。

           3.3 p有左子树pL则将ppL入栈,且用指针tempptr指向ptempptr=p然后执行

                   q=TL ; While(q->rchild){q=q->rchild;s.push(q);}之后可以找到p的前驱节点q,将q的值赋给原p节点即tempptr->data=q->data,若q是叶子节点则直接删除否则将q的左子树代替q。树变矮且弹栈s.pop() ;然后执行如下循环体

                       3.3.1)若栈不空且lower不为0则执行

                                   a.弹栈 q=s.top();s.pop();及其q的父节点fa=s.top();

                                     fa=NULL则表明q是根节点则若要执行下面 b

                                     c时不用在给lower赋值了。

                                   b.lower=1 则表明左子树变矮,执行相应的失衡调整,并且调整过程中若导致q树变矮也得根据qfa的左子树还是右子树将 lower=1或为lower=2

                                   c. lower=2 则表明右子树变矮,执行相应的失衡调整,并且调整过程中若导致q树变矮也得根据qfa的左子树还是右子树将 lower=1或为lower=2

                   退出循环后返回0退出;

 4)将p入栈且p=p->lchild;然后跳到(2);

 5)将p入栈且p=p->rchild;然后跳到(2);

 

 

上一篇:史上最详细阿里云服务器搭建网站流程(图文教程)


下一篇:阿里云新用户免费体验云服务器ECS介绍,可试用1个月!