手把手教,手写AVL树

 

平衡二叉树相信大家都不陌生了,它是一颗平衡的二叉排序树,它的查询、插入删除的时间复杂度均为O(logn),是非常好且重要的动态查找结构,因此被广泛的应用。而平衡二叉树的实现因为引入了旋转操作而经常让人难以理解,楼主写这篇文章的目的,其实是希望能够通过造轮子的方式,帮助到大家完全理解从普通二叉排序树逐步优化到平衡二叉树(AVL树)的过程。

一、平衡二叉树之AVL树简介

 

而AVL树是一种高度平衡的平衡二叉树,树中的任意节点的左右子树的高度之差不超过1。如果将二叉树上结点的平衡因子BF(Balanced Factor)定义为该结点的左子树与右子树的高度之差,根据AVL树的定义,AVL树中的任意结点的平衡因子只可能是-1(右子树高于左子树)、0或者1(左子树高于右子树),在某些图中也会表示为绝对高度差,即0,1,2这种形式,请注意理解。它通过树的旋转操作来维护平衡特性。下面我会逐步通过C++代码来理解、最终实现AVL树。

二、AVL树实现

1.二叉排序树实现

AVL树是一颗平衡的二叉排序树,所以为了实现AVL树,我们可以先从实现一颗普通的二叉排序树入手,实现一颗普通二叉排序树。为了接下来将二叉排序树优化为AVL树,代码中将树直接取名为AVL。

树中节点具有双亲和左右两个子节点的指针,

插入删除操作都是先查找到节点位置,再进行插入或者删除。

删除时,如果删除的是同时有左右子树的非叶子节点,则寻找该节点的后继节点,替换该节点再将后继节点删除,这里不做过多解释,代码如下:

#include<stdio.h>
#include<malloc.h>

struct AVLNode{
    int value;
    int balance;  //AVL树的平衡字段,普通二叉排序树并不需要用到该字段
    AVLNode* left;
    AVLNode* right;
    AVLNode* parent;
};
//这是一颗普通的二叉排序树,,命名为AVLTree仅仅因为方便起见 struct AVLTree{
    AVLNode* root;
}tree;
//查询操作 struct AVLNode* select(int value,AVLNode* root){
    if(root==0){
        return 0;
    }
    if(root->value==value){
        return root;
    }
    if(root->value>value){
        if(root->left)
            return select(value,root->left);
        else
            return root;
    }
    if(root->value<value){
        if(root->right)
            return select(value,root->right);
        else
            return root;
    }
}
//插入操作
void insert(int value,AVLNode* root){
    AVLNode* node=select(value,root);
    if(node==0){
        tree.root=(AVLNode*)malloc(sizeof(AVLNode));
        tree.root->value=value;
        tree.root->left=tree.root->right=0;
        tree.root->parent=0;
        tree.root->balance=0;
    }
    else if(node->value!=value){
        if(node->value>value){
            node->left=(AVLNode*)malloc(sizeof(AVLNode));
            node->left->value=value;
            node->left->left=node->left->right=0;
            node->left->parent=node;
            node->left->balance=0;
        }else if(node->value<value){
            node->right=(AVLNode*)malloc(sizeof(AVLNode));
            node->right->value=value;
            node->right->left=node->right->right=0;
            node->right->parent=node;
            node->right->balance=0;
        }
    }
}
void delnodeifhas1childornot(AVLNode* a){
    if(a->parent==0){
        if(a->left){
            tree.root=a->left;
            a->left->parent=0;
        }else{
            tree.root=a->right;
            a->right->parent=0;
        }
    }else{
        if(a->parent->left==a){
            if(a->left){
                a->parent->left=a->left;
                a->left->parent=a->parent;
            }else{
                a->parent->left=a->right;
                if(a->right)
                    a->right->parent=a->parent;
            }
        }else{
            if(a->left){
                a->parent->right=a->left;
                a->left->parent=a->parent;
            }else{
                a->parent->right=a->right;
                if(a->right)
                    a->right->parent=a->parent;
            }
        }
    }
}
struct AVLNode* getmin(AVLNode* a){
    if(a->left)
        getmin(a->left);
    else
        return a;
} 
void delnodeifhas2child(AVLNode* a){
    AVLNode* after=getmin(a->right);
    a->value=after->value;
    delnodeifhas1childornot(after);
}
//删除操作
void del(int value,AVLNode* root){ AVLNode* node=select(value,root); if(node->value==value){ if(node->left&&node->right){ delnodeifhas2child(node); }else{ delnodeifhas1childornot(node); } } }

 

