数据结构

一、栈

先进后出

二、队列

先进先出

三、数组

查询快,增加修改慢

四、链表

查询慢,增加修改慢

五、二叉树

节点:

查找二叉树

二叉查找树的特点

  • 二叉查找树,又称二叉排序树或者二叉搜索树

  • 每一个节点上最多有两个子节点

  • 左子树上所有节点的值都小于根节点的值

  • 右子树上所有节点的值都大于根节点的值

二叉查找树添加节点规则

  • 小的存左边

  • 大的存右边

  • 一样的不存

数据结构(二叉树)遍历方式

  1. 前序遍历:当前节点,左子节点,右子结点
  2. 中序遍历:左子节点,当前节点,右子结点
  3. 后序遍历:左子节点,右子结点,当前节点
  4. 层序遍历:一层一层的去遍历

平衡二叉树

特点

  • 二叉树左右两个子树的高度差不超过1

  • 任意节点的左右两个子树都是一颗平衡二叉树

平衡二叉树旋转

  • 旋转触发时机

    • 当添加一个节点之后,该树不再是一颗平衡二叉树

  • 左旋

    • 确定支点:从添加的节点开始,不断的往父节点找不平衡的节点

    以不平衡的点作为支点
    将根节点的右侧往左拉
    原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点

右旋

  • 确定支点:从添加的节点开始,不断的往父节点找不平衡的节点

以不平衡的点作为支点
就是将根节点的左侧往右拉
原先的左子节点变成新的父节点,并把多余的右子节点出让,给已经降级的根节点当左子节点

平衡二叉树旋转的四种情况

左左

  • 左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡

  • 如何旋转: 直接对整体进行右旋即可

左右

  • 左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡

  • 如何旋转: 先在左子树对应的节点位置进行左旋,再对整体进行右旋

右右

  • 右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡

  • 如何旋转: 直接对整体进行左旋即可

右左

  • 右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡

  • 如何旋转: 先在右子树对应的节点位置进行右旋,再对整体进行左旋

红黑树

红黑树的特点

红黑树的增删改查性能都很好

  • 平衡二叉B树

  • 每一个节点可以是红或者黑

  • 红黑树不是高度平衡的,它的平衡是通过"自己的红黑规则"进行实现的

节点

红黑规则

  1. 每一个节点是红色的,或者是黑色的
  2. 根节点必须是黑色
  3. 叶节点是黑色的
  4. 两个红色节点不能相连
  5. 任意节点到所有后代叶节点的简单路径上,黑色节点数量相同;

红黑树结构图

红黑树添加节点的默认颜色

  • 添加节点时,默认为红色,效率高

红黑树添加节点后如何保持红黑规则

  • 根节点位置

    • 直接变为黑色

  • 非根节点位置

    • 父节点为黑色

      • 不需要任何操作,默认红色即可

    • 父节点为红色

      • 叔叔节点为红色

        1. 将"父节点"设为黑色,将"叔叔节点"设为黑色

        2. 将"祖父节点"设为红色

        3. 如果"祖父节点"为根节点,则将根节点再次变成黑色

      • 叔叔节点为黑色

        1. 将"父节点"设为黑色

        2. 将"祖父节点"设为红色

        3. 以"祖父节点"为支点进行旋转

实现代码

