为实习准备的数据结构(5)-- 图解AVL树(平衡二叉搜索树)

原创
02/07 16:55
阅读数 111

在这里插入图片描述

前言

之前种过AVL树,为什么要再写呢?依旧是因为我忘了,重刷一遍呗。

平衡二叉搜索树(AVL树)

二叉搜索树一定程度上可以提高搜索效率,但是当原序列有序,例如序列A = {1,2,3,4,5,6},构造二叉搜索树如图。依据此序列构造的二叉搜索树为右斜树,同时二叉树退化成单链表,搜索效率降低为O(n)。

如下图:
在这里插入图片描述

在此二叉搜索树中查找元素6需要查找6次。二叉搜索树的查找效率取决于树的高度,因此保持树的高度最小,即可保证树的查找效率。同样的序列A,改为下图方式存储,查找元素6时只需比较3次,查找效率提升一倍。

在这里插入图片描述

可以看出当节点数目一定,保持树的左右两端保持平衡,树的查找效率最高。这种左右子树的高度相差不超过1的树为平衡二叉树。

AVL树的节点数据结构

和上面使用的那个普通结构略有不同。

class TreeNode{
   
   
   
public:
	//这几个数据放做公有的,方便操作
    int depth; //深度,这里计算每个结点的深度,通过深度的比较可得出是否平衡
    TreeNode* parent; //该结点的父节点,方便操作
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), depth(0), left(NULL), right(NULL) {
   
   
   }
    TreeNode() : val(0), depth(0), left(NULL), right(NULL) {
   
   
   }
};

在原始数据上创建AVL树

我的代码尝试:
(先对原始数据进行排序,然后再填充二叉搜索树,使用递归的方式。)

#include<iostream>
#include<vector>
using namespace std;

void createTree(vector<int>& vec, TreeNode* root, int begin, int end) {
   
   
   
    //如果只剩一个键
    if (begin == end) {
   
   
   
        root->val = vec[begin];
        return;
    }

    int mid_sz = (begin+end)/2;
    root->val = vec[mid_sz];

    if (mid_sz - 1 >= begin) {
   
   
   
        root->left = new TreeNode(0);
        createTree(vec, root->left, begin, mid_sz - 1);
    }

    root->right = new TreeNode(0);
    createTree(vec, root->right,mid_sz + 1,end);
}

void PreOrderTraverse(TreeNode* root) {
   
   
   
    if (NULL == root)
        return;
    cout << root->val;
    PreOrderTraverse(root->left);
    PreOrderTraverse(root->right);
}

int main() {
   
   
   
    TreeNode* roott = new TreeNode(0);
    vector<int> vec = {
   
   
    0,1,2,3,4,5,6,7};
    createTree(vec,roott,0,vec.size()-1);
    PreOrderTraverse(roott);
}

调整树的节点使平衡的操作:旋转

LL (右旋):在左叶的左侧插入数据

图解过程:
在这里插入图片描述

在这里插入图片描述

代码实现:

//在左叶的左侧插入数据
TreeNode* LL(TreeNode* root) {
   
   
   
    TreeNode* x = root->left;	//即将返回的节点是y的左子节点(就是那个B)
    TreeNode* temp = x->right;	//先把y的右子节点取出来(就是那个E)
    x->right = root;			//把y放进x的右子节点(把A放到B的右节点)
    root->left = temp;			//把前面预存的放到y的左子节点(把E放到A的右节点)
    return x;					//(返回那个B)
}

int main() {
   
   
   
    TreeNode* roott = new TreeNode(0);
    vector<int> vec = {
   
   
    0,1,2,3,4,5,6,7};
    createTree(vec,roott,0,vec.size()-1);
    roott = LL(roott);
    PreOrderTraverse(roott);
}

RR(左旋):在右子叶的右侧插入数据

图解过程:
在这里插入图片描述
在这里插入图片描述

右旋其实就是上面左旋的镜像过程,所以不难,直接仿写上面左旋的过程即可:

代码实现

TreeNode* RR(TreeNode* root) {
   
   
   
    TreeNode* x = root->right;	//即将返回的节点是y的右子节点
    TreeNode* temp = x->left;	//先把x的左子节点取出来
    x->left = root;			//把y放进x的左子节点
    root->right = temp;			//把前面预存的放到y的右子节点  
    return x;
}

int main() {
   
   
   
    TreeNode* roott = new TreeNode(0);
    vector<int> vec = {
   
   
    0,1,2,3,4,5,6,7};
    createTree(vec,roott,0,vec.size()-1);
    roott = RR(roott);
    PreOrderTraverse(roott);
}

后面的部分,就比较抽象了。


LR(左右旋):在左叶节点的右侧插入数据

在这里插入图片描述

我们将这种情况抽象出来,得到下图:
在这里插入图片描述

我们需要对节点y进行平衡的维护。步骤如下图所示(第三个图里面x和z的位置换一下。):
在这里插入图片描述

代码实现

TreeNode* LR(TreeNode* root) {
   
   
   
	root->left = RR(root->left);
	root = LL(root);
	return root;
}
//简单明了啊

RL(右左旋):在右叶节点的左侧插入数据

在这里插入图片描述

我们将这种情况抽象出来,得到下图:

在这里插入图片描述

我们需要对节点y进行平衡的维护。步骤如下图所示(第三个图里面x和z的位置换一下。):
在这里插入图片描述

