平衡二叉树的插入和删除(从现在开始摆脱旋转)

简介: 平衡二叉树的插入和删除(从现在开始摆脱旋转)

一.插入操作

1.找到合适位置插入


2.从下到上,沿着插入节点与根节点的连线,找到不平衡的二叉树


以68为根节点的二叉树平衡,左右子树高度差为1



以60为根节点的二叉树不平衡,左右子树高度差为2,不平衡


3.使不平衡的二叉树平衡,最后插入到原来的二叉树中


再来一个例子


同理,从下到上找根节点,判断是否为平衡二叉树



经观察可以发现,整棵树才是非平衡二叉树,所以从根节点,沿着路径画三个节点,将这三个节点调整为平衡二叉树



调整完毕后剩下的节点按照平衡二叉树的规则填补进去即可



二.删除操作


要求:二叉树的高度不增加


1.直接删除叶子节点



2.被删除的节点无左子树,就让右子树的根节点代替



3.被删除节点无右子树,就让左子树的根节点代替



4.左右都有孩子


那么就找左子树中最大的数(63)替换,或者找右子树中最小的数(67)进行替换


下面是替换了63的例子

目录
相关文章
|
8月前
|
Java
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
74 0
|
8月前
|
数据库 索引
数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解(题目讲解 简单易懂)
数据结构中平衡二叉树插入删除中左旋、右旋、左右双旋、右左双旋的详解(题目讲解 简单易懂)
139 0
|
7月前
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
133 1
|
7月前
数据结构篇:旋转操作在AVL树中的实现过程
数据结构篇:旋转操作在AVL树中的实现过程
53 0
|
存储 算法 C语言
二叉树的概念和性质/向上调整、向下调整算法/堆的插入和删除/堆排序/Top-K问题【上】【数据结构/二叉树/初阶/C语言实现】
二叉树的概念和性质/向上调整、向下调整算法/堆的插入和删除/堆排序/Top-K问题【上】【数据结构/二叉树/初阶/C语言实现】
89 0
|
8月前
|
测试技术
ONT60 旋转链表 思路分享
先将整个链表整体反转,再分别反转前k个和剩下的。
37 0
|
8月前
|
索引
将数组指定索引位置的元素 移动到 目标索引位置,且不改变其他元素原本的顺序,注意这个不是对调元素位置,是移动某一个元素位置不影响其他元素顺(使用场景:拖拽改变数据的顺序,点击上下左右箭头移动元素顺序)
将数组指定索引位置的元素 移动到 目标索引位置,且不改变其他元素原本的顺序,注意这个不是对调元素位置,是移动某一个元素位置不影响其他元素顺(使用场景:拖拽改变数据的顺序,点击上下左右箭头移动元素顺序)
|
算法 Go C++
【面试必刷TOP101】 删除有序链表中重复的元素-I & 删除有序链表中重复的元素-II
【面试必刷TOP101】 删除有序链表中重复的元素-I & 删除有序链表中重复的元素-II
55 0
|
存储 算法
数组算法:倒置,查找,插入,删除
数组算法:倒置,查找,插入,删除
94 0
复杂数据的几种遍历方式(有点绕)
复杂数据的几种遍历方式(有点绕)
67 0