红黑树(R-B Tree, 全称 Red-Black Tree)是一种特殊的二叉查找树, 其中每个节点都有颜色, 红色或者黑色。
红黑树
红黑树(平衡的排序二叉树)，满足以下性质：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点
根据性质5，我们得出：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长
红黑树的关键性质：内部保证有序，旋转开销小，整体相对平衡。
主要是 Java 中的 TreeMap 和 TreeSet. jdk1.8 之后, HashMap 的table中的链表长度大于8的时候也是用红黑树。
时间复杂度: 查找, 插入, 删除都可以在 O(log n) 内完成. 且节点数为 n 的数高度最大为 2log(n+1)。
一、红黑树及应用 1.1 红黑树 红黑树(R-B Tree, 全称 Red-Black Tree)是一种特殊的二叉...
数据结构 & 算法 LeetCode 剑指 Offer 编程之美 UIKit 精选 UITableView 整洁的...
原文精选：哈希指针是一种数据结构，这种数据结构在我们即将讨论的很多系统中都很有用。简单来说，哈希指针是一个指向数据...
几个重要问题类型 排序 查找 字符串处理 图问题 组合问题 几何问题 数值问题 几种基本数据结构 线性数据结构 图...
一、简述 Mybatis 的插件运行原理，以及如何编写一个插件？ 1、Mybatis 仅可以编写针对 Parame...
一、&和&&的区别 &是位运算符，表示按位与运算，&&是逻辑运算符，表示逻辑与（and） 二、Collection...
一、一张表，里面有 ID 自增主键，当 insert 了 17 条记录之后，删除了第 15,16,17 条记录，再...
一、Spring Boot 的核心注解是哪个？它主要由哪几个注解组成的？ 启动类上面的注解是@SpringBoot...
一、内存模型以及分区，需要详细到每个区放什么 JVM 分为堆区、栈区、方法区、本地方法栈、程序计数器 方法区：主要...
原文链接：https://hackernoon.com/50-data-structure-and-algorit...
本文标题：问题精选-数据结构
本文链接：https://www.haomeiwen.com/subject/mwjurltx.html
网友评论