红黑树复杂度_红黑树查询时间复杂度

2024年 9月 14日上午11:36 • 激活谷笔记

红黑树 (Red-Black Tree) – 介绍　　介绍：　　红黑树是一种自平衡二叉搜索树，其中每个节点都有一个额外的位，并且该位通常被解释为颜色（红色或黑色）。这些颜色用于确保树在插入和删除期间保持平衡。虽然树的平衡并不完美，但减少搜索时间并将其保持在 O(log n) 时间左右就足够了，其中 n 是树中素的总数。这棵树是Rudolf Bayer于 1972 年发明的。　　必须注意的是，由于每个节点只需要 1 位空间来存储颜色信息，这些类型的树显示与经典（未着色）二叉搜索树相同的内存占用。　　每棵红黑树都遵循的规则：每个节点都有红色或黑色的颜色。树的根总是黑色的。没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点）。从节点（包括根）到其任何后代 NULL 节点的每条路径都具有相同数量的黑色节点。所有叶子节点都是黑色节点。　　为什么是红黑树？　　大多数 BST 操作（包括，搜索、最大值、最小值、插入、删除……等）需要 O(h) 时间，其中 h 是 BST 的高度。对于倾斜的二叉树，这些操作的成本可能会变成 O(n)。如果我们确保每次插入和删除后树的高度保持 O(log n)，那么我们可以保证所有这些操作的上限为 O(log n)。红黑树的高度及各操作的时间复杂度始终为 O(log n)，其中 n 是树中的节点数，　　与AVL 树的比较：　　与红黑树相比，AVL 树更平衡，但在插入和删除过程中可能会导致更多的旋转。因此，如果您的应用程序涉及频繁的插入和删除，那么应该首选红黑树。如果插入和删除的频率较低，而搜索是一种更频繁的操作，那么 AVL 树应该优先于红黑树。　　红黑树如何确保平衡？　　理解平衡的一个简单示例是，在红黑树中不可能有 3 个节点的链。我们可以尝试任何颜色的组合，看看它们是否都违反了红黑树属性。　　

三节点红黑树可能的结构　　红黑树的属性：红黑树的黑色高度是从根节点到叶节点的路径上的黑色节点数。叶节点也算作黑色节点。因此，高度为 h 的红黑树的黑色高度 >= h/2。具有 n 个节点的红黑树的高度为 h<= 2 log 2 (n + 1)。所有叶子 (NIL) 都是黑色的。节点的黑色深度定义为从根到该节点的黑色节点数，即黑色祖先的数量。每棵红黑树都是二叉树的特例。　　红黑树的黑色高度：　　黑色高度是从根到叶子的路径上黑色节点的数量。叶节点也算作黑色节点。从上面的属性 3 和 4，我们可以得出，高度为 h 的红黑树的 black-height >= h/2。　　从任何一个节点到其最远的后代叶子的节点数不超过到最近的后代叶子的节点数的两倍。　　每个具有 n 个节点的红黑树的高度 <= 2Log 2 (n+1) 　　证明如下：　　对于一般的二叉树，设k是所有根到 NULL 路径上的最小节点数，则 n >= 2 k – 1（例如，如果 k 为 3，则 n 至少为 7）。这个表达式也可以写成 k <= Log 2 (n+1)。　　从红黑树的属性 4 和上述声明，我们可以说在具有 n 个节点的红黑树中，有一条从根到叶的路径最多具有 Log 2 (n+1) 个黑色节点。　　根据红黑树的属性 3 和 5，我们可以声称红黑树中黑色节点的数量至少为 ⌊ n/2 ⌋ 其中 n 是节点的总数。　　从以上几点，我们可以得出这样一个事实：具有n 个节点的红黑树的高度 <= 2Log 2 (n+1) 　　红黑树中的搜索操作：　　由于每棵红黑树都是二叉树的特例，所以红黑树的搜索算法与二叉树的搜索算法类似。　　算法: 　　

　　实例: 在以下红黑树中搜索11从根开始。将插入素与根进行比较，如果小于根，则递归左，否则递归右。如果在任何地方找到要搜索的素，则返回 true，否则返回 false。　　

跟随蓝色气泡　　红黑树的应用：大多数自平衡 BST 库函数，如 C++ 中的 map、multiset 和 multimap（或 TreeMap 和 TreeSet 等 java 软件包）都使用红黑树。它用于实现Linux的CPU调度。Completely Fair Scheduler使用它。它还用于机器学习中的 K-mean 聚类算法，以降低时间复杂度。此外，MySQL 还使用红黑树对表进行索引，以减少搜索和插入时间。　　相关文章：　　（二）红黑树（Red-Black Tree）- 插入操作 – 嗅探网的文章 – 知乎　　（三）红黑树（Red-Black Tree）- 删除操作 – 嗅探网的文章 – 知乎　　完整示例代码下载链接：　　（包含各种语言：C语言、Python、Java，C++等均有示例）见标题　　

红黑树 复杂度_红黑树查询时间复杂度

相关推荐

红黑树复杂度_红黑树查询时间复杂度