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

文章目录

  • 前言
  • 平衡二叉树
    • 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);elsereturn 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);elsereturn 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;elsestd::cout << "未找到节点: " << key << std::endl;return 0;
}

参考资料

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

写在最后

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

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

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

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

前端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…
阅读更多...
mysql（数据库）可视化工具——Navicat Premium

mysql（数据库）可视化工具——Navicat Premium

Navicat Premium是一款功能强大的数据库管理工具&#xff0c;它支持多种数据库管理系统&#xff0c;包括MySQL、MariaDB、SQL Server、SQLite、Oracle和PostgreSQL等。Navicat Premium提供了直观的用户界面&#xff0c;使用户能够轻松地管理数据库结构、执行复杂的SQL查询、导入…
阅读更多...
从零开始学React--环境搭建

从零开始学React--环境搭建

React官网 快速入门 – React 中文文档 1.搭建环境 下载nodejs,双击安装 nodejs下载地址 更新npm npm install -g npm 设置npm源&#xff0c;加快下载速度 npm config set registry https://registry.npmmirror.com 创建一个react应用 npx create-react-app react-ba…
阅读更多...
生态系统服务功能之碳储量

生态系统服务功能之碳储量

大家好&#xff0c;这期开始新生态系统服务功能即碳储量的计算&#xff0c;这部分较简单&#xff0c;下面让我们开始吧&#xff01;&#xff01;&#xff01; 碳储量的计算公式 生态系统通过从大气中释放和吸收二氧化碳等温室气体来调节地球气候&#xff0c;而森林、 草原和沼…
阅读更多...
PVE虚拟机 安装 OpenWrt

PVE虚拟机 安装 OpenWrt

1、创建虚拟机 2、操作系统 3、磁盘&#xff0c;先删除 4、网络 5、其它默认 6、在 local 分区上传镜像 7、登录PVE虚拟机 # 切换到镜像目录 cd /var/lib/vz/template/iso/# 把镜像导入磁盘 qm importdisk 102 openwrt-buddha-version-v7_2022_-x86-64-generic-squashfs-uefi…
阅读更多...
精选免费在线工具与资源推荐20240531

精选免费在线工具与资源推荐20240531

精选免费在线工具与资源推荐 引言 在互联网高速发展的今天&#xff0c;我们身处一个信息爆炸的时代。为了更好地应对工作和学习中的挑战&#xff0c;我们时常需要借助各种工具和资源来提高效率。幸运的是&#xff0c;网络上存在着大量免费且高效的在线工具和资源&#xff0c;…
阅读更多...
VALL-EX下载介绍：只需3秒录音，即可克隆你的声音

VALL-EX下载介绍：只需3秒录音，即可克隆你的声音

VALL-EX是一个强大和创新的多语言文本转语音模型&#xff0c;支持对中文、英文和日语的语音进行合成和克隆&#xff0c;使用者只需上传一段3-10秒的录音&#xff0c;就可以生成高质量的目标音频&#xff0c;同时保留了说话人的声音、情感和声学环境 VALL-EX的应用范围非常广泛&…
阅读更多...
常见仪表盘指示灯的含义，这次够全了！

常见仪表盘指示灯的含义，这次够全了！

汽车是当前主要的交通工具之一&#xff0c;给人们的工作、生活提供了便利。大家在学会开车的同时&#xff0c;也得了解一些基本的汽车常识&#xff0c;可以及时的发现车辆的问题&#xff0c;并作出正确的判断&#xff0c;以此降低车辆的损耗和维修成本。其中最基本的&#xff0…
阅读更多...
开源监控工具monit安装部署

开源监控工具monit安装部署

Monit 简介 Monit是一个轻量级(500KB)跨平台的用来监控Unix/linux系统的开源工具。部署简单&#xff0c;并且不依赖任何第三方程序、插件或者库。 Monit可以监控服务器进程、文件、文件系统、网络状态&#xff08;HTTP/SMTP等协议&#xff09;、远程主机、服务器资源变化等等。…
阅读更多...
【WEEK14】 【DAY4】Swagger第二部分【中文版】

【WEEK14】 【DAY4】Swagger第二部分【中文版】

