数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解(题目讲解 简单易懂)

简介: 数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解(题目讲解 简单易懂)

相信很多初学者会跟我一样觉得这里的旋转操作十分抽象,其实十分简单,我们只需要搞清楚插入或删除是个什么情况,再进行对应的旋转即可

平衡二叉树定义

平衡树(Balance Tree,BT) 指的是,任意节点的子树的高度差都小于等于1。常见的符合平衡树的有,B树(多路平衡搜索树)、AVL树(二叉平衡搜索树)等。平衡树可以完成集合的一系列操作, 时间复杂度空间复杂度相对于“2-3树”要低,在完成集合的一系列操作中始终保持平衡,为大型数据库的组织、索引提供了一条新的途径。 [1] 

设“2-3 树”的每个结点存放一组与应用问题有关的数据, 且有一个关键字 (>0的整数) 作为标识。关键字的存放规则如下:对于结点X, 设左、中、右子树均不空, 则左子树任一结点的关键字小于中子树中任一结点的关键字;中子树中任一结点的关键字小于结点X的关键字;而X的关键字又小于右子树中任一结点的关键字, 称这样的“2-3树”为平衡树

平衡二叉树的插入

插入是考试题目中出现频率较高的,如果插入导致了不平衡就要调整各节点之间的关系以重新达到平衡,具体可以分为以下几种

1:LL平衡旋转(右单旋转)

发生这种不平衡的原因是在结点A的左孩子的左子树上插入了新结点,导致A的平衡因子由1变成2失去平衡,这个时候需要一次向右的旋转操作,将A的左孩子B向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点,而B的原右子树则作为A结点的左子树,文字描述还是十分抽象,下面用题目具体讲解

2:RR平衡旋转(左单旋转)

由于在结点A的右孩子的右子树上插入了新结点,A的平衡因为由-1减到-2,导致以A为根的子树失去平衡,需要一次向左的旋转操作,将A的右孩子B向左上旋转代替A成为根结点,A结点向左下旋转成为B的左子树的根结点,而B的原左子树则作为A结点的右子树

3:LR平衡旋转(先左后右双旋转)

由于在A的左孩子的右子树上插入新结点,此时需要进行两次旋转,先将A结点的左孩子B的右子树的根结点C向左上旋转提升B结点的位置,然后把该C结点向右上旋转提升到A结点的位置,只要理解了上述两种旋转这种组合旋转也是十分简单

4:RL平衡旋转

由于在A的左孩子的右子树上插入新结点,需要进行两次旋转操作,先右旋转后左旋转,先将A结点的右孩子B的左子树根结点C向右上旋转提升到B结点的位置,然后将C结点向左上旋转提升到A结点的位置

平衡二叉树的删除

它与插入操作类似,如果删除导致了不平衡,则向上回溯找到第一个不平衡的结点,然后根据上面不平衡的性质进行旋转,与插入的不同之处在于,删除的时候可能需要调整多棵子树进行多次旋转,难说有什么通解,只要把上面插入的四种旋转操作弄清楚这一块还是十分简单的

创作不易 觉得有帮助请点赞关注收藏~~~

相关文章
|
7天前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
39 9
 算法系列之数据结构-二叉树
|
2月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
61 12
|
2月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
60 10
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
60 2
|
3月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
4月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
139 4
|
4月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
241 8
|
5月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
48 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
5月前
|
存储 算法 数据管理
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
这篇文章通过需求分析、代码实现和测试验证,详细介绍了二叉排序树的创建、遍历和删除操作,以及二叉平衡树(AVL)的自平衡特性和单旋转操作,旨在提高树结构在数据管理中的效率和性能。
95 0
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
|
5月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
72 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树