2.从二叉排序树到AVL树

2.1 旋转操作原理

AVL树通过左旋右旋来实现它的平衡性。理解左旋和右旋是AVL树实现的关键点,那么问题来了,所谓左旋右旋又具体是怎么样的操作呢?以右旋为例。

初始的AVL树有两个节点,a和b,此时树平衡。

              

 

插入节点c,若节点c小于b,则成为b的左子节点,此时a左子树深度为2,右子树深度为0,处于不平衡状态,此时执行右旋操作。

                           

右旋就是使a、b进行右旋1/4圆,使得b节点作为父节点,a节点变为b节点的右节点,b的左子树在经过右旋操作后仍是b的左子树。

如果b有右子树。那么右旋后b的右子树将成为a的左子树。

 

这就是右旋操作的具体实现,左旋是右旋对称的过程。当二叉树插入或者删除一个节点时,如果破坏了树的平衡性,就会根据树的失衡情况进行旋转操作,如果左子树高于右子树,则右旋,如果右子树高于左子树,则左旋。

右旋及左旋的代码如下:



struct
AVLNode* turnRight(AVLNode* a){ // 右旋使a的父节点的子节点替换为b AVLNode* b=a->left; if(a->parent!=0){ if(a->parent->right==a){ a->parent->right=b; }else{ a->parent->left=b; } } b->parent=a->parent; //将b的右子树作为a的左子树,并将a作为b的右子树 a->parent=b; a->left=b->right; if(a->left!=0) a->left->parent=a; b->right=a; //重新设置a、b节点的balance值 setBalance(a); setBalance(b); //返回b节点 return b; }

struct AVLNode* turnLeft(AVLNode* a){
    //左旋把a的父节点的子节点替换为b
    AVLNode* b=a->right;
    if(a->parent!=0){
        if(a->parent->right==a){
            a->parent->right=b;
        }else{
            a->parent->left=b;
        }
    }
    b->parent=a->parent;
    //将a作为b的左子树,并将b的左子树作为a的右子树
    a->parent=b;
    a->right=b->left;
    b->left=a;
    if(a->right!=0)
        a->right->parent=a;
    //重新设置a\b的balance值
    setBalance(a);
    setBalance(b);
//返回b节点
return b; }
int height(AVLNode* a){
    if(a==0){
        return 0;
    }
    int rightheight=height(a->right);
    int leftheight=height(a->left);
    return rightheight > leftheight ? (rightheight+1) : (leftheight+1);
}
void setBalance(AVLNode* a){
    if(a)
        a->balance=height(a->right)-height(a->left);
}

上面将树从失衡状态恢复到平衡状态只进行了一次旋转操作,事实上还有一种稍微复杂的情况,需要进行两次旋转才能将树重新恢复平衡

 

如果节点插入到a的左子树的右节点,则需要先左旋再右旋来重新平衡树。同理,如果节点插入到a的右子树的左子节点,则需要先右旋再左旋来重新平衡树。如果直接进行右旋,生成的树将仍然是失衡的。

代码如下,调用了上面实现的旋转操作:

struct AVLNode* turnLeftThenRight(AVLNode* a){
    a->left = turnLeft(a->left);
    return turnRight(a);
}
struct AVLNode* turnRightThenLeft(AVLNode* a){
    a->right = turnRight(a->right);
    return turnLeft(a);
}

2.2 实现AVL树插入删除

 AVL树的insert操作,仅仅在二叉排序树的insert基础上增加了rebalance操作。

//AVL树在insert或者del之后进行rebalance操作,从插入节点的父节点开始,逐层向上遍历进行rebalance,直到遍历到根节点,由于树是平衡的,所以rebalance的时间复杂度是O(logn)。
void rebalance(AVLNode* a){
    setBalance(a);
    if(a->balance== -2){                   //如果左子树比右子树高2层,需要通过旋转来重新平衡
        if(a->left->balance <=0){          //如果左子节点的左子树比右子树高,则进行一次右旋;如果左子节点的右子树比左子树高,则先进行左旋,再进行右旋。
            a=turnRight(a);
        }else{
            a=turnLeftThenRight(a);
        }
    }else if(a->balance==2){       //如果右子树比左子树高2层,需要通过旋转来重新平衡
        if(a->right->balance>=0){       //如果右子节点的右子树比左子树高,则进行一次左旋;如果右子节点的右子树比左子树低,则先进行右旋,再进行左旋。
            a=turnLeft(a);
        }else{
            a=turnRightThenLeft(a);
        }
    }
    if(a->parent){
        rebalance(a->parent);
    }else{
        tree.root=a;
    }
}

void insert(int value,AVLNode* root){
    AVLNode* node=select(value,root);
    if(node==0){
        tree.root=(AVLNode*)malloc(sizeof(AVLNode));
        tree.root->value=value;
        tree.root->left=tree.root->right=0;
        tree.root->parent=0;
        tree.root->balance=0;
    }
    else if(node->value!=value){
        if(node->value>value){
            node->left=(AVLNode*)malloc(sizeof(AVLNode));
            node->left->value=value;
            node->left->left=node->left->right=0;
            node->left->parent=node;
            node->left->balance=0;
            rebalance(node);           //插入完成后进行rebalance
        }else if(node->value<value){
            node->right=(AVLNode*)malloc(sizeof(AVLNode));
            node->right->value=value;
            node->right->left=node->right->right=0;
            node->right->parent=node;
            node->right->balance=0;
            rebalance(node);           //插入完成后进行rebalance
        }
    }
}

 

AVL树的删除操作,也只是在二叉排序树的删除操作上,增加了rebalance操作。

void delnodeifhas1childornot(AVLNode* a){
    if(a->parent==0){
        if(a->left){
            tree.root=a->left;
            a->left->parent=0;
        }else{
            tree.root=a->right;
            a->right->parent=0;
        }
    }else{
        if(a->parent->left==a){
            if(a->left){
                a->parent->left=a->left;
                a->left->parent=a->parent;
            }else{
                a->parent->left=a->right;
                if(a->right)
                    a->right->parent=a->parent;
            }
        }else{
            if(a->left){
                a->parent->right=a->left;
                a->left->parent=a->parent;
            }else{
                a->parent->right=a->right;
                if(a->right)
                    a->right->parent=a->parent;
            }
        }
        rebalance(a->parent);
    }
}
struct AVLNode* getmin(AVLNode* a){
    if(a->left)
        getmin(a->left);
    else
        return a;
} 
void delnodeifhas2child(AVLNode* a){
    AVLNode* after=getmin(a->right);
    a->value=after->value;
    delnodeifhas1childornot(after);
}
void del(int value,AVLNode* root){         //删除操作
    AVLNode* node=select(value,root);
    if(node->value==value){
        if(node->left&&node->right){
            delnodeifhas2child(node);
        }else{
            delnodeifhas1childornot(node);
        }
    }
}

完整AVL树c++代码如下:

#include<stdio.h>
#include<malloc.h>

struct AVLNode{
    int value;
    int balance;
    AVLNode* left;
    AVLNode* right;
    AVLNode* parent;
};

struct AVLTree{
    AVLNode* root;
}tree;

int height(AVLNode* a){
    if(a==0){
        return 0;
    }
    int rightheight=height(a->right);
    int leftheight=height(a->left);
    return rightheight > leftheight ? (rightheight+1) : (leftheight+1);
}
struct AVLNode* select(int value,AVLNode* root){
    if(root==0){
        return 0;
    }
    if(root->value==value){
        return root;
    }
    if(root->value>value){
        if(root->left)
            return select(value,root->left);
        else
            return root;
    }
    if(root->value<value){
        if(root->right)
            return select(value,root->right);
        else
            return root;
    }
}
void setBalance(AVLNode* a){
    if(a)
        a->balance=height(a->right)-height(a->left);
}

struct AVLNode* turnLeft(AVLNode* a){
    AVLNode* b=a->right;
    if(a->parent!=0){
        if(a->parent->right==a){
            a->parent->right=b;
        }else{
            a->parent->left=b;
        }
    }
    b->parent=a->parent;
    a->parent=b;
    a->right=b->left;
    b->left=a;
    if(a->right!=0)
        a->right->parent=a;
    setBalance(a);
    setBalance(b);
    return b;
}
struct AVLNode* turnRight(AVLNode* a){
    AVLNode* b=a->left;
    if(a->parent!=0){
        if(a->parent->right==a){
            a->parent->right=b;
        }else{
            a->parent->left=b;
        }
    }
    b->parent=a->parent;
    a->parent=b;
    a->left=b->right;
    if(a->left!=0)
        a->left->parent=a;
    b->right=a;
    setBalance(a);
    setBalance(b);
    return b;
}

struct AVLNode* turnLeftThenRight(AVLNode* a){
    a->left = turnLeft(a->left);
    return turnRight(a);
}
struct AVLNode* turnRightThenLeft(AVLNode* a){
    a->right = turnRight(a->right);
    return turnLeft(a);
}
void rebalance(AVLNode* a){
    setBalance(a);
    if(a->balance== -2){
        if(a->left->balance <=0){
            a=turnRight(a);
        }else{
            a=turnLeftThenRight(a);
        }
    }else if(a->balance==2){
        if(a->right->balance>=0){
            a=turnLeft(a);
        }else{
            a=turnRightThenLeft(a);
        }
    }
    if(a->parent){
        rebalance(a->parent);
    }else{
        tree.root=a;
    }
}

void insert(int value,AVLNode* root){
    AVLNode* node=select(value,root);
    if(node==0){
        tree.root=(AVLNode*)malloc(sizeof(AVLNode));
        tree.root->value=value;
        tree.root->left=tree.root->right=0;
        tree.root->parent=0;
        tree.root->balance=0;
    }
    else if(node->value!=value){
        if(node->value>value){
            node->left=(AVLNode*)malloc(sizeof(AVLNode));
            node->left->value=value;
            node->left->left=node->left->right=0;
            node->left->parent=node;
            node->left->balance=0;
            rebalance(node);
        }else if(node->value<value){
            node->right=(AVLNode*)malloc(sizeof(AVLNode));
            node->right->value=value;
            node->right->left=node->right->right=0;
            node->right->parent=node;
            node->right->balance=0;
            rebalance(node);
        }
    }
}
void delnodeifhas1childornot(AVLNode* a){
    if(a->parent==0){
        if(a->left){
            tree.root=a->left;
            a->left->parent=0;
        }else{
            tree.root=a->right;
            a->right->parent=0;
        }
    }else{
        if(a->parent->left==a){
            if(a->left){
                a->parent->left=a->left;
                a->left->parent=a->parent;
            }else{
                a->parent->left=a->right;
                if(a->right)
                    a->right->parent=a->parent;
            }
        }else{
            if(a->left){
                a->parent->right=a->left;
                a->left->parent=a->parent;
            }else{
                a->parent->right=a->right;
                if(a->right)
                    a->right->parent=a->parent;
            }
        }
        rebalance(a->parent);
    }
}
struct AVLNode* getmin(AVLNode* a){
    if(a->left)
        getmin(a->left);
    else
        return a;
} 
void delnodeifhas2child(AVLNode* a){
    AVLNode* after=getmin(a->right);
    a->value=after->value;
    delnodeifhas1childornot(after);
}
void del(int value,AVLNode* root){
    AVLNode* node=select(value,root);
    if(node->value==value){
        if(node->left&&node->right){
            delnodeifhas2child(node);
        }else{
            delnodeifhas1childornot(node);
        }
    }
}
void insertNodetest(){
    insert(5,tree.root);
    insert(6,tree.root);
    insert(7,tree.root);
    insert(3,tree.root);
    insert(4,tree.root);
    insert(4,tree.root);
    insert(5,tree.root);
    insert(5,tree.root);
    insert(3,tree.root);
    insert(8,tree.root);
    insert(9,tree.root);
    insert(10,tree.root);
    insert(11,tree.root);
    insert(12,tree.root);
}
void delNodetest(){
    del(6,tree.root);
    del(11,tree.root);
    del(12,tree.root);
    del(3,tree.root);
    del(3,tree.root);
    del(5,tree.root);
    del(9,tree.root);
    del(12,tree.root);
}
int main(){
    insertNodetest(); // 测试构建AVL树
    delNodetest();    // 测试删除AVL树节点
}

至此,我们就完全实现了一颗AVL树的插入删除和查询功能。

 

 (欢迎加qq:1363890602,讨论qq群:297572046,备注:编程艺术)

 收藏 (0) 打赏

您可以选择一种方式赞助本站

支付宝赞助

微信钱包赞助

版权所有丨本站资源仅限于学习研究,严禁从事商业或者非法活动!:ABC资源站 » 手把手教,手写AVL树

切换注册

登录

忘记密码 ?

切换登录

注册