【基本数据结构】平衡二叉树

文章目录

  • 前言
  • 平衡二叉树
    • 1 简介
    • 2 旋转
      • 2.1 左旋
      • 2.2 右旋
      • 2.3 何时旋转
    • 3 插入节点
    • 4 删除节点
    • 5 代码
  • 参考资料
  • 写在最后

前言

本系列专注更新基本数据结构，现有以下文章：

【算法与数据结构】数组.

【算法与数据结构】链表.

【算法与数据结构】哈希表.

【算法与数据结构】二叉查找树

【算法与数据结构】平衡二叉树

平衡二叉树

1 简介

平衡二叉树是为了解决二叉查找树中树退化成链这一问题而提出的。平衡二叉树在插入、删除某一节点之后通过左旋或右旋操作保持动态平衡，从而避免节点失衡（最坏的情况是树退化成链）。

二叉树某节点是否失衡由该节点的 失衡因子 来衡量，失衡因子为左子树节点高度与右子节点高度之差。

当二叉树中某节点的左、右子树高度差不超过1，则表示该节点平衡，高度差不超过 1 对应平衡因子的值为 ±1 和 0。

左旋与右旋，由于插入、删除节点导致二叉树中出现不平衡节点，此时可以通过左旋或右旋操作调整节点位置以达到二叉查找树的动态平衡。平衡二叉树也是一棵二叉查找树，它的查找、插入、删除都与二叉查找树的操作相同，只是在插入、删除新的节点之后需要通过一些旋转操作来保持其平衡性。

2 旋转

2.1 左旋

左旋，顾名思义，指的是向左旋转节点，或者是逆时针旋转节点。在图 2-1 中，由于插入了一个新的节点到平衡二叉树中，根节点 3 平衡因子变为 0-2=-2，说明此时根节点已经失衡了。为了保持这棵二叉查找树的平衡性，需要左旋根节点。

平衡二叉树-左旋.drawio (1)
图 2-1 左旋

实现代码

// 左旋操作
Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = std::max(height(x->left), height(x->right)) + 1;
    y->height = std::max(height(y->left), height(y->right)) + 1;

    return y;
}

上述代码是左旋的具体操作，传入的一个节点指针 x，表示从该节点开始进行左旋，最终返回的是左旋操作后该子树新的根节点。

以图 2-1 为例，传入的节点为 3，首先记录 3 的右子节点 4，记作 y；接着记录 y 的左子节点空节点，记作 T2；接下来将 4 的左链接连到 3 上，3 的右链接连到空节点上。

最后，还需要更新节点 x 和 y 的高度，为后面计算平衡因子做准备。

2.2 右旋

右旋，指的是向右旋转节点，或者是顺时针旋转节点。在图 2-2 中，由于插入了一个新的节点到平衡二叉树中，根节点 9 平衡因子变为 2-0=2，说明此时根节点已经失衡了。为了保持这棵二叉查找树的平衡性，需要右旋根节点。

平衡二叉树-右旋.drawio (1)
图 2-2 右旋

实现代码

// 右旋操作
Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = std::max(height(y->left), height(y->right)) + 1;
    x->height = std::max(height(x->left), height(x->right)) + 1;

    return x;
}

右旋操作与左旋操作类似，具体实现见代码。

2.3 何时旋转

什么时候需要进行旋转操作，当然是失衡的时候。以下列出的是失衡的四种情况，以及为了保持平衡需要做出的旋转决策：

  • LL型，在当前节点的左子节点的左子节点插入新的节点后，当前节点失衡，此时为了保持平衡需要右旋当前节点。
  • RR型，在当前节点的右子节点的右子节点插入新的节点后，当前节点失衡，此时为了保持平衡需要左旋当前节点。
  • LR型，在当前节点的左子节点的右子节点插入新的节点后，当前节点失衡，此时为了保持平衡需要先左旋当前节点的左子节点，再右旋当前节点。
  • RL型，在当前节点的右子节点的左子节点插入新的节点后，当前节点失衡，此时为了保持平衡需要先右旋当前节点的右子节点，再左旋当前节点。

