【数据结构】平衡二叉树

embedded/2024/12/23 17:27:18/

目录

一、概念

二、平衡二叉树的插入

（一）插入步骤

（二）旋转

1、左旋

2、右旋

3、左右双旋

4、右左双旋

三、特点

四、整体代码

一、概念

        平衡二叉树是在二叉搜索树的改进，二叉搜索树详见：【数据结构】二叉搜索树-CSDN博客

        若使用递增序列持续插入构建二叉搜索树，会导致二叉搜索树严重不平衡，查找效率退化至O（N），即失去了二叉搜索树的优势。

        因此为了提高查找效率，引入了平衡二叉树：在一棵搜索二叉树中每个节点的左右子树的高度差的绝对值不超过1。左右子树的高度差称为平衡因子，平衡因子=右子树高度-左子树高度，当然左子树高度-右子树高度也是能满足需求的。

        本文仅对平衡二叉树的插入部分进行讲解。而对平衡二叉树节点进行删除：先按照二叉搜索树的特性寻找目标节点，删除节点后更新平衡因子时，平衡因子为1或-1便可以停止向上更新。当平衡因子绝对值大于1时，同样需要进行旋转解决。

        平衡二叉树在通过大量的旋转控制整颗树任意一个节点的左右子树高度差不大于1，使树的结构近似完全二叉树，极大地提高了搜索效率。但是因为频繁地旋转会导致其插入删除地效率不高。

二、平衡二叉树的插入

          本文中定义节点的数据结构：

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& data = K()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<K, V>* _pLeft;AVLTreeNode<K, V>* _pRight;AVLTreeNode<K, V>* _pParent;pair<K, V> _data;int _bf;   // 节点的平衡因子
};

（一）插入步骤

        平衡二叉树的插入和二叉搜索树的插入步骤在寻找节点及插入节点时完全相同，只是平衡二叉树书多了平衡因子的更新以及旋转部分。

        首先依靠二叉搜索树的特性寻找插入位置。在找到目标位置后插入元素并维护其与父节点的指针关系。在本文采用 平衡因子=右子树高度-左子树高度 ，因此根据插入节点位置更新父节点的平衡因子并判断是否需要旋转调整平衡。

        以上两种情况，情况一插入更新完节点平衡因子后无需旋转调整，而情况二插入后平衡因子异常需要旋转调整。

        插入的情况其实简单可以分为四种情况：

（二）旋转

         当出现上图情况时，就需要对平衡二叉树的节点进行旋转，旋转的目的是要让这颗树继续维持平衡二叉树的形态，同时调节子树的高度，让其和插入前的高度保持一致，旋转后不要忘记更新那些被旋转的节点的平衡因子。    

        实际对于平衡二叉树插入节点来说，经过旋转后子树的高度没有变化，因此无需向上检查平衡因此是否异常。

1、左旋

        上图是左旋的示意图，节点60不一定为该树的根，也可能是子树，我们将发生平衡因子异常的最小子树的根暂称为根，也就是上图的节点60，将该子树中的节点90暂称为父节点，下文中不进行赘述了。

        上图中插入节点后，节点60的平衡因子异常，因为节点60的平衡因子为2且节点90的平衡因子为1，因此判断插入的位置为节点90的右子树中，故需要左旋调整子树，将节点90的左子树托孤给节点60的右指针，再将节点60作为节点90的左孩子。经过调整后该子树高度不变且满足二叉平衡树的特性。

// 左单旋
void RotateL(Node* pParent)
{Node* parent = pParent;//记录节点90的父节点//旋转后需要维护子树与父节点的连接关系Node* pNode = parent->_pParent;Node* subR = parent->_pRight;//将60的左孩子托孤给90的右指针parent->_pRight = subR->_pLeft;//60的左孩子可能为空 因此只要不为空时需要维护其与父节点90的连接关系if (subR->_pLeft)subR->_pLeft->_pParent = parent;//节点60的左指针指向节点90subR->_pLeft = parent;parent->_pParent = subR;//维护整棵子树与上层父节点的关系if (pNode == nullptr){_pRoot = subR;subR->_pParent = nullptr;}else{if (pNode->_pLeft == parent){pNode->_pLeft = subR;}else{pNode->_pRight = subR;}subR->_pParent = pNode;}//更新平衡因子parent->_bf = 0;subR->_bf = 0;
}

2、右旋

         上图中插入节点后，节点90的平衡因子异常，因为节点90的平衡因子为-2且节点60的平衡因子为-1，因此判断插入的位置为节点60的左子树中，故需要右旋调整子树，将节点60的右子树托孤给节点90的右指针，再将节点90作为节点60的右孩子。经过调整后该子树高度不变且满足二叉平衡树的特性。

