目录 树 二叉树 如何表示（或者存储）一棵二叉树 二叉树的遍历 二叉查找树（Binary Search Tree） 二叉查找树的时间复杂度分析 二叉查找树和散列表 红黑树 平衡二叉查找树 如何定义一棵“...“层数”跟深度的计算类似，不过，计数起点是 1，也就是说根节点的位于第 1 层。 二叉树 如何表示（或者存储）一棵二叉树 一种是基于指针或者引用的二叉链式存储法 一种是基于数组的顺序存储法。...既然这样，现在问题就转变成另外一个了，也就是，如何求一棵包含 n 个节点的完全二叉树的高度？ 树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示。...这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。 AVL树不存在变色的问题，只有左旋转、右旋转这两种操作。 如何定义一棵“红黑树”？...从上面我画的红黑树的例子和定义看，在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。
红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。...没有键值相等的节点（no duplicate nodes）。 因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。...红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。...但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？ 这就引出了红黑树的5个性质： 1.每个结点要么是红的要么是黑的。 2.根结点是黑的。...正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的: 红黑树的查找、插入、删除的时间复杂度最坏为O(log n) 这一结论成立的原因。
比如在链表上添加一个数据域来记录结点的位置、在一棵二叉搜索树上添加一个指针域来记录结点的后继指针，等等。 本章介绍两种通过扩张红黑树构造出的数据结构，一种是动态顺序统计树；另一种是区间树。...二、扩张的两种数据结构 简单总结下通过红黑树扩张的两种数据结构：动态顺序统计树和区间树。 动态顺序统计树在原红黑树的基础上增加一个数据域 x.size，其等于 x 左右孩子的节点数。...通过这一小小的改造，就可以利用红黑树解第9章介绍的顺序统计，其所有操作的时间复杂度降到O(lgn)。...对于改造的动态顺序统计数，有两个比较重要的函数：一就是求第 k 小的数:Select(x, k); 二是求节点 x 的排名：Rank(T, x)，这两个操作都能在O(lgn)内完成。...如下是一棵动态顺序统计树： ? 区间树则是对红黑树扩张以便支持由区间构成的动态集合操作，红黑树用到的关键字值是区间树的区间左端点值。以下是一个区间树及其所表示的区间： ?
红色内部结点与黑色内部结点的比值可以表示为 (\frac{2^{d+1} - k}{k})。...需要注意的是，红黑树的构造过程并不是简单的将根节点设置为红色或黑色，而是需要通过一系列的旋转和颜色翻转操作来保证树的平衡。具体的构造过程可以参考《算法导论》中的红黑树章节。...那么如何构造一棵红黑树使得红色内部结点个数最多呢？我们可以将所有关键字均放在红色节点上，这样红色节点的个数就等于n，而黑色节点的个数就为0。这样，红色内部结点个数与黑色内部结点个数的比值就是无穷大。...根据性质5，我们可以得出结论：在一棵红黑树中，从根节点到任意叶子节点的简单路径上，黑色节点的数量相同。设这个数量为k，那么红黑树的黑高为k。...由于黑色节点的数量为k，那么红黑树中的内部结点数量为2^(k-1) - 1。这是因为在一棵完全二叉树中，具有k层的满二叉树的节点数量为2^(k-1) - 1。
在操作系统源程序中，树和森林被用来构造文件系统。我们看到的window和linux等文件管理系统都是树型结构。在编译系统中，如C编译器源代码中，二叉树的中序遍历形式被用来存放C 语言中的表达式。...二叉树的算法时间复杂度表示为：O(logn)。拿这64格子棋盘举例，查找任一米粒所耗的时间，不超过64次，这速度难以置信吧。...红黑树 R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。...对于有n个结点的一棵完全二叉树来说，这些操作的最坏运行时间为Θ ( lg n ) \Theta(\lg n)Θ(lgn)。...ext2fs源码中直接能搜到红黑树的源码rbtree.c 鸿蒙OpenHarmony3.0源码中，红黑树rbtree.c源码位置： code-v3.0-LTS\OpenHarmony\third_party
中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。...虽然二叉排序树的最坏效率是O(n),但它支持动态查询,且有很多改进版的二叉排序树可以使树高为O(logn),如SBT,AVL,红黑树等.故不失为一种好的动态排序方法. 2.2 二叉排序树b中查找 在二叉排序树...常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。 平衡二叉树是二叉排序树的另一种形式。...红黑树 ---- 红黑树一种含有红黑结点并能自平衡的二叉查找树。除了符合二叉查找树的基本特性外，它必须满足下面性质： 性质1：每个节点要么是黑色，要么是红色。 性质2：根节点是黑色。...树中第k层上的结点个数为2k-1，查找它们所需的比较次数是k。
---- 前言 红黑树的基本情况我们已经在上一篇文章中学习过了，本文主要研究的是红黑树的实际应用：封装实现 set 和 map，看看如何通过一棵红黑树满足两个不同的数据结构；在正式封装之前，先要对之前的红黑树进行完善...，就是整个红黑树中的最右节点 ---- 2、封装实现 下面可以正式步入本文的主题：用一棵红黑树封装实现 set 和 map 红黑树的封装实现会涉及部分代码改动 为了进行区分，红黑树的完善代码名为 RBTree...这个类型 这一波是 set 为 map 做出了牺牲，迁就了 map 红黑树 改造第一步：接口调整 注：库中的 value_type 太长了，这里改为 T，既能表示 k，也能表示 k/v；原红黑树节点中的...typedef RBTree> Tree; private: Tree _t; //这也是一棵红黑树 }; } 接下来就很简单了，直接使用 红黑树 中的接口即可..._node) //构造 或 拷贝构造 {} 如何做到的？
文章目录 Part1 数组、链表、红黑树简介 1、二叉搜索树 2、AVL树与红黑树 2.1、AVL树 2.2、红黑树与AVL树的比较 2.3、红黑树的性质 2.4、红黑树的插入 Part2 HashMap...这棵树，说是树，其实它已经退化成链表了，但从概念上来看，它仍是一棵二叉搜索树，只要我们按照逐次增大，如1、2、3、4、5、6的顺序构造一棵二叉搜索树，则形如上图。...2.3、红黑树的性质 红黑树的性质： 红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是 RED ,也可以是 BLACK ；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍...链表查找时间复杂度为O(n)如何优化（树化过程） JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。...HashMap 通过引入红黑树来解决这个问题，使复杂度降到了O(logn).
在红黑树中，每个结点都关联一个额外的属性：红色或黑色中的一种颜色。...由此，可以得出引理：一棵具有n个节点的红黑树，其树高至多为2log(n+1) 。...这是因为当链表长度小于8的时候，链表虽然在查询效率（最坏时间复杂度为O(n)）上低于红黑树（最坏时间复杂度O(logn)），但是插入和删除操作开销远小于红黑树完成相同操作所需的开销，总体会优于红黑树。...我们再来看一下HashMap中的红黑树是如何实现的： static final class TreeNode extends LinkedHashMap.Entry { TreeNode...TreeMap中的红黑树 Map中的另一个重要实现类——TreeMap。
极端情况下，一条链从根到叶的话，时间固定就是O(n)了。就像下面这个棵树： 3、红黑树 红黑树也是一个二叉搜索树。那为什么会需要这么一棵树呢？ 就是为了避免上面哪种极端或者接近极端情况的出现。...它可以【保证最坏的情况下操作时间复杂度为O(lgn)】。 对的，是保证！那怎么保证呢？当然是通过维持红黑树本身的结构特点来实现。...我们上面及到过二叉搜索树节点包含的数据，红黑树会在其基础上增加一个存储位来表示节点的颜色（红或者黑）。...黑高：从某个节点到达其叶节点的【任何一个（参考e】简单路径上的黑色节点个数称之为黑高。红黑树的黑高即为其根节点的黑高。...一颗有 n 个内部节点的红黑树的高度至多为 2lg（n+1），也即我们前面说的能够保证最坏的情况下操作时间复杂度为O(lgn)。 红黑树有哪些应用呢？
实际上，红黑树的内部节点数量会在上述最多和最少之间变化，具体取决于树的具体构造。 通义千问： 在红黑树中，每个节点要么是红色，要么是黑色。...因此，一棵黑高为 k 的红黑树中，根节点到叶子节点的路径上最多有 k 个黑色节点（不包括叶子节点）。由于红黑树中红色节点不能连续存在，所以每个黑色节点之间至少有一个红色节点。...灵小智： 在一棵黑高为 k 的红黑树中，我们可以计算出内部结点的最多可能数量和最少可能数量。 最大可能数量：在红黑树中，每个红色节点必然有两个黑色子节点。...由于黑色节点不限制个数，我们可以构造一棵满二叉树，其中每个节点都是红色，每个红色节点有两个黑色子节点。如果树的黑高为 k，那么从根节点到叶子节点的路径上有 k 个黑色节点。...所以，在一棵黑高为k的红黑树中，内部结点的最大数量为2^(k-1) - 1，最小数量为0。
红黑树的概念 红黑树是一棵二叉搜索树，但是红黑树通过增加一个存储位表示结点的颜色RED或BLACK。...在定义当中，构造函数初始化列表对颜色_col默认初始化为红色是因为权衡了上面所述红黑树性质中的性质3和性质4。 性质3是说明了红黑树没有连续的红色节点，性质4说明的是每条路径都有相同数量的黑色节点。...红黑树的旋转直接复用AVL树的旋转的代码即可。 验证红黑树 红黑树的验证分两步：①通过中序遍历验证其是否满足二叉搜索树的性质。②验证是否满足红黑树的性质。...return Check(_root, 0, ref); } 红黑树与AVL树的对比 ⭐相同点：红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log_2 N)。...所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
这个方法会根据 HashMap 数组来决定是否转换为红黑树。 只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。...= 6; // 桶中结构转化为红黑树对应的 table 的最小值 static final int MIN_TREEIFY_CAPACITY = 64; // 存储元素的数组，...= null && key.equals(k)))) e = p; // 再判断 P 是不是一棵红黑树，如果是一棵红黑树就调用 putTreeVal...// 如果达到了8个结点，那么就调用treeifyBin()对当前这个链表进行树化（转成红黑树） // 在转成红黑树时，要进行判断，如果该 table 数组的大小小于64...= null && key.equals(k)))) e = p; // 再判断 P 是不是一棵红黑树，如果是一棵红黑树就调用 putTreeVal
原文链接：https://my.oschina.net/hosee/blog/618828 一、红黑树的介绍 先来看下算法导论对R-B Tree的介绍： 红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色...没有键值相等的节点（no duplicate nodes）。 因为一棵由n个结点随机构造的二叉查找树的高度为lgn，所以顺理成章，二叉查找树的一般操作的执行时间为O(lgn)。...红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。...但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢？这就引出了红黑树的5个性质： 每个结点要么是红的要么是黑的。 根结点是黑的。...正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度（红黑树的高度至多为2log(n+1)证明略），从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)
在这个例子中，二叉搜索树退化成了链表，搜索的时间复杂度为 O(n)，失去了作为一棵二叉搜索树的意义。 为了让二叉搜索树不至于太“倾斜”，我们需要构建一棵 平衡二叉搜索树。 ?...对于2-3树中的2-节点来说，本身就和二叉搜索树的节点无异，可以直接转换为红黑树的一个黑节点，但是对于3-节点来说，我们需要进行一点小转换： 将3-节点拆开，成为一棵树，并且3-节点的左元素作为右元素的子树...我们可以简单思考一下，对于一棵普通的平衡二叉搜索树来说，它的搜索时间复杂度为O(logn)，而作为红黑树，存在着最坏的情况，也就是查找的过程中，经过的节点全都是原来2-3树里的3-节点，导致路径延长两倍...，时间复杂度为O(2logn)，由于时间复杂度的计算可以忽略系数，因此红黑树的搜索时间复杂度依然是O(logn)，当然，由于这个系数的存在，在实际使用中，红黑树会比普通的平衡二叉树（AVL树）搜索效率要低一些...红黑树的创建 上文中我们讲解了如何由2-3树转换一棵红黑树，下面我们就来看看如何不经过2-3树直接创建一棵红黑树，毕竟我们写代码的时候不能先创建一棵2-3树再转化成红黑树吧。
map中的key是唯一的，并且不能修改 默认按照小于的方式对key进行比较 map中的元素如果用迭代器去遍历，可以得到一个有序的序列 map的底层为平衡搜索树(红黑树)，查找效率比较高O(log...1(-1/0/1) 如果一棵二叉搜索树是高度平衡的，它就是AVL树 如果它有n个结点，其高度可保持在O(log_2 n)，搜索时间复杂度O(log_2 n) 4.1.2 AVL树节点的定义 AVL树节点的定义...4.2.1 红黑树的概念 红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。...) 4.2.8 红黑树与AVL树的比较 红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log_2 N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数...map的底层结构就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可 Mymap.h #pragma once namespace dc { template<class K, class
以42作为根节点，顺序插入元素） 在这个例子中，二叉搜索树退化成了链表，搜索的时间复杂度为 O(n)，失去了作为一棵二叉搜索树的意义。...将原来的左元素标记为红色（表示红色节点与其父节点在2-3树中曾是平级的关系） 我们来转换一棵复杂点的2-3树，根据上边的两条转换规则，我们将2-节点直接转换为黑色节点，将3-节点拆成一棵子树，并给左元素标上红色...我们可以简单思考一下，对于一棵普通的平衡二叉搜索树来说，它的搜索时间复杂度为O(logn)，而作为红黑树，存在着最坏的情况，也就是查找的过程中，经过的节点全都是原来2-3树里的3-节点，导致路径延长两倍...，时间复杂度为O(2logn)，由于时间复杂度的计算可以忽略系数，因此红黑树的搜索时间复杂度依然是O(logn)，当然，由于这个系数的存在，在实际使用中，红黑树会比普通的平衡二叉树（AVL树）搜索效率要低一些...红黑树的创建 上文中我们讲解了如何由2-3树转换一棵红黑树，下面我们就来看看如何不经过2-3树直接创建一棵红黑树，毕竟我们写代码的时候不能先创建一棵2-3树再转化成红黑树吧。
红黑树首先是一棵二分搜索树，这一点和AVL树是一样的，红黑树也是一种平衡二叉树，红黑树在二分搜索树中添加了一些其它的性质，来保证红黑树不会退化成链表，来保证自己在某种情况下是一种平衡二叉树。 ...所以查找元素的时间复杂度是O(logn)级别的、修改元素的时间复杂度是O(logn)级别的、删除元素的时间复杂度是O(logn)级别的、新增元素的时间复杂度是O(logn)级别的，因此红黑树不会像二分搜索树一样退化成一个链表...5、2-3树如何维持绝对的平衡，通过向2-3树中添加节点操作来看2-3树如何维持绝对的平衡。通过通过向2-3树中添加节点操作来看2-3树维持绝对的平衡来看红黑树，其实是等价的。 ? ...但是，我们实现的二分搜索树，其实对边这样的一个对象是并没有相应的类来表示的，那么同样在红黑树中，我们也没有必要对于每两个节点，它们之间所连接的这个边实现一个特殊的类来表示，可是这个边又是红色的，如何来表示特殊的颜色的边呢...向红黑树中添加新节点，等价于向2-3树的3节点上融合一个新的元素，对应这个过程在红黑树中是如何操作的呢，有三种形式。
2-3树是二叉查找树的变种，树中的2和3代表两种节点，以下表示为2-节点和3-节点。 2-节点即普通节点：包含一个元素，两条子链接。...因此，红黑树出现了，红黑树的背后逻辑就是2-3树的逻辑，但是由于用红黑作为标记这个小技巧，最后实现的代码量并不大。(但是，要直接理解这些代码是如何工作的以及背后的道理，就比较困难了。...红黑树中，所有的节点都是标准的2-节点，为了体现出3-节点，这里将3-节点的两个元素用左斜红色的链接连接起来，即连接了两个2-节点来表示一个3-节点。...红黑树示意图如下： 红黑树的应用 红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。...红黑树的时间复杂度和相关证明 红黑树的时间复杂度为: O(lgn) 下面通过“数学归纳法”对红黑树的时间复杂度进行证明。 定理：一棵含有n个节点的红黑树的高度至多为2log(n+1).
领取专属 10元无门槛券
手把手带您无忧上云