在 LL型 情况中，我们注意到失衡节点的失衡因子为 2，失衡节点的左子节点的失衡因子为 1。类似的，在 RR型 中，失衡节点的失衡因子为 -2，失衡节点的失衡因子为 -1；在 LR型 中，失衡节点的失衡因子为 2，失衡节点的失衡因子为 -1；在 RL型 中，失衡节点的失衡因子为 -2，失衡节点的失衡因子为 1。于是，我们可以根据失衡节点的失衡因子、失衡节点的左子节点的失衡因子、失衡节点的右子节点的失衡因子来判断当前是什么类型，进而做出相应的旋转决策。

平衡二叉树-LL型.drawio
图 2-3 LL型
平衡二叉树-RR型.drawio
图 2-4 RR型
平衡二叉树-LR型.drawio
图 2-5 LR型
平衡二叉树-RL型.drawio
图 2-6 RL型

3 插入节点

插入节点和在二叉查找树中插入节点一样，先进行未命中的查找，将节点插入到合适的位置。然后根据以上四种情况进行旋转以保持平衡二叉树的平衡性。比如在图 2-6 中插入一个新的节点 8，通过二分查找确定节点 8 的位置为节点 6 右子节点。但是插入节点 8 之后，造成根节点 5 的平衡因子失衡了。因为这是 RL型 情况，所以先右旋根节点的右子树，然后再左旋根节点。

需要注意的是，当插入节点导致多个祖先节点失衡，只需要调整距离插入节点最近的失衡节点即可，其他失衡节点会自动平衡。

平衡二叉树-插入-注意事项.drawio (1)
图 3-1 调整最近的失衡节点

实现代码

