数据结构
一、栈
先进后出
二、队列
先进先出
三、数组
查询快,增加修改慢
四、链表
查询慢,增加修改慢
五、二叉树
节点:
查找二叉树
二叉查找树的特点
-
二叉查找树,又称二叉排序树或者二叉搜索树
-
每一个节点上最多有两个子节点
-
左子树上所有节点的值都小于根节点的值
-
右子树上所有节点的值都大于根节点的值
二叉查找树添加节点规则
-
小的存左边
-
大的存右边
-
一样的不存
数据结构(二叉树)遍历方式
- 前序遍历:当前节点,左子节点,右子结点
- 中序遍历:左子节点,当前节点,右子结点
- 后序遍历:左子节点,右子结点,当前节点
- 层序遍历:一层一层的去遍历
平衡二叉树
特点
-
二叉树左右两个子树的高度差不超过1
-
任意节点的左右两个子树都是一颗平衡二叉树
平衡二叉树旋转
-
旋转触发时机
-
当添加一个节点之后,该树不再是一颗平衡二叉树
-
-
左旋
-
确定支点:从添加的节点开始,不断的往父节点找不平衡的节点
以不平衡的点作为支点
将根节点的右侧往左拉
原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点 -
右旋
-
确定支点:从添加的节点开始,不断的往父节点找不平衡的节点
以不平衡的点作为支点
就是将根节点的左侧往右拉
原先的左子节点变成新的父节点,并把多余的右子节点出让,给已经降级的根节点当左子节点
平衡二叉树旋转的四种情况
左左
-
左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡
-
如何旋转: 直接对整体进行右旋即可
左右
-
左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡
-
如何旋转: 先在左子树对应的节点位置进行左旋,再对整体进行右旋
右右
-
右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡
-
如何旋转: 直接对整体进行左旋即可
右左
-
右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡
-
如何旋转: 先在右子树对应的节点位置进行右旋,再对整体进行左旋
红黑树
红黑树的特点
红黑树的增删改查性能都很好
-
平衡二叉B树
-
每一个节点可以是红或者黑
-
红黑树不是高度平衡的,它的平衡是通过"自己的红黑规则"进行实现的
节点
红黑规则
- 每一个节点是红色的,或者是黑色的
- 根节点必须是黑色
- 叶节点是黑色的
- 两个红色节点不能相连
- 任意节点到所有后代叶节点的简单路径上,黑色节点数量相同;
红黑树结构图
红黑树添加节点的默认颜色
-
添加节点时,默认为红色,效率高
红黑树添加节点后如何保持红黑规则
-
根节点位置
-
直接变为黑色
-
-
非根节点位置
-
父节点为黑色
-
不需要任何操作,默认红色即可
-
-
父节点为红色
-
叔叔节点为红色
-
将"父节点"设为黑色,将"叔叔节点"设为黑色
-
将"祖父节点"设为红色
-
如果"祖父节点"为根节点,则将根节点再次变成黑色
-
-
叔叔节点为黑色
-
将"父节点"设为黑色
-
将"祖父节点"设为红色
-
以"祖父节点"为支点进行旋转
-
-
-
实现代码
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);}
}
相关文章:

数据结构
一、栈 先进后出 二、队列 先进先出 三、数组 查询快,增加修改慢 四、链表 查询慢,增加修改慢 五、二叉树 节点: 查找二叉树 二叉查找树的特点 二叉查找树,又称二叉排序树或者二叉搜索树 每一个节点上最多有两个子节点 左子树上所…...

动态规划相关题目
文章目录 1.动态规划理论基础2.斐波那契数3.爬楼梯4.使用最小花费爬楼梯5.不同路径6.不同路径 II7. 整数拆分8. 不同的二叉搜索树 1.动态规划理论基础 1.1 什么是动态规划? 动态规划,英文:Dynamic Programming,简称DP,如果某一…...

iOS - Runtime - Class-方法缓存(cache_t)
文章目录 iOS - Runtime - Class-方法缓存(cache_t)1. 散列表的存取值 iOS - Runtime - Class-方法缓存(cache_t) Class内部结构中有个方法缓存(cache_t),用散列表(哈希表)来缓存曾经调用过的方法,可以提高…...

2014年认证杯SPSSPRO杯数学建模B题(第一阶段)位图的处理算法全过程文档及程序
2014年认证杯SPSSPRO杯数学建模 B题 位图的处理算法 原题再现: 图形(或图像)在计算机里主要有两种存储和表示方法。矢量图是使用点、直线或多边形等基于数学方程的几何对象来描述图形,位图则使用像素来描述图像。一般来说&#…...

