[数据结构]深入浅出讲解二叉树-平衡二叉树-左右旋转

树是一种数据结构,单位为Node(节点)。不同于链表的直线排列,树呈现一种自上而下的分层排序规则。

        树->数据结构:
        单元为Node(节点)->当这样的节点多了 就可以关联出不同的形态
        一个父节点有一个左子节点,有一个右子节点
        有的节点下方没有其他数据 也就没有左子节点和右子节点了
        事实上,每一个节点都是一个独立的对象。存在着:
        a.本身储存的值 b.父节点地址 c.左子节点地址 d.右子节点地址
        看到这里,我们会想到链表。因此链表也是有数据域和指针域
        你会发现 如果我们聚焦目光于一个节点
        同链表相比,二叉树的节点在数据域上是相差无几的
        只是指针域被分成了三个部分:父节点的地址,左子节点的地址,右子节点的地址
        树结构中,普及一些专业名词:
        1.度:每一个节点的子节点数称为度。普通二叉树的非根节点和最底层节点的度均是2
        2.二叉树:我们同样观察到,有一种树最上层的节点没有父节点
        最下层的节点没有左右子节点,我们将一种度<=2的的数据结构称为二叉树
        3.树的高度:也就是树的总层数。
        4.根节点:最上层的节点(只有唯一一个)
        5.根节点的左子树:这个左子树相当于以其左子节点作为一棵新树的根节点
        由这个左子节点衍生出来的一整棵树都是根节点的左子树
        6.根节点的右子树:原理如上。
        7.二叉查找树:
        二叉查找树是一种特殊的二叉树,它具有以下性质:
          1.每一个节点上最多有两个子节点(首先是一个二叉树)
          2.任意节点左子树的大小均小于当前节点
          3.任意节点的右子树的大小均大于当前节点
        添加原则:
          1.小的存左边
          2.大的存右边
          3.一样大的不存
        8.二叉树的遍历方式
        a.前序遍历:从根节点开始,按照 当前->左子树->右子树顺序遍历
        b.中序遍历(最重要):按照左子树->当前节点->右子树顺序遍历
        c.后序遍历:按照左子树->当前->右子树的顺序进行遍历
        d.层序遍历:从上到下一个一个取 注意 先左后右
        这个东西很好理解 前序就是当前节点最先获取 中序就是当前节点在中间获取 后序就是当前节点在最后获取
        ——————————————————————————————————————————————————————————————————————
        二叉查找树的弊端:
        7 10 11 12 13 按照二叉查找数
        首先存7作为根节点 然后10放11后面
         大概的样子就是
                7
                 10
                   11
                     12
                      13
         现在这一棵二叉树似乎变成了一个单向链表 但是此时两边的树是不一样长的
         这样的树是有问题的 这样的查询效率过低了 如果我要查询数据13 岂不是要从根节点开始
         找5次才能找到13
         关键点:要提高查询效率 左右的高度要差不多长的树->
         这里我们就引入了一个新的二叉树 这样的二叉树是基于二叉查找树的
         增加一条新的规则:任意节点左右子树的(高度差)不超过1
         (这点很容易迷惑 任意的意思是从上往下的每一个节点)
         不能被根节点的左子树右子树的高度满足条件迷惑
         当你看根节点左右子节点的时候 就会发现可能子节点不满足这个条件
         ————————————————————————————————————————————————————————————————————————
         平衡二叉树的旋转机制:
         规则1:左旋(前提条件:添加了一个节点后,该树不是一颗平衡二叉树)
         规则2:右旋(当添加一个节点之后,该节点不是一棵平衡二叉树)
         研究左旋转规则:
         1.确定支点:从添加的节点开始,不断地朝父节点寻找不平衡点
         2.将根节点的右边往左边拉
         3.原先的右节点变成新的父节点,并且把多余的左子节点出让 给已经降级的根节点当右节点
         研究右旋规则:
         1.发现添加节点后,平衡被破坏了,从被添加的节点开始向上找第一个不平衡的点
         2.找到第一个不平衡的点作为支点
         3.原先的左子节点变成新的父节点,并且把多余的右子节点出让 给已经降级的根节点当左节点