2024.5.30 Thursday 接上文【WEEK14】 【DAY3】Swagger第一部分【中文版】 目录 16.4.配置扫描接口16.4.1.修改SwaggerConfig.java16.4.1.1.使用.basePackage()方法指定扫描的包路径16.4.1.2.其他扫描方式均可在RequestHandlerSelectors.class中查看源码 16.4.2.仍然是修改Swag…
阅读更多...
Echarts 让柱状图在图表中展示，离开X轴

Echarts 让柱状图在图表中展示，离开X轴

文章目录 需求分析需求 分析 话不多说，直接源码展示 option = {title: {text: Waterfall Chart,subtext: Li
阅读更多...
STM32 定时器与PWM的LED控制

STM32 定时器与PWM的LED控制

学习目标&#xff1a; 1. 使用定时器的某一个通道控制LED周期性亮灭&#xff1b; 2. 采用定时器PWM模式&#xff0c;让 LED 以呼吸灯方式渐亮渐灭。 一、定时器 1、STM32定时器介绍 STMicroelectronics是STM32微控制器中的重要块&#xff0c;具有丰富的外设和功能&#xff0…
阅读更多...
大模型管理工具Ollama搭建及整合springboot

大模型管理工具Ollama搭建及整合springboot

目录 一、Ollama介绍 1.1 什么是Ollama 1.2 Ollama特点与优势 二、Ollama本地部署 2.1 版本选择 2.2 下载安装包 2.3 执行安装 2.4 Ollama常用命令 三、使用Ollama部署千问大模型 3.1 千问大模型介绍 3.2 部署过程 四、springboot接入Ollama 4.1 引入Ollama依赖 4…
阅读更多...
R语言ggplot2包绘制网络地图

R语言ggplot2包绘制网络地图

重要提示&#xff1a;数据和代码获取&#xff1a;请查看主页个人信息&#xff01;&#xff01;&#xff01; 载入R包 rm(listls()) pacman::p_load(tidyverse,assertthat,igraph,purrr,ggraph,ggmap) 网络节点和边数据 nodes <- read.csv(nodes.csv, row.names 1) edges…
阅读更多...
5.29工效学-人因工程人机交互

5.29工效学-人因工程人机交互

对于工效学这门课&#xff0c;一直都感觉很有意思&#xff0c;是一个值得再认真一点的课。可惜上课的时候效率不高&#xff0c;有感兴趣的东西课后也没有自行去拓展开来&#xff0c;前面的课我感觉还讲了比较重要的东西&#xff0c;但是&#xff0c;全忘了呢&#xff08;真的对…
阅读更多...
Llama改进之——分组查询注意力

Llama改进之——分组查询注意力

引言 今天介绍LLAMA2模型引入的关于注意力的改进——分组查询注意力(Grouped-query attention,GQA)1。 Transformer中的多头注意力在解码阶段来说是一个性能瓶颈。多查询注意力2通过共享单个key和value头&#xff0c;同时不减少query头来提升性能。多查询注意力可能导致质量下…
阅读更多...
民国漫画杂志《时代漫画》第38期.PDF

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

时代漫画38.PDF: https://url03.ctfile.com/f/1779803-1248636380-dd7daa?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps: 资源来源网络!
阅读更多...
Webrtc支持HEVC之FFMPEG支持HEVC编解码(一)

Webrtc支持HEVC之FFMPEG支持HEVC编解码(一)

一、前言 Webrtc使用的FFMPEG(webrtc\src\third_party\ffmpeg)和官方的不太一样，使用GN编译，各个平台使用了不一样的配置文件 以Windows为例，Chrome浏览器也类似 二、修改配置文件 windows：chromium\config\Chrome\win\x64 其他平台: chromium\config\Chrome\YOUR_SYS…
阅读更多...
基础—SQL—DQL（数据查询语言）分组查询

基础—SQL—DQL（数据查询语言）分组查询

一、引言 分组查询的关键字是&#xff1a;GROUP BY。 二、DQL—分组查询 1、语法 SELECT 字段列表 FROM 表名 [ WHERE 条件 ] GROUP BY 分组字段名 [ HAVING 分组后过滤条件 ]; 注意&#xff1a; 1、[ ] 里的内容可以有可以没有。 2、这条SQL语句有两块指定条件的地方&#…
阅读更多...
CSS Canvas鼠标点击特效之天女散花（文本粒子动画）

CSS Canvas鼠标点击特效之天女散花（文本粒子动画）

1.效果 2.代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><style>body,html {margin: 0;padding: 0;wi…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023