void RotateR(Node* pParent)
{Node* parent = pParent;//记录节点90的父节点Node* pNode = parent->_pParent;Node* subL = parent->_pLeft;//将节点60的右孩子托孤给节点90的左指针parent->_pLeft = subL->_pRight;if (subL->_pRight)subL->_pRight->_pParent = parent;//节点60的右指针指向节点90subL->_pRight = parent;parent->_pParent = subL;//维护整棵子树与节点的连接关系if (pNode == nullptr){_pRoot = subL;subL->_pParent = nullptr;}else{if (pNode->_pLeft == parent){pNode->_pLeft = subL;}else{pNode->_pRight = subL;}subL->_pParent = pNode;}//更新平衡因子parent->_bf = 0;subL->_bf = 0;
}

3、左右双旋

        上图中插入节点，节点90的平衡因子异常，因为节点90的平衡因子为-2且节点30的平衡因子为1，因此判断插入节点的位置在节点30的右子树中并记录插入后节点60的平衡因子，故需要进行左右双旋调整子树。

        首先进行左旋：将节点60的左子树托孤给节点30的右指针，节点90的左指针指向节点60，而节点60的左指针指向节点30。其次再进行右旋：将节点60的右子树托孤给节点90的左指针，节点60的右指针指向节点90。

        上述过程实际可以直接简化为将节点60的左子树托孤给节点30的右指针，将节点60的右子树托孤给节点90的左指针，将节点60的左指针指向节点30，节点60的右指针指向节点90。完成旋转后根据先前记录的平衡因子再更新节点30和节点90的平衡因子：

        （1）若节点60的平衡因子为1，说明插入节点为节点60的右孩子，进行旋转后节点30的平衡因子为-1，节点90的平衡因子为0；

        （2）若节点60的平衡因子为-1，说明插入节点为节点60的左孩子，进行旋转后节点30的平衡因子为0，节点90的平衡因子为1；

        （3）若节点60的平衡因子为0，说插入的节点就是为节点60，进行旋转后节点30、60和90的平衡因子都为0。

        经过调整后该子树高度不变且满足二叉平衡树的特性。

// 左右双旋
void RotateLR(Node* pParent)
{//记录旋转前的节点Node* parent = pParent;Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;//记录节点60的平衡因子int bf = subLR->_bf;RotateL(parent->_pLeft);RotateR(parent);//根据60的平衡因子更新节点30、60和90的平衡因子if (bf == 1){parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else if (bf == -1){parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subLR->_bf = 0;subL->_bf = 0;}else{assert(false);}
}

4、右左双旋

        

        上图中插入节点，节点30的平衡因子异常，因为节点30的平衡因子为2且节点90的平衡因子为-1，因此判断插入节点的位置在节点90的左子树中并记录插入后节点60的平衡因子，故需要进行右左双旋调整子树。

        首先进行右旋：将节点60的右子树托孤给节点90的左指针，节点30的右指针指向节点60，而节点60的右指针指向节点90。其次再进行左旋：将节点60的左子树托孤给节点30的右指针，节点60的左指针指向节点30。

        上述过程实际可以直接简化为将节点60的左子树托孤给节点30的右指针，将节点60的右子树托孤给节点90的左指针，将节点60的左指针指向节点30，节点60的右指针指向节点90。完成旋转后根据先前记录的平衡因子再更新节点30和节点90的平衡因子：

        （1）若节点60的平衡因子为1，说明插入节点为节点60的右孩子，进行旋转后节点30的平衡因子为-1，节点90的平衡因子为0；

        （2）若节点60的平衡因子为-1，说明插入节点为节点60的左孩子，进行旋转后节点30的平衡因子为0，节点90的平衡因子为1；

        （3）若节点60的平衡因子为0，说插入的节点就是为节点60，进行旋转后节点30、60和90的平衡因子都为0。

        经过调整后该子树高度不变且满足二叉平衡树的特性。