——————————————————————————————————————————————————————————————————————————————
         平衡二叉树需要旋转的四种情况
         1.左左:根节点的左子树的左子树不平衡,导致二叉树不平衡->一次右旋就可以
         2.左右:根节点的左子树的右子树不平衡,导致二叉树不平衡->一次局部左旋和整体一次右旋
         ps:这里很有意思 就是要先把左右问题变成左左问题 再转化为左左的问题
         3.右右:就是根节点的右子树的右子树不平衡,导致二叉树不平衡->一次左旋就可以
         4.右左:根节点的右子树的左子树不平衡,导致二叉树不平衡->一次局部右旋和整体一次左
 

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

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

相关文章

windows 如何卸载证书

1、windows r 2、输入 certmgr.msc 3、进入证书管理&#xff0c;选择个人 4、选择个人---找到要删除的证书&#xff0c;删除 就可以了。

每日一练:“五人分鱼”问题

1. 题目 五人分鱼问题&#xff1a;A、B、C、D、E 五人在某天夜里合伙去捕鱼&#xff0c;到第二天凌晨时都疲惫不堪&#xff0c;于是各自找地方睡觉。   日上三杆&#xff0c;A 第一个醒来&#xff0c;他将鱼分为五份&#xff0c;把多余的一条鱼扔掉&#xff0c;拿走自己的一份…

LeetCode Hot100 31.下一个排列

题目&#xff1a; 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如&#xff0c;arr [1,2,3] &#xff0c;以下这些都可以视作 arr 的排列&#xff1a;[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列…

软件测试-软件缺陷有哪些,一文贯彻到底

软件缺陷 软件缺陷&#xff1a;又称之为“Bug”。即计算机软件或程序中存在的某种破坏正常运行能力的问题、错误&#xff0c;或者隐藏的功能缺陷。 表现形式A 软件没有实现产品规格说明书所要求的功能模块。 表现形式B 软件中出现了产品规格说明指明不应该出现的错误。 表现…

WordPress:解决xmlrpc.php被扫描爆破的风险

使用WordPress的朋友都知道&#xff0c;一些【垃圾渣渣】会利用xmlrpc.php文件来进行攻击&#xff0c;绕过WP后台错误登录次数限制进行爆破。虽然密码复杂的极难爆破&#xff0c;但及其占用服务器资源。 方法一、利用宝塔防火墙&#xff08;收费版&#xff09; 一般可以直接使…

代码随想录算法训练营第五十二天【动态规划part13】 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

300.最长递增子序列 题目链接 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 求解思路 动规五部曲 1.dp数组及其下标定义&#xff1a; dp[i]表示包括i以前的以nums[i]结尾的最长递增子序列的长度 2.状态转移方程&#xff1a; 位置i的最长升序…

如何解决SSL证书部署后未生效或网站显示不安全

本文介绍SSL证书部署后未生效或网站显示不安全的排查方法。 浏览器提示“您与此网站建立的连接不安全” 浏览器提示“无法访问此页面” 浏览器提示“这可能是因为站点使用过期或者不全的TLS安全设置” 浏览器提示“此页面上部分内容不安全&#xff08;例如图像&#xff09;”…

网络类型解析(基础):探索通信世界的多样面貌

在当今数字化时代&#xff0c;网络已经成为人们生活和工作中不可或缺的一部分。从个人设备之间的直接通信到全球范围的数据传输&#xff0c;不同类型的网络为我们提供了多种连接方式和通信选择。透过对这些网络类型的解析&#xff0c;我们将更好地理解它们的特点、优势和适用场…

Excel导入操作

<template><el-dialogwidth"500px"title"员工导入":visible"showExcelDialog"close"$emit(update:showExcelDialog, false)"><el-row type"flex" justify"center"><div class"upload-e…