public class RBTree {class Node {int val, color;Node left, right;}
//    使用NIL节点来充当叶节点Node NIL;Node root;public RBTree() {NIL = new Node();NIL.val = -1;NIL.color = 1;NIL.left = NIL.right = NIL;root = NIL;}// 创建节点private Node getNewNode(int val) {Node p = new Node();p.val = val;p.color = 0;p.left = p.right = NIL;return p;}//判断有没有红色孩子private boolean has_red_child(Node tree) {return tree.left.color == 0 || tree.right.color == 0;}//左旋private Node left_rotate(Node tree) {Node temp = tree.right;tree.right = temp.left;temp.left = tree;return temp;}//右旋private Node right_rotate(Node tree) {Node temp = tree.left;tree.left = temp.right;temp.right = tree;return temp;}//寻找前驱private Node preNode(Node tree) {Node p = tree.left;while (p.right != null) {p = p.right;}return p;}//删除public void erase(int val) {root = erase(root, val);}private Node erase(Node tree, int val) {tree = __erase(tree, val);tree.color = 1;return tree;}private Node __erase(Node tree, int val) {if (tree == NIL) return tree;if (val < tree.val) {tree.left = __erase(tree.left, val);} else if (val > tree.val) {tree.right = __erase(tree.right, val);} else {if (tree.left == NIL || tree.right == NIL) {Node temp = tree.left == NIL ? tree.right : tree.left;temp.color += tree.color;tree = temp;return tree;} else {Node temp = preNode(tree);tree.val = temp.val;tree.left = __erase(tree.left, temp.val);}}return erase_maintion(tree);}//删除调整private Node erase_maintion(Node tree) {if (tree.left.color != 2 && tree.right.color != 2) return tree;
//        兄弟为红,旋转树,新根节点转为黑,原根节点转为红if (has_red_child(tree)) {int flag = 0;tree.color = 0;if (tree.left.color == 0) {tree = right_rotate(tree);flag = 1;} else {tree = left_rotate(tree);}tree.color = 1;if (flag == 1) tree.right = erase_maintion(tree.right);else tree.left = erase_maintion(tree.left);return tree;}
//        兄弟为黑色并且没有红色子节点,子节点减黑,根节点加黑if (tree.left.color == 1 && !has_red_child(tree.left)|| tree.right.color == 1 && !has_red_child(tree.right)) {tree.color += 1;tree.left.color -= 1;tree.right.color -= 1;return tree;}
//        兄弟节点为黑并且有红色子节点
//            |-- 左子树为黑色
//              |-- 左子树的右子树为红色且左子树节点为黑 LR
//                  |-- 子树小左旋,新节点转黑,原节点转红,进入LL形态
//              |-- 左子树的左子树为红色 LL
//                  |-- 整树右旋,新节点改为原根节点的颜色,原根节点已经新叔叔节点转为黑色
//            |-- 右子树为黑色
//              |-- 右子树的左子树为红色且右子树节点为黑 RL
//                  |-- 子树小右旋,新节点转黑,原节点转红,进入RR形态
//              |-- 右子树的右子树为红色 RR
//                  |-- 整树左旋,新节点改为原根节点的颜色,原根节点已经新叔叔节点转为黑色if (tree.left.color == 1) {tree.right.color = 1;if (tree.left.left.color != 0) {tree.left.color = 0;tree.left = left_rotate(tree.left);tree.left.color = 1;}tree.left.color = tree.color;tree = right_rotate(tree);} else {tree.left.color = 1;if (tree.right.right.color != 0) {tree.right.color = 0;tree.right = right_rotate(tree.right);tree.right.color = 1;}tree.right.color = tree.color;tree = left_rotate(tree);}tree.left.color = 1;tree.right.color = 1;return tree;}//添加public void insert(int val) {root = insert(root, val);}private Node insert(Node tree, int val) {tree = __insert(tree, val);tree.color = 1;return tree;}private Node __insert(Node tree, int val) {if (tree == NIL) {return getNewNode(val);}if (val < tree.val) {tree.left = __insert(tree.left, val);} else if (val > tree.val) {tree.right = __insert(tree.right, val);}return insert_maintain(tree);}//添加调整private Node insert_maintain(Node tree) {if (!has_red_child(tree)) return tree;//节点双红if (tree.left.color == 0 && tree.right.color == 0) {if (!has_red_child(tree.left) && !has_red_child(tree.right)) return tree;tree.color = 0;tree.left.color = tree.right.color = 1;return tree;}if (tree.left.color == 0 && !has_red_child(tree.left)) return tree;if (tree.right.color == 0 && !has_red_child(tree.right)) return tree;// 左子树失衡if (tree.left.color == 0) {if (tree.left.right.color == 0) {tree.left = left_rotate(tree.left);}tree = right_rotate(tree);} else {if (tree.right.left.color == 0) {tree.right = right_rotate(tree.right);}tree = left_rotate(tree);}tree.color = 0;tree.left.color = tree.right.color = 1;return tree;}//打印输出public void preorder() {preorder(root, root.val, 0);}private void preorder(Node tree, int val, int flag) {if (tree == NIL) return;if (flag == 0) {System.out.printf("%d is root, color is %s\n", val, tree.color == 0 ? "red" : "black");} else {System.out.printf("%d is %d's %s child, color is %s\n", tree.val, val, flag == 1 ? "right" : "left", tree.color == 0 ? "red" : "black");}preorder(tree.left, tree.val, -1);preorder(tree.right, tree.val, 1);}
}

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

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