【物联网项目】基于ESP8266的家庭灯光与火情智能监测系统——文末完整工程资料源码
目录 系统介绍 硬件配置 硬件连接图 系统分析与总体设计 系统硬件设计 ESP8266 WIFI开发板 人体红外传感器模块 光敏电阻传感器模块 火焰传感器模块 可燃气体传感器模块 温湿度传感器模块 OLED显示屏模块 系统软件设计 温湿度检测模块 报警模块 OLED显示模块 …...
Unity中控制帧率的思考
如何控制帧率: 在Unity中,你可以通过设置Application.targetFrameRate来限制帧率。 例如,如果你想将帧率限制为16帧, 你可以在你的代码中添加以下行: Application.targetFrameRate 16; 通常,这行代码会放在…...
阿里云子域名配置,且不带端口访问
进入阿里云控制台,创建一个SSL证书 # 域名名称child.domain.com创建完成后,将返回主机记录以及记录值,保存好,用于下一步使用 创建DNS解析 创建DNS的TXT类型解析 选择记录类型:TXT 填写主机记录:_dnsa…...
C#-ConcurrentDictionary用于多线程并发字典
ConcurrentDictionary 是 .NET Framework 中用于多线程并发操作的一种线程安全的字典集合类。它提供了一种在多个线程同时访问和修改字典时保持数据一致性的机制。 以下是 ConcurrentDictionary 类的一些重要特性和用法: 线程安全性:ConcurrentDictiona…...

深入探讨多线程编程:从0-1为您解释多线程(下)
文章目录 6. 死锁6.1 死锁原因 6.2 避免死锁的方法加锁顺序一致性。超时机制。死锁检测和解除机制。 6. 死锁 6.1 死锁 原因 系统资源的竞争:(产生环路)当系统中供多个进程共享的资源数量不足以满足进程的需要时,会引起进程对2…...

深度学习pytorch——减少过拟合的几种方法(持续更新)
1、增加数据集 2、正则化(Regularization) 正则化:得到一个更加简单的模型的方法。 以一个多项式为例: 随着最高次的增加,会得到一个更加复杂模型,模型越复杂就会更好的拟合输入数据的模型(图-1)&#…...

排序第五篇 归并排序
一 简介 归并排序(Merge Sort) 的基本思想是: 首先将待排序文件看成 n n n 个长度为1的有序子文件, 把这些子文件两两归并, 得到 n 2 \frac{n}{2} 2n 个长度为 2 的有序子文件; 然后再把这 n 2 \frac{n}{2} 2n 个有序的子…...

【Win】使用PowerShell和Webhooks轻松发送消息至Microsoft Teams
Microsoft Teams是一款由微软开发的团队协作和通讯工具。如果您对这个名字还不太熟悉,那么现在就是一个了解它的好时机。微软将Teams定位为其之前Skype for Business解决方案的继任者,并且它也提供了与其他基于频道的通讯应用程序(例如Slack、…...

ESCTF-OSINT赛题WP
这你做不出来?check ESCTF{湖北大学_嘉会园食堂} 这个识图可以发现是 淡水渔人码头 但是 osint 你要发现所有信息 聊天记录说国外 同时 提示给了美国 你综合搜索 美国 渔人码头 在美国旧金山的渔人码头(英语:Fisherman’s Wharf)是一个著名旅…...
2024蓝桥杯省赛保奖突击班-Day2-前缀和、差分、尺取_笔记_练习题解
3月25日-课堂笔记 前缀和预处理 O ( n ) \mathcal{O}(n) O(n) s[1] a[1]; for(int i 2; i < n; i)s[i] s[i - 1] a[i];利用前缀和查询区间和 O ( 1 ) O(1) O(1) long long calc(int l, int r) {return l 1 ? s[r] : s[r] - s[l - 1]; }差分序列的求法 c[1] a[…...

C++基础之虚函数(十七)
一.什么是多态 多态是在有继承关系的类中,调用同一个指令(函数),不同对象会有不同行为。 二.什么是虚函数 概念:首先虚函数是存在于类的成员函数中,通过virtual关键字修饰的成员函数叫虚函数。 性质&am…...
快速入门Kotlin①基本语法
前言 23年底读了一遍“Kotlin官方文档”,官方文档大而全,阅读下来,大有裨益。 此系列文章的目的是记录学习进程,同时,若能让读者迅速掌握重点内容并快速上手,那就再好不过了。 函数 带有两个 Int 参数、…...

【理解指针(四)】
文章目录 一、指针数组二、指针数组来模拟二维数组三、字符指针变量注意: 字符串的例子(曾经的一道笔试题) 四、数组指针变量1、什么是数组指针变量2、数组指针怎么初始化 五、二维数组传参的本质六、函数指针1、什么是函数指针变量2、函数的…...

Ribbon简介
目录 一 、概念介绍 1、Ribbon是什么 2、认识负载均衡 2.1 服务器端的负载均衡 2.2 客户端的负载均衡 3、Ribbon工作原理 4、Ribbon的主要组件 IClientConfig ServerList ServerListFilter IRule Iping ILoadBalancer ServerListUpdater 5、Ribbon支持…...

【感悟《剑指offer》典型编程题的极练之路】02字符串篇!
个人主页:秋风起,再归来~ 文章所属专栏:《剑指offer》典型编程题的极练之路 个人格言:悟已往之不谏,知来者犹可追 克心守己,…...
通过 Docker 实现国产数据库 OpenGauss 开发环境搭建
通过 Docker 实现国产数据库 OpenGauss 开发环境搭建 一 前置准备 2.1 下载镜像 docker pull enmotech/opengauss:5.0.1构建镜像的 Dockerfile,方便后期实现个性化定制: FROM ubuntu:22.04 as builderARG TARGETARCHWORKDIR /warehouseRUN set -eux;…...

通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...