C++stack

目录 1.什么是stack 2.容器适配器 3.stack的使用 top push pop 4.模拟实现stack 1.什么是stack 1. stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其删除只能从容器的一端进行 元素的插入与提取操作。(后进先出) 2. stack是作为容…

git的版本控制流程

1、git是一款版本控制工具 例如我们常用的淘宝&#xff0c;每次升级&#xff0c;版本号就会加一。那么我们怎么控制版本号呢&#xff1f; --使用git。 2、最常使用的git指令 git add . 暂存 git commit -m"***" 提交到本地 git pull 将远程仓库代码下拉到本地 git …

Python知识碎片补充【侯小啾python领航班系列(十四)】

Python知识碎片补充【侯小啾python领航班系列(十四)】 大家好,我是博主侯小啾, 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ�…

c#学习相关系列之as和is的相关用法

一、子类和父类的关系 public class Program{static void Main(string[] args){Animal animal new Dog();// Dog dog (Dog)new Animal(); 编译成功&#xff0c;运行报错Dog dog (Dog)animal;Dog dog new Dog();Animal animal dog; //等价于Animal animal new Dog();}}pub…

应用于智慧社区的AI边缘计算盒子+AI算法软硬一体化方案

据统计&#xff0c;全国大约有45W个小区&#xff0c;监控高空抛物、治理乱扔垃圾、人员管理、烟火检测、占道、人流量检测、车型检测等&#xff1b;营造社区安全等需求跟每一个参与者息息相关&#xff0c;据法院公开资料显示&#xff0c;每年有1000宗以上跟高空抛物有关的各类案…

0X04

看到一道有趣的misc题 misc签到题 打开后啥都没有&#xff0c;全选后发现每一行有空格&#xff0c;数了一行发现空格数量转ascil码后是f&#xff0c;猜测都如此&#xff0c; 后面就可以交个脚本了&#xff0c;统计之后转换成ascii from Crypto.Util.number import long_to_b…

【Linux--进程控制】

目录 一、进程等待1.1进程等待方法1.2获取子进程status 二、进程替换2.1单进程版本--最简单得程序替换2.2 进程替换得原理2.3 多进程版本--验证各种程序替换接口2.4 总结 一、进程等待 1.1进程等待方法 问题1&#xff1a;进程等待是什么&#xff1f; 通过系统调用wait/waitpi…

算法:笛卡尔平面坐标系上,若干连接点形成线,剔除距离小于阈值的点,Kotlin

算法&#xff1a;笛卡尔平面坐标系上&#xff0c;若干连接点形成线&#xff0c;剔除距离小于阈值的点&#xff0c;Kotlin const val THRESHOLD 0.6f //距离小于这个点将被剔除。data class Point(val x: Float, val y: Float)fun removeNearbyPoint(points: List<Point>…

【数电笔记】逻辑代数的基本定律、常用公式

说明&#xff1a; 笔记配套视频来源&#xff1a;B站 逻辑代数的基本定律 1. 常量间的运算 2. 逻辑变量与常量的运算 3. 与普通代数相似的定律 4. 摩根定律&#xff08;反演律&#xff09; 5. 等式证明方法例题 逻辑代数的常用公式 1. 吸收律 2. 冗余律 3. 示例应用 4. 关于异…

conda 安装指定Version的指定Build

入下图&#xff0c;我想装cudnn的7.6.5的指定Build版本cuda10.0_0 应该使用如下命令&#xff1a; mamba install cudnn7.6.5cuda10.0_0 没有mamba用conda install也可以

快手获客技巧:轻松获取高转化率的潜在客户!

**一、引言** 随着互联网的发展&#xff0c;越来越多的企业开始关注短视频平台&#xff0c;尤其是快手。作为中国最大的短视频平台之一&#xff0c;快手拥有庞大的用户群体和丰富的视频内容。通过掌握快手获客技巧&#xff0c;企业不仅可以获取更多潜在客户&#xff0c;还能提高…