相关文章

算法---动态规划练习-5(下降路径最小和)

下降路径最小和 1. 题目解析2. 讲解算法原理方法一方法二 3. 编写代码法一法二 1. 题目解析 题目地址&#xff1a;点这里 2. 讲解算法原理 方法一 首先&#xff0c;通过matrix的大小确定矩阵的行数m和列数n。 创建一个大小为(m1) (n2)的二维动态规划数组dp&#xff0c;其中d…

就业班 第二阶段 2401--3.26 day6 Shell初识 连接vscode

远程连接vs_code可能出现的问题 C:\Users\41703\.ssh 验证远程主机的身份&#xff0c;如果连不上vscode&#xff0c;可以尝试删除这里面的公钥代码。 重新安装那个扩展&#xff0c;排除扩展本身的问题 谁连过我&#xff0c;并操作了什么 curl https://gitea.beyourself.org.c…

Django路由

Router介绍 在实际开发过程中&#xff0c;一个Django项目会包含很多的app,这时候如果我们只在主路由里进行配置就会显得杂乱无章&#xff0c;所以通常会在每个app里&#xff0c;创建各自的urls.py路由模块&#xff0c;然后从根路由出发&#xff0c;将app所属的url请求&#xff…

Spring Boot | Spring Boot的“核心配置“与“注解“

目录: Spring Boot的核心配置与注解 &#xff1a;1. 全局配置文件 ( application.properties / application.yaml&#xff1a;创建项目时候自动生成&#xff0c;其会被“自动导入”到“程序”中 )application.properties配置文件application.yaml 配置文件 (推荐使用)当value值…

PSA制氧装置的工作原理及应用解析

PSA制氧装置&#xff0c;即变压吸附制氧装置&#xff0c;是一种广泛应用于工业生产与其他领域的重要设备。该装置基于吸附剂在不同压力下对气体分子吸附能力的差异&#xff0c;通过周期性压力变化来实现氧气的分离与提纯。 工作原理 PSA制氧装置的工作原理主要基于物理吸附与解…

【ESP32S3 Sense接入百度在线语音识别】

视频地址&#xff1a; ESP32S3 Sense接入百度在线语音识别 1. 前言 使用Seeed XIAO ESP32S3 Sense开发板接入百度智能云实现在线语音识别。自带麦克风模块用做语音输入&#xff0c;通过串口发送字符“1”来控制数据的采集和上传。 步骤概括    (1) 在百度云控制端选择“语音…

JVM(三)——字节码技术

三、字节码技术 1、类文件结构 一个简单的 HelloWorld.java package com.mysite.jvm.t5; // HelloWorld 示例 public class HelloWorld {public static void main(String[] args) {System.out.println("hello world");} }执行 javac -parameters -d . HellowWorld.…

会员中心微服务

文章目录 1.环境配置1.创建会员中心模块2.检查父子模块的pom.xml1.父模块注意&#xff1a;如果父模块中的依赖显示not found&#xff0c;原因是子模块并没有引用&#xff0c;不用在意 2.子模块 3.pom.xml 引入相关依赖&#xff08;别忘记刷新maven&#xff09;4.application.ym…

机器学习预测气候变化对产量的影响

通过机器学习预测作物产量 今天分享一篇文献解读&#xff0c;将围绕论文《结合机器学习和环境变量约束气候变化下作物产量变化预测的不确定性》展开,该研究通过将动态线性模型(DLM)和随机森林机器学习模型(RF)分别与9个全球网格作物模型(GGCM)集成来整合和克服这两种建模框架的…

webpack练习之手写loader

手写一个style-loader来把样式文件插入head里面&#xff0c;准备工作 vue webpack就自己弄了&#xff0c;webpack的一些配置也自己配置好 一、创建index.css文件 .box{width: 100px;height: 100px;background-color: red; }然后在vue的main.js文件中引入它 二、创建自定义l…