第二个图中y的左孩子为T1
(被水印遮住的部分为:T1,T2,T3,T4)

代码实现

TreeNode* RL(TreeNode* root) {
   
   
   
    root->right = LL(root->right);
    root = RR(root);
    return root;
}
//简单明了啊

新节点的插入

在这里需要先补两个函数,虽然可能现在看不懂,但是配上调用函数的上下文就懂了。

计算平衡因子

int getBalanceFactor(TreeNode* node){
   
   
   
	if(node==NULL){
   
   
   
		return 0;
	}
	return get_depth(node->left)-getHeight(node->right);
}
int get_depth(TreeNode* node){
   
   
   
	if(node==NULL){
   
   
   
		return 0;
	}
	return node->depth;
}

getBalanceFactor函数返回值的分析:

  1. 如果刚插入的叶子节点的爷爷节点的返回值大于0

    1. 如果刚插入的叶子节点的父节点的返回值大于0:(LL)
    2. 如果刚插入的叶子节点的父节点的返回值小于0:(LR)
  2. 如果刚插入的叶子节点的爷爷节点的返回值小于0

    1. 如果刚插入的叶子节点的父节点的返回值大于0:(RL)
    2. 如果刚插入的叶子节点的父节点的返回值小于0:(RR)

正式插入新节点

TreeNode* Insert_Node(TreeNode* root, int val) {
   
   
   
    //先将节点插入
    if (NULL == root)
        return new TreeNode(val);
    else {
   
   
   
        if (val < root->val)
            root->left = Insert_Node(root->left, val);
        else
            root->right = Insert_Node(root->right, val);
    }
    //计算平衡因子
    int balanceFactor = getBalanceFactor(root);

    //判断是否该旋转,该如何旋转
    if (balanceFactor > 1) {
   
   
       //左子树有事儿
        balanceFactor = getBalanceFactor(root->left);
        if (balanceFactor == 1)     //插左边了
            return LL(root);
        else if (balanceFactor == -1)   //插右边了
            return RR(root);
        else {
   
   
   
            cout << "罕见故障" << endl;
        }
    }
    else if (balanceFactor < -1) {
   
   
     //右子树有事儿
        balanceFactor = getBalanceFactor(root->right);
        if (balanceFactor == 1)     //插左边了
            return RL(root);
        else if(balanceFactor == -1)   //插右边了
            return RR(root);
        else {
   
   
   
            cout << "罕见故障" << endl;
        }
    }
    return root;
}

int main() {
   
   
   
    TreeNode* roott = new TreeNode(0);
    vector<int> vec = {
   
   
    0,1,2,3,4,5,6,7};
    createTree(vec,roott,0,vec.size()-1);
    roott = Insert_Node(roott,8);
    PreOrderTraverse(roott);
}

现有节点删除

代码里的注释把整个过程写的已经很详尽了。

//删除节点
TreeNode* DelSerchNode(TreeNode* node, int e) {
   
   
   
    if (node == NULL)
        return NULL;
    TreeNode* retNode;
    if (e < node->val) {
   
   
   
        node->left = DelSerchNode(node->left, e);
        retNode = node;
    }
    else if (e > node->val) {
   
   
   
        node->right = DelSerchNode(node->right, e);
        retNode = node;
    }
    else {
   
   
    
        // 待删除节点左子树为空的情况
        if (node->left == NULL) {
   
   
   
            TreeNode* rightNode = node->right;
            node->right = NULL;
            retNode = rightNode;
        }
        // 待删除节点右子树为空的情况
        else if (node->right == NULL) {
   
   
   
            TreeNode* leftNode = node->left;
            node->left = NULL;
            retNode = leftNode;
        }
        else {
   
   
   
            // 待删除节点左右子树均不为空的情况
            // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            TreeNode* temp = node;
            while (NULL != temp->left) {
   
   
   
                temp = temp->left;
            }
            node->val = temp->val;
            node->left = NULL;
            //temp = NULL;  //这还删不掉了。。。。这指针还真是顽强
            delete temp;

            retNode = node;
        }
    }
    if (retNode == NULL)
        return NULL;

    //计算平衡因子
    int balanceFactor = getBalanceFactor(retNode);
    //判断是否该旋转,该如何旋转
    if (balanceFactor > 1) {
   
   
       //左子树有事儿
        balanceFactor = getBalanceFactor(retNode->left);
        if (balanceFactor == 1)     //插左边了
            return LL(retNode);
        else if (balanceFactor == -1)   //插右边了
            return RR(retNode);
        else {
   
   
   
            cout << "罕见故障" << endl;
        }
    }
    else if (balanceFactor < -1) {
   
   
     //右子树有事儿
        balanceFactor = getBalanceFactor(retNode->right);
        if (balanceFactor == 1)     //插左边了
            return RL(retNode);
        else if (balanceFactor == -1)   //插右边了
            return RR(retNode);
        else {
   
   
   
            cout << "罕见故障" << endl;
        }
    }
    return retNode;
}

int main() {
   
   
   
    TreeNode* roott = new TreeNode(0);
    vector<int> vec = {
   
   
    0,1,2,3,4,5,6,7};
    createTree(vec,roott,0,vec.size()-1);
    roott = DelSerchNode(roott,5);
    PreOrderTraverse(roott);

先到这里吧。

本文同步分享在 博客“看,未来”(CSDN)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部