// 右左双旋
void RotateRL(Node* pParent)
{//记录旋转前的节点Node* parent = pParent;Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;//记录节点60的平衡因子int bf = subRL->_bf;//复用之前的代码RotateR(parent->_pRight);RotateL(parent);//根据60的平衡因子更新节点30、60和90的平衡因子if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}

三、平衡二叉树的检测       

// AVL树的验证
bool IsAVLTree()
{return _IsAVLTree(_pRoot);
}
// 根据AVL树的概念验证pRoot是否为有效的AVL树
bool _IsAVLTree(Node* pRoot)
{if (pRoot == nullptr)return true;int left = _Height(pRoot->_pLeft);int right = _Height(pRoot->_pRight);if (right - left != pRoot->_bf){cout << pRoot->_data.first << "平衡因子异常" << endl;return false;}return (abs(right - left) < 2) && _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
}
size_t _Height(Node* pRoot)
{if (pRoot == nullptr)return 0;return (_Height(pRoot->_pLeft) > _Height(pRoot->_pRight) ? 
_Height(pRoot->_pLeft) + 1 : _Height(pRoot->_pRight) + 1);
}

        平衡二叉树的检测就是对平衡因子的检查，不仅仅是检查平衡因子的值是否在[-1， 1]的范围内，还要检查平衡因子的值是否有效。采用递归的方式去求得左子树和右子树的高度，二者相减得出实际的平衡因子。将得出的平衡因子和记录的平衡因子作比较，若不符合则返回 false，若成功则递归检查其他节点。

四、整体代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& data = K()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<K, V>* _pLeft;AVLTreeNode<K, V>* _pRight;AVLTreeNode<K, V>* _pParent;pair<K, V> _data;int _bf;   // 节点的平衡因子
};// AVL: 二叉搜索树 + 平衡因子的限制
template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:AVLTree(): _pRoot(nullptr){}//中序遍历void Inorder(){_Inorder(_pRoot);}// 在AVL树中插入值为data的节点bool Insert(const pair<K, V>& data){if (_pRoot == nullptr){_pRoot = new Node(data);return true;}Node* cur = _pRoot;Node* parent = nullptr;//寻找插入位置	while (cur){if (cur->_data.first < data.first){parent = cur;cur = cur->_pRight;}else if (cur->_data.first > data.first){parent = cur;cur = cur->_pLeft;}elsereturn false;}cur = new Node(data);//插入节点if (cur->_data.first < parent->_data.first){parent->_pLeft = cur;}else{parent->_pRight = cur;}cur->_pParent = parent;while (parent){//平衡因子更新if (parent->_pRight == cur)parent->_bf++;elseparent->_bf--;//判断是否需要旋转if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_pParent;}else if (parent->_bf == 0){break;}else{if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else{assert(false);}break;}}return true;}// AVL树的验证bool IsAVLTree(){return _IsAVLTree(_pRoot);}private:// 根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsAVLTree(Node* pRoot){if (pRoot == nullptr)return true;int left = _Height(pRoot->_pLeft);int right = _Height(pRoot->_pRight);if (right - left != pRoot->_bf){cout << pRoot->_data.first << "平衡因子异常" << endl;return false;}return (abs(right - left) < 2) && _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);}size_t _Height(Node* pRoot){if (pRoot == nullptr)return 0;return (_Height(pRoot->_pLeft) > _Height(pRoot->_pRight) ? _Height(pRoot->_pLeft) + 1 : _Height(pRoot->_pRight) + 1);}// 右单旋void RotateR(Node* pParent){Node* parent = pParent;Node* pNode = parent->_pParent;Node* subL = parent->_pLeft;parent->_pLeft = subL->_pRight;if (subL->_pRight)subL->_pRight->_pParent = parent;subL->_pRight = parent;parent->_pParent = subL;if (pNode == nullptr){_pRoot = subL;subL->_pParent = nullptr;}else{if (pNode->_pLeft == parent){pNode->_pLeft = subL;}else{pNode->_pRight = subL;}subL->_pParent = pNode;}parent->_bf = 0;subL->_bf = 0;}// 左单旋void RotateL(Node* pParent){Node* parent = pParent;Node* pNode = parent->_pParent;Node* subR = parent->_pRight;parent->_pRight = subR->_pLeft;if (subR->_pLeft)subR->_pLeft->_pParent = parent;subR->_pLeft = parent;parent->_pParent = subR;if (pNode == nullptr){_pRoot = subR;subR->_pParent = nullptr;}else{if (pNode->_pLeft == parent){pNode->_pLeft = subR;}else{pNode->_pRight = subR;}subR->_pParent = pNode;}parent->_bf = 0;subR->_bf = 0;}// 右左双旋void RotateRL(Node* pParent){Node* parent = pParent;Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;int bf = subRL->_bf;RotateR(parent->_pRight);RotateL(parent);if (bf == 1){parent->_bf = -1;subRL->_bf = 0;subR->_bf = 0;}else if (bf == -1){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 1;}else if (bf == 0){parent->_bf = 0;subRL->_bf = 0;subR->_bf = 0;}else{assert(false);}}// 左右双旋void RotateLR(Node* pParent){Node* parent = pParent;Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;RotateL(parent->_pLeft);RotateR(parent);if (bf == 1){parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else if (bf == -1){parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subLR->_bf = 0;subL->_bf = 0;}else{assert(false);}}//中序遍历void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_pLeft);cout << root->_data.first << " ";_Inorder(root->_pRight);}private:Node* _pRoot;
};