// 插入节点
Node* insert(Node* node, int key) {
    if (node == nullptr)
        return new Node(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node;

    node->height = 1 + std::max(height(node->left), height(node->right));

    int balance = getBalance(node);

    // LL 型
    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    // RR 型
    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    // LR 型
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // RL 型
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    return node;
}

在上述插入代码中，我们先进行未命中的查找，在递归查找中插入新的节点。接着，更新当前根节点的高度。最后根据当前节点的平衡因子的不同值来确定是哪一个类型，再根据不同的类型进行相应的调整。具体地：

  • 如果当前节点的失衡因子为 2，并且是在当前节点的左子节点的左子节点插入新的节点，则是 LL 型，右旋该节点即可；
  • 如果当前节点的失衡因子为 -2，并且是在当前节点的右子节点的右子节点插入新的节点，则是 RR 型，左旋节点即可；
  • 如果当前节点的失衡因子为 2，并且是在当前节点的左子节点的右子节点插入新的节点，则是 LR 型，先左旋该节点的左子节点，再右旋该节点；
  • 如果当前节点的失衡因子为 -2，并且是在当前节点的右子节点的左子节点插入新的节点，则是 RL 型，先右旋该节点的右子节点，再左旋该节点；

4 删除节点

删除节点操作也需要先进行查找，递归的进行查找。查找到需要删除的节点 root 之后，按照以下情况进行处理：

  • 如果该节点是叶子节点，直接删除该节点；
  • 如果该节点仅有左子节点或者右子节点，则删除对应的子节点；
  • 如果该节点的左右节点都齐全，则用右子节点中最小的节点更新 root，并删除这个右子节点。

接着更新 root 的高度。最后将失衡的节点旋转，保持平衡。依然是根据当前节点与左、右子节点的平衡因子来判断属于哪种旋转情况，然后进行相应的旋转。

实现代码

// 删除节点
Node* deleteNode(Node* root, int key) {
    if (root == nullptr)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if ((root->left == nullptr) || (root->right == nullptr)) {
            Node* temp = root->left ? root->left : root->right;
            if (temp == nullptr) {
                temp = root;
                root = nullptr;
            } else
                *root = *temp;
            delete temp;
        } else {
            Node* temp = minValueNode(root->right);
            root->key = temp->key;
            root->right = deleteNode(root->right, temp->key);
        }
    }

    if (root == nullptr)
        return root;

    root->height = 1 + std::max(height(root->left), height(root->right));
    int balance = getBalance(root);

    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

5 代码

#include <iostream>
#include <algorithm>

class AVLTree {
private:
    struct Node {
        int key;
        Node* left;
        Node* right;
        int height;
        Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
    };

    Node* root;

    int height(Node* n) {
        return n == nullptr ? 0 : n->height;
    }
    

    // 求平衡因子
    int getBalance(Node* n) {
        return n == nullptr ? 0 : height(n->left) - height(n->right);
    }

    // 右旋操作
    Node* rightRotate(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;

        x->right = y;
        y->left = T2;

        y->height = std::max(height(y->left), height(y->right)) + 1;
        x->height = std::max(height(x->left), height(x->right)) + 1;

        return x;
    }

    // 左旋操作
    Node* leftRotate(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;

        y->left = x;
        x->right = T2;

        x->height = std::max(height(x->left), height(x->right)) + 1;
        y->height = std::max(height(y->left), height(y->right)) + 1;

        return y;
    }

    // 插入节点
    Node* insert(Node* node, int key) {
        if (node == nullptr)
            return new Node(key);

        if (key < node->key)
            node->left = insert(node->left, key);
        else if (key > node->key)
            node->right = insert(node->right, key);
        else
            return node;

        node->height = 1 + std::max(height(node->left), height(node->right));

        int balance = getBalance(node);

        // LL 型
        if (balance > 1 && key < node->left->key)
            return rightRotate(node);

        // RR 型
        if (balance < -1 && key > node->right->key)
            return leftRotate(node);

        // LR 型
        if (balance > 1 && key > node->left->key) {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }

        // RL 型
        if (balance < -1 && key < node->right->key) {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
        return node;
    }

    // 获得最小节点值
    Node* minValueNode(Node* node) {
        Node* current = node;
        while (current->left != nullptr)
            current = current->left;
        return current;
    }

    // 删除节点
    Node* deleteNode(Node* root, int key) {
        if (root == nullptr)
            return root;

        if (key < root->key)
            root->left = deleteNode(root->left, key);
        else if (key > root->key)
            root->right = deleteNode(root->right, key);
        else {
            if ((root->left == nullptr) || (root->right == nullptr)) {
                Node* temp = root->left ? root->left : root->right;
                if (temp == nullptr) {
                    temp = root;
                    root = nullptr;
                } else
                    *root = *temp;
                delete temp;
            } else {
                Node* temp = minValueNode(root->right);
                root->key = temp->key;
                root->right = deleteNode(root->right, temp->key);
            }
        }

        if (root == nullptr)
            return root;

        root->height = 1 + std::max(height(root->left), height(root->right));
        int balance = getBalance(root);

        if (balance > 1 && getBalance(root->left) >= 0)
            return rightRotate(root);

        if (balance > 1 && getBalance(root->left) < 0) {
            root->left = leftRotate(root->left);
            return rightRotate(root);
        }

        if (balance < -1 && getBalance(root->right) <= 0)
            return leftRotate(root);

        if (balance < -1 && getBalance(root->right) > 0) {
            root->right = rightRotate(root->right);
            return leftRotate(root);
        }
        return root;
    }

    // 查找节点
    Node* search(Node* root, int key) {
        if (root == nullptr || root->key == key)
            return root;

        if (key < root->key)
            return search(root->left, key);

        return search(root->right, key);
    }

    // 中序遍历
    void inOrder(Node* root) {
        if (root != nullptr) {
            inOrder(root->left);
            std::cout << root->key << " ";
            inOrder(root->right);
        }
    }

public:
    AVLTree() : root(nullptr) {}

    // 插入节点的对外接口
    void insert(int key) {
        root = insert(root, key);
    }

    // 删除节点的对外接口
    void deleteNode(int key) {
        root = deleteNode(root, key);
    }

    // 搜索节点的对外接口
    bool search(int key) {
        return search(root, key) != nullptr;
    }

    // 中序遍历的对外接口
    void inOrder() {
        inOrder(root);
        std::cout << std::endl;
    }
};

int main() {
    AVLTree tree;

    tree.insert(10);
    tree.insert(20);
    tree.insert(30);
    tree.insert(40);
    tree.insert(50);
    tree.insert(25);

    std::cout << "中序遍历后的AVL树: ";
    tree.inOrder();

    tree.deleteNode(10);

    std::cout << "删除节点10后的AVL树: ";
    tree.inOrder();

    int key = 25;
    if (tree.search(key))
        std::cout << "找到节点: " << key << std::endl;
    else
        std::cout << "未找到节点: " << key << std::endl;

    return 0;
}

参考资料

【视频】平衡二叉树(AVL树)

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家觉得有些地方需要补充，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/669554.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

33【Aseprite 作图】树——拆解

33【Aseprite 作图】树——拆解

1 树叶 画树叶真累啊&#xff0c;可以先画一个轮廓&#xff0c;细节一点点修 2 1 2 &#xff1b;2 2 2 &#xff08;横着横&#xff09;&#xff0c;这样一点点画树叶 填充颜色&#xff0c;用了喷雾工具 2 树干部分 轮廓部分&#xff0c;左边的是3 3 3 &#xff1b;上下都是…
阅读更多...
从不同角度看如何让大模型变得更聪明呢？

从不同角度看如何让大模型变得更聪明呢？

算法创新&#xff0c;从代码上优化大模型&#xff0c;可以采取一系列策略来提升其性能和效率。 算法优化&#xff1a;对模型的算法进行精细调整&#xff0c;如改进神经网络架构&#xff0c;使用更高效的层&#xff08;如深度可分离卷积&#xff09;&#xff0c;或者优化递归神经…
阅读更多...
前端地图中，已知一个点位，获取相同经度或者纬度下的，某个距离的另一个点位

前端地图中，已知一个点位，获取相同经度或者纬度下的，某个距离的另一个点位

效果图说明&#xff1a;我在圆的中心点位&#xff0c;找到他某个直线距离的另个一点&#xff0c;标注两者之间的距离。如图所示是25000米。 沿纬度方向移动 在相同经度下&#xff0c;计算沿纬度方向移动1000米的新点位&#xff1a; function calculateLatitudePoint(lat, ln…
阅读更多...
回归预测 | MATLAB实现基于GOOSE-LightGBM的多特征输入单输出数据回归预测(鹅优化算法)

回归预测 | MATLAB实现基于GOOSE-LightGBM的多特征输入单输出数据回归预测(鹅优化算法)

回归预测 | MATLAB实现基于GOOSE-LightGBM的多特征输入单输出数据回归预测(鹅优化算法) 目录 回归预测 | MATLAB实现基于GOOSE-LightGBM的多特征输入单输出数据回归预测(鹅优化算法)效果一览基本介绍程序设计参考资料 效果一览 基本介绍 MATLAB实现基于LightGBM算法的数据回归预…
阅读更多...
Qt第三方库QicsTable简单实例（1）

Qt第三方库QicsTable简单实例（1）

闲来无事&#xff0c;无意间看到一个Qics表格操作第三方库&#xff0c;自己写了一个特别简单的实例&#xff0c;效果如图所示&#xff1a; 操作界面的数据还是特别快的&#xff0c;因为使用了模型
阅读更多...
java并发处理机制

java并发处理机制

在Java中&#xff0c;并发处理机制主要是通过线程来实现的。Java提供了丰富的类和接口来支持多线程编程&#xff0c;主要集中在 java.util.concurrent 包中。以下是一些关键的并发处理机制&#xff1a; 1.线程创建&#xff1a;可以通过继承 Thread 类或实现 Runnable 接口来创建…
阅读更多...
前端Vue小兔鲜儿电商项目实战Day06

前端Vue小兔鲜儿电商项目实战Day06

一、本地购物车 - 列表购物车 1. 基础内容渲染 ①准备模板 - src/views/cartList/index.vue <script setup> const cartList [] </script><template><div class"xtx-cart-page"><div class"container m-top-20"><div…
阅读更多...
C语言：如何写文档注释、内嵌注释、行块注释？

C语言：如何写文档注释、内嵌注释、行块注释？

技术答疑流程 扫描二维码&#xff0c;添加个人微信&#xff1b;支付一半费用&#xff0c;获取答案&#xff1b;如果满意&#xff0c;则支付另一半费用&#xff1b; 知识点费用&#xff1a;10元 项目费用&#xff1a;如果有项目任务外包需求&#xff0c;可以微信私聊
阅读更多...
Wpf 使用 Prism 实战开发Day31

Wpf 使用 Prism 实战开发Day31

登录数据绑定 1.首先在LoginViewModel 登录逻辑处理类中&#xff0c;创建登录要绑定属性和命令 public class LoginViewModel : BindableBase, IDialogAware {public LoginViewModel(){ExecuteCommand new DelegateCommand<string>(Execure);}public string Title { ge…
阅读更多...
Arduino烧录esp8266

Arduino烧录esp8266

default_encoding: cp936 Assume aggressive ‘core.a’ caching enabled. Note: optional global include file ‘arduino_modified_sketch_764314\Blink.ino.globals.h’ does not exist. Read more at https://arduino-esp8266.readthedocs.io/en/latest/faq/a06-global-bui…
阅读更多...
数据管理知识体系必知的14张语境关系图

数据管理知识体系必知的14张语境关系图

近期对数据管理知识体系中的语境关系图进行了整体学习梳理，总共有14张图，具体如下，供大家参考。应该说语境关系图和环境因素六边形图是各有侧重、互为补充关系。语境关系图是环境因素六边形图的细化，描述了每个知识领域中的细节，相当于数据管理的微观视角， 包括与人员、 …
阅读更多...
秒杀基本功能开发（显示商品列表和商品详情）

秒杀基本功能开发（显示商品列表和商品详情）

文章目录 1.数据库表设计1.商品表2.秒杀商品表3.修改一下秒杀时间为今天到明天 2.pojo和vo编写1.com/sxs/seckill/pojo/Goods.java2.com/sxs/seckill/pojo/SeckillGoods.java3.com/sxs/seckill/vo/GoodsVo.java 3.Mapper编写1.GoodsMapper.java2.GoodsMapper.xml3.分别编写Seck…
阅读更多...
JCR一区级 | Matlab实现TCN-LSTM-MATT时间卷积长短期记忆神经网络多特征分类预测

JCR一区级 | Matlab实现TCN-LSTM-MATT时间卷积长短期记忆神经网络多特征分类预测

JCR一区级 | Matlab实现TCN-LSTM-MATT时间卷积长短期记忆神经网络多特征分类预测 目录 JCR一区级 | Matlab实现TCN-LSTM-MATT时间卷积长短期记忆神经网络多特征分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.JCR一区级 | Matlab实现TCN-LSTM-MATT时间卷积长短…
阅读更多...
用户画像知识点补充——多数据源

用户画像知识点补充——多数据源

引入 针对用户画像项目来说&#xff08;产品&#xff09;必须要支持从多种数据源加载业务数据&#xff0c;构建用户标签。 在之前的标签模型开发中&#xff0c;主要是为了简化开发复杂度&#xff0c;业务数据统一存储到HBase表中。 数据源包含如下几个方面&#xff1a; 存储H…
阅读更多...
民国漫画杂志《时代漫画》第38期.PDF

民国漫画杂志《时代漫画》第38期.PDF

时代漫画38.PDF: https://url03.ctfile.com/f/1779803-1248636380-dd7daa?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps: 资源来源网络!
阅读更多...
R19 NR移动性增强概况

R19 NR移动性增强概况

随着5G/5G-A技术不断发展和业务需求的持续增强&#xff0c;未来网络的部署将不断向高频演进。高频小区的覆盖范围小&#xff0c;用户将面临更为频繁的小区选择、重选、切换等移动性过程。 为了提升网络移动性能和保障用户体验&#xff0c;移动性增强一直是3GPP的热点课题。从NR…
阅读更多...
11.1 排序算法

11.1 排序算法

目录 11.1 排序算法 11.1.1 评价维度 11.1.2 理想排序算法 11.1 排序算法 排序算法&#xff08;sorting algorithm&#xff09;用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用&#xff0c;因为有序数据通常能够被更高效地查找、分析和处理。 如图 1…
阅读更多...
修改element-ui el-radio颜色

修改element-ui el-radio颜色

修改element-ui el-radio颜色 需求效果图代码实现 小结 需求 撤销扣分是绿色&#xff0c;驳回是红色 效果图 代码实现 dom <el-table-columnlabel"操作"width"200px"><template v-slot"scope"><el-radio-group v-model"s…
阅读更多...
短剧源码系统深层次解析：技术架构与实现

短剧源码系统深层次解析：技术架构与实现

短剧源码系统作为短视频内容生产与分发的核心技术&#xff0c;其技术实现对于开发者和运营者至关重要。本文将深入探讨短剧源码系统的关键技术架构&#xff0c;特别是前端框架uni-app和Vue&#xff0c;以及后端框架ThinkPHP5和Workerman的应用。 前端框架&#xff1a;uni-app与…
阅读更多...
Unity打包Webgl端进行 全屏幕自适应

Unity打包Webgl端进行 全屏幕自适应

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一&#xff1a;修改 index.html二&#xff1a;将非移动端设备&#xff0c;canvas元素的宽度和高度会设置为100%。三&#xff1a;修改style.css总结 下载地址&#x…
阅读更多...
最新文章

Copyright @ 2022~2023