jmeter二次开发发送java请求_保姆级教程!!!

一、引言 JMeter是Apache基金会开发的一款开源性能测试工具,广泛应用于软件性能测试领域。它能够模拟多线程并发用户对应用程序进行压力测试,以评估应用程序的性能和稳定性。然而,在实际使用过程中,用户可能会遇到需要发送Java请求的场景,例如测试Java Web应用程序或其他…

【Monero】Wallet RPC | Wallet CLI | 门罗币命令行查询余额、种子、地址等命令方法教程

ubuntu22.04 首先在运行daemon&#xff0c;详细安装运行教程可参考&#xff1a;The Monero daemon (monerod) ./monerodWallet CLI run ./monero-wallet-cli如果还没有钱包就根据提示创建钱包即可 输入密码 查询余额 balance查询种子 seed其他可执行命令操作&#xff1…

拌合楼管理软件开发(十一) 海康威视车牌识别摄像头安装调试,总算是跑通了。

前言&#xff1a;总算是调测通了 话接上回&#xff0c;车牌识别摄像头买回来了&#xff0c;卡在电源上了&#xff0c;今天抽时间把电源问题解决了&#xff0c;开始代码正式的调测。一切还算顺利了&#xff0c;没有再碰到打脸的事情了。 一、电源接线&#xff1a; 如同前面预想的…

selenium元素定位--xpath定位--层级与逻辑组合定位

其他元素非唯一时&#xff0c;又不想用xpath绝对定位时&#xff0c;需要用到层级与逻辑定位. 一、层级属性结合定位&#xff1a; 遇到元素没有class、name、id等或属性动态变化情况时&#xff0c;可以找父节点元素&#xff0c;父级节点没有id时&#xff0c;可以继续往上找id&…

linux在使用重定向写入文件时(使用标准C库函数时)使处理信号异常(延时)--问题分析

linux在使用重定向写入文件时(使用标准C库函数时)使处理信号异常(延时)–问题分析 在使用alarm函数进行序号处理测试的时候发现如果把输出重定向到文件里面会导致信号的处理出现严重的延迟(ubuntu18) #include <stdio.h> #include <stdlib.h> #include <unist…

UE5 C++ 3D血条 响应人物受伤 案例

一.3Dwidget 1.创建C Userwidget的 MyHealthWidget&#xff0c;声明当前血量和最大血量 UCLASS() class PRACTICEC_API UMyHealthWidget : public UUserWidget {GENERATED_BODY() public:UPROPERTY(EditAnywhere,BlueprintReadWrite,Category "MyWidget")float C…

Ubuntu连不上外网的问题—ping不通baidu.com

一、问题 虚拟机不能联网&#xff0c;ping百度时候出现这个问题 book100ask:~$ ping www.baidu.com ping: www.baidu.com: Name or service not known 二、解决办法 首先&#xff0c;定位问题&#xff0c;再问我出现的问题中&#xff0c;认为是NAT设置的问题&#xff0c;只要…

【Frida】【Android】02_JAVA层HOOK

&#x1f6eb; 系列文章导航 【Frida】【Android】01_手把手教你环境搭建 https://blog.csdn.net/kinghzking/article/details/136986950【Frida】【Android】02_JAVA层HOOK https://blog.csdn.net/kinghzking/article/details/137008446【Frida】【Android】03_RPC https://bl…

matlab编译成jar包

1、输入deploytool命令 2、选择Library Compiler 3、配置打包 4、有效文件 5、java函数调用 package com.beescloud.frame.matlab;import com.mathworks.toolbox.javabuilder.MWException; import test.Class1;public class MatlabTest {public static void main(String[] arg…

PanTools v1.0.17 多网盘批量管理 批量分享、转存、复制...

软件介绍 一款针对多个热门网盘的文件管理、批量分享、批量转存、批量复制、批量重命名、批量链接检测、跨账号移动文件、多账号文件搜索等&#xff0c;支持不同网盘的不同账号的资源文件操作。适用于网站站长、资源爱好者等&#xff0c;对于管理名下具有多个网盘多个账号具有…