AVL 树

2025 年 1 月 12 日 | 2 分钟阅读

算法

删除

步骤 1 开始
步骤 2 存储要删除的元素
步骤 3 执行 BST 以插入第一个元素
步骤 4 遍历到不平衡节点 (z) 的位置，然后转到步骤 5
步骤 5 检查节点 y 作为 z 的较大高度子节点，x 作为 y 的较大高度子节点的位置。
步骤 6 有 4 种可能的排列方式：
步骤 6a y 是 z 的左子节点，x 是 y 的左子节点 (左左情况)
步骤 6b y 是 z 的左子节点，x 是 y 的右子节点 (左右情况)
步骤 6c y 是 z 的右子节点，x 是 y 的右子节点 (右右情况)
步骤 6d y 是 z 的右子节点，x 是 y 的左子节点 (右左情况)
步骤 7 停止

程序

#include<stdio.h>
 
typedef struct node
{
    int data;
    struct node *left,*right;
    int ht;
}node;
 
node *insert(node *,int);
node *Delete(node *,int);
void preorder(node *);
void inorder(node *);
int height( node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);
 
int main()
{
    node *root=NULL;
    int x,n,i,op;
printf("\nEnter an element to be deleted:");
                    scanf("%d",&x);
                    root=Delete(root,x);
}
node * Delete(node *T,int x)
{
    node *p;
    
    if(T==NULL)
    {
        return NULL;
    }
    else
        if(x > T->data)        // insert in right subtree
        {
            T->right=Delete(T->right,x);
            if(BF(T)==2)
                if(BF(T->left)>=0)
                    T=LL(T);
                else
                    T=LR(T);
        }
        else
            if(x<T->data)
            {
                T->left=Delete(T->left,x);
                if(BF(T)==-2)    //Rebalance during windup
                    if(BF(T->right)<=0)
                        T=RR(T);
                    else
                        T=RL(T);
            }
            else
            {
                //data to be deleted is found
                if(T->right!=NULL)
                {    //delete its inorder succesor
                    p=T->right;
                    
                    while(p->left!= NULL)
                        p=p->left;
                    
                    T->data=p->data;
                    T->right=Delete(T->right,p->data);
                    
                    if(BF(T)==2)//Rebalance during windup
                        if(BF(T->left)>=0)
                            T=LL(T);
                        else
                            T=LR(T);\
                }
                else
                    return(T->left);
            }
    T->ht=height(T);
    return(T);
}
 
int height(node *T)
{
    int lh,rh;
    if(T==NULL)
        return(0);
    
    if(T->left==NULL)
        lh=0;
    else
        lh=1+T->left->ht;
        
    if(T->right==NULL)
        rh=0;
    else
        rh=1+T->right->ht;
    
    if(lh>rh)
        return(lh);
    
    return(rh);
}
 
node * rotateright(node *x)
{
    node *y;
    y=x->left;
    x->left=y->right;
    y->right=x;
    x->ht=height(x);
    y->ht=height(y);
    return(y);
}
 
node * rotateleft(node *x)
{
    node *y;
    y=x->right;
    x->right=y->left;
    y->left=x;
    x->ht=height(x);
    y->ht=height(y);
    
    return(y);
}
 
node * RR(node *T)
{
    T=rotateleft(T);
    return(T);
}
 
node * LL(node *T)
{
    T=rotateright(T);
    return(T);
}
 
node * LR(node *T)
{
    T->left=rotateleft(T->left);
    T=rotateright(T);
    
    return(T);
}
 
node * RL(node *T)
{
    T->right=rotateright(T->right);
    T=rotateleft(T);
    return(T);
}
 
int BF(node *T)
{
    int lh,rh;
    if(T==NULL)
        return(0);
 
    if(T->left==NULL)
        lh=0;
    else
        lh=1+T->left->ht;
 
    if(T->right==NULL)
        rh=0;
    else
        rh=1+T->right->ht;
 
    return(lh-rh);
}
 
void preorder(node *T)
{
    if(T!=NULL)
    {
        printf("%d(Bf=%d)",T->data,BF(T));
        preorder(T->left);
        preorder(T->right);
    }
}
 
void inorder(node *T)
{
    if(T!=NULL)
    {
        inorder(T->left);
        printf("%d(Bf=%d)",T->data,BF(T));
        inorder(T->right);
    }
}

输出

Enter an element to be deleted:6
Balanced AVL tree:
							15
					11
							8	
								
Root -> 5
							4
					3
							2

下一主题String Clone()

AVL 树

算法

删除

程序

输出

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

AVL 树

算法

删除

程序

输出

相关帖子

c) RL 旋转

a) LL 旋转

d) RR 旋转

b) LR 旋转

AVL 树中的插入

AVL 树中的删除

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器