http://www.ppmy.cn/embedded/148125.html

相关文章

Linux系统加固

Linux系统加固

Linux系统安全加固 文章目录 Linux系统安全加固密码策略文件、目录安全未授权suid、未授权sgid排查与加固禁止root登录ftp、禁止匿名访问ftp计划任务排查与加固、开机自启排查与加固限定root用户远程ssh登录日志加固 无用账号、用户组和空口令账户排查与加固 禁用或删除无用账号…
阅读更多...
【mysql】1205 -Lock wait timeout exceeded； try restarting transaction

【mysql】1205 -Lock wait timeout exceeded； try restarting transaction

问题&#xff1a; mysql8执行SQL提示下面错误&#xff1a; 1205 -Lock wait timeout exceeded; try restarting transaction 1205-超过锁定等待超时&#xff1b;尝试重新启动事务 可能的原因&#xff1a; 事务冲突&#xff1a;多个事务同时尝试修改同一行数据&#xff0c;导…
阅读更多...
使用ElasticSearch实现全文检索

使用ElasticSearch实现全文检索

文章目录 全文检索任务描述技术难点任务目标实现过程1. java读取Json文件&#xff0c;并导入MySQL数据库中2. 利用Logstah完成MySQL到ES的数据同步3. 开始编写功能接口3.1 全文检索接口3.2 查询详情 4. 前端调用 全文检索 任务描述 在获取到数据之后如何在ES中进行数据建模&a…
阅读更多...
设计模式の享元模板代理模式

设计模式の享元模板代理模式

文章目录 前言一、享元模式二、模板方法模式三、代理模式3.1、静态代理3.2、JDK动态代理3.3、Cglib动态代理3.4、小结 前言 本篇是关于设计模式中享元模式、模板模式、以及代理模式的学习笔记。 一、享元模式 享元模式是一种结构型设计模式&#xff0c;目的是为了相似对象的复用…
阅读更多...
druid与pgsql结合踩坑记

druid与pgsql结合踩坑记

最近项目里面突然出现一个怪问题&#xff0c;数据库是pgsql&#xff0c;jdbc连接池是alibaba开源的druid&#xff0c;idea里面直接启动没问题&#xff0c;打完包放在centos上和windows上cmd窗口都能直接用java -jar命令启动&#xff0c;但是放到国产信创系统上就是报错&#xf…
阅读更多...
STM32F407 | Embedded IDE01 - vscode搭建Embedded IDE开发环境（支持JLINK、STLINK、DAPLINK）

STM32F407 | Embedded IDE01 - vscode搭建Embedded IDE开发环境（支持JLINK、STLINK、DAPLINK）

导言 Embedded IDE官网:https://em-ide.com/docs/intro 我猜肯定有部分人使用SI Keil开发STM32项目&#xff0c;也有vscode Keil开发STM32程序。SI或vscode编写代码&#xff0c;然后切换Keil编译、下载、调试程序。有一段时间&#xff0c;我也是这么干的。但是&#xff0c;程…
阅读更多...
分布式系统架构：服务容错

分布式系统架构：服务容错

1.为什么需要容错 分布式系统的本质是不可靠的&#xff0c;一个大的服务集群中&#xff0c;程序可能崩溃、节点可能宕机、网络可能中断&#xff0c;这些“意外情况”其实全部都在“意料之中”。故障的发生是必然的&#xff0c;所以需要设计一套健壮的容错机制来应对这些问题。 …
阅读更多...
CSS系列（30）-- 逻辑属性详解

CSS系列（30）-- 逻辑属性详解

前端技术探索系列&#xff1a;CSS 逻辑属性详解 &#x1f310; 致读者&#xff1a;探索国际化布局的艺术 &#x1f44b; 前端开发者们&#xff0c; 今天我们将深入探讨 CSS 逻辑属性&#xff0c;这个强大的国际化布局特性。 基础概念 &#x1f680; 逻辑属性映射 /* 物理…
阅读更多...
最新文章

Copyright @ 2022~2023