红黑树（Red-Black Tree）：原理、常见算法及其应用

ops/2024/12/23 8:46:29/

目录

引言

红黑树的基本概念

常见算法

插入节点

查找节点

删除节点

红黑树的应用场景

1. 数据库索引

2. 符号表

3. 动态集合

总结

优势对比

自平衡条件

旋转次数

操作效率

应用场景

实现复杂度

引言

红黑树（Red-Black Tree）是一种自平衡的二叉查找树，它的设计目的是为了在最坏的情况下保证查找、插入和删除操作的时间复杂度为 O(logn)。红黑树通过特定的颜色标记和旋转操作来维持树的近似平衡，从而确保了高效的性能表现。本文将从红黑树的基本概念出发，逐步介绍其原理、常见算法，并通过具体的Java代码示例来加深理解，最后探讨红黑树在算法中的实际应用场景，并总结对比红黑树与平衡二叉树（如AVL树）的优势。

红黑树的基本概念

红黑树是一种特殊的二叉查找树，其特点在于通过颜色标记来保持树的平衡性。每个节点都被标记为红色或黑色，并遵循以下规则：

  1. 根节点是黑色。
  2. 每个叶子节点（NIL节点）都是黑色。
  3. 没有相邻的两个红色节点（即任何一个红色节点的父节点和子节点必须是黑色）。
  4. 从任一节点到达其每个叶子节点的所有路径上黑色节点的数量相同（称为黑高）。

这些规则确保了红黑树的高度不会超过 2log2​(n+1)，其中 n 是树中的节点数。

节点定义

class RedBlackTreeNode {int val;boolean color; // true for red, false for blackRedBlackTreeNode left;RedBlackTreeNode right;RedBlackTreeNode parent;RedBlackTreeNode(int x) {val = x;color = true; // New nodes are initially redleft = null;right = null;parent = null;}
}

常见算法

插入节点

插入新节点时，需要先按照二叉查找树的方式找到合适的位置，然后进行必要的旋转和重新着色操作以恢复红黑树的平衡性。

Java代码实现

public class RedBlackTree {private RedBlackTreeNode root;private RedBlackTreeNode nil;public RedBlackTree() {nil = new RedBlackTreeNode(Integer.MIN_VALUE);nil.color = false; // Blackroot = nil;}// 插入节点public void insert(int value) {RedBlackTreeNode newNode = new RedBlackTreeNode(value);RedBlackTreeNode y = nil;RedBlackTreeNode x = root;while (x != nil) {y = x;if (newNode.val < x.val) {x = x.left;} else {x = x.right;}}newNode.parent = y;if (y == nil) {root = newNode;} else if (newNode.val < y.val) {y.left = newNode;} else {y.right = newNode;}newNode.left = nil;newNode.right = nil;newNode.color = true; // New node is red// Balance the treeinsertFixup(newNode);}private void insertFixup(RedBlackTreeNode z) {while (z.parent.color == true) {if (z.parent == z.parent.parent.left) {RedBlackTreeNode y = z.parent.parent.right;if (y.color == true) { // Case 1z.parent.color = false;y.color = false;z.parent.parent.color = true;z = z.parent.parent;} else { // Case 2if (z == z.parent.right) {z = z.parent;leftRotate(z);}// Case 3z.parent.color = false;z.parent.parent.color = true;rightRotate(z.parent.parent);}} else { // Symmetric to the above codeRedBlackTreeNode y = z.parent.parent.left;if (y.color == true) {z.parent.color = false;y.color = false;z.parent.parent.color = true;z = z.parent.parent;} else {if (z == z.parent.left) {z = z.parent;rightRotate(z);}z.parent.color = false;z.parent.parent.color = true;leftRotate(z.parent.parent);}}}root.color = false; // Root is always black}// 左旋private void leftRotate(RedBlackTreeNode x) {RedBlackTreeNode y = x.right;x.right = y.left;if (y.left != nil) {y.left.parent = x;}y.parent = x.parent;if (x.parent == nil) {root = y;} else if (x == x.parent.left) {x.parent.left = y;} else {x.parent.right = y;}y.left = x;x.parent = y;}// 右旋private void rightRotate(RedBlackTreeNode y) {RedBlackTreeNode x = y.left;y.left = x.right;if (x.right != nil) {x.right.parent = y;}x.parent = y.parent;if (y.parent == nil) {root = x;} else if (y == y.parent.right) {y.parent.right = x;} else {y.parent.left = x;}x.right = y;y.parent = x;}
}

示例：插入关键字序列 (16, 3, 7, 11, 9, 26, 18, 14, 15)

public static void main(String[] args) {RedBlackTree rbTree = new RedBlackTree();// 插入关键字序列rbTree.insert(16);rbTree.insert(3);rbTree.insert(7);rbTree.insert(11);rbTree.insert(9);rbTree.insert(26);rbTree.insert(18);rbTree.insert(14);rbTree.insert(15);// 打印树的节点rbTree.printTree(rbTree.root);
}

查找节点

查找特定值的节点时，从根节点开始，根据值与当前节点值的关系决定向左还是向右。

Java代码实现

public RedBlackTreeNode search(int value) {return searchRecursive(root, value);
}private RedBlackTreeNode searchRecursive(RedBlackTreeNode current, int value) {if (current == nil) {return nil;}if (value == current.val) {return current;}return value < current.val? searchRecursive(current.left, value): searchRecursive(current.right, value);
}

删除节点

删除节点时需要考虑三种情况：

  1. 节点是叶子节点。
  2. 节点有一个子节点。
  3. 节点有两个子节点。

Java代码实现

public void delete(int value) {RedBlackTreeNode z = search(value);if (z == nil) {return; // Value not found}deleteNode(z);
}private void deleteNode(RedBlackTreeNode z) {RedBlackTreeNode y = z;boolean yOriginalColor = y.color;RedBlackTreeNode x = nil;if (z.left == nil) {x = z.right;transplant(z, z.right);} else if (z.right == nil) {x = z.left;transplant(z, z.left);} else {y = minimum(z.right);yOriginalColor = y.color;x = y.right;if (y.parent == z) {x.parent = y;} else {transplant(y, y.right);y.right = z.right;y.right.parent = y;}transplant(z, y);y.left = z.left;y.left.parent = y;y.color = z.color;}if (yOriginalColor == false) {deleteFixup(x);}
}private void deleteFixup(RedBlackTreeNode x) {while (x != root && x.color == false) {if (x == x.parent.left) {RedBlackTreeNode s = x.parent.right;if (s.color == true) { // Case 1s.color = false;x.parent.color = true;leftRotate(x.parent);s = x.parent.right;}if (s.left.color == false && s.right.color == false) { // Case 2s.color = true;x = x.parent;} else {if (s.right.color == false) { // Case 3s.left.color = false;s.color = true;rightRotate(s);s = x.parent.right;}// Case 4s.color = x.parent.color;x.parent.color = false;s.right.color = false;leftRotate(x.parent);x = root;}} else { // Symmetric to the above codeRedBlackTreeNode s = x.parent.left;if (s.color == true) { // Case 1s.color = false;x.parent.color = true;rightRotate(x.parent);s = x.parent.left;}if (s.right.color == false && s.left.color == false) { // Case 2s.color = true;x = x.parent;} else {if (s.left.color == false) { // Case 3s.right.color = false;s.color = true;leftRotate(s);s = x.parent.left;}// Case 4s.color = x.parent.color;x.parent.color = false;s.left.color = false;rightRotate(x.parent);x = root;}}}x.color = false;
}private void transplant(RedBlackTreeNode u, RedBlackTreeNode v) {if (u.parent == nil) {root = v;} else if (u == u.parent.left) {u.parent.left = v;} else {u.parent.right = v;}v.parent = u.parent;
}private RedBlackTreeNode minimum(RedBlackTreeNode x) {while (x.left != nil) {x = x.left;}return x;
}private void printTree(RedBlackTreeNode node) {if (node != nil) {printTree(node.left);System.out.print("Value: " + node.val + " Color: " + (node.color ? "Red" : "Black") + "\n");printTree(node.right);}
}

红黑树的应用场景

1. 数据库索引

红黑树可以用于构建数据库的索引，以加速查询速度。

应用原理

  • 数据库记录的键值存储在红黑树的节点中。
  • 查询时，根据键值在树中查找对应的记录。
  • 插入和删除记录时，自动调整树的平衡，保持较低的高度。

场景描述

在数据库管理系统中，索引是提高查询效率的重要手段之一。当数据库需要频繁地按某个字段进行查询时，可以创建基于该字段的红黑树索引。这样，在执行查询操作时，可以迅速定位到指定键值所在的记录，而不需要全表扫描。红黑树的自平衡特性确保了索引结构的高效性，即使在频繁的插入和删除操作下也能保持良好的性能。

2. 符号表

在编程语言的编译器中，符号表用于跟踪变量声明和类型信息。

应用原理

  • 变量名称作为键值存储在红黑树中。
  • 变量的类型和其他相关信息作为键值对应的数据存储。
  • 编译器在处理源代码时，需要维护一个符号表来跟踪所有的变量声明及其属性。

场景描述

编译器在处理源代码时，需要维护一个符号表来跟踪所有的变量声明及其属性。红黑树可以有效地管理这些信息，因为编译器可以根据变量名称快速查找、插入或更新相应的信息。这有助于编译器在编译过程中进行类型检查和其他优化工作。红黑树的自平衡特性使得符号表能够在处理大型代码库时依然保持高效。

3. 动态集合

红黑树可以用于实现动态集合，支持动态添加、删除元素并保持有序。

应用原理

  • 集合中的元素作为键值存储在红黑树中。
  • 插入新元素时，保持树的有序性。
  • 删除元素时，调整树以保持红黑树的性质。

场景描述

在需要动态管理一组有序元素的应用场景中，如任务队列或优先级队列，红黑树可以有效地支持元素的插入、删除操作，同时保持集合的有序性。这使得在处理动态变化的数据集合时更加高效和灵活。红黑树的自平衡特性使得动态集合在频繁的操作下依然保持良好的性能。

总结

红黑树作为一种高效的数据结构，在计算机科学中有广泛的应用。通过特定的颜色标记和旋转操作来保持树的近似平衡，红黑树在最坏的情况下也能够保证操作的时间复杂度为 �(log⁡�)O(logn)。掌握红黑树的概念和相关算法对于深入理解计算机科学的核心知识至关重要。

以下是总结对比红黑树与平衡二叉树（如AVL树）的优势：

优势对比

自平衡条件
  • 红黑树：允许一定程度的高度不平衡，只要满足红黑树的五条规则即可。
  • AVL树：严格限制左右子树的高度差不超过1，这使得AVL树的高度始终接近最优。
旋转次数
  • 红黑树：在插入或删除节点时，需要进行的旋转次数通常少于AVL树。
  • AVL树：为了保持严格的平衡条件，AVL树在插入或删除节点时需要频繁地进行旋转。
操作效率
  • 红黑树：由于旋转次数较少，红黑树在频繁的插入和删除操作下整体性能通常优于AVL树。
  • AVL树：虽然AVL树的高度更低，但由于频繁的旋转，整体性能在某些情况下可能不如红黑树。
应用场景
  • 红黑树：因其较宽松的平衡条件，适用于更多需要自平衡特性的场景，如数据库索引、操作系统调度等。
  • AVL树：适用于需要严格平衡条件的应用场景，如某些特定的数值计算领域。
实现复杂度
  • 红黑树：相比AVL树，红黑树的实现相对简单，更容易理解和实现。
  • AVL树：AVL树的实现较为复杂，需要处理更多的情况来保持严格的平衡条件。

综上所述，红黑树以其较高的灵活性、较低的旋转次数以及更简单的实现方式，在许多实际应用中表现出色。然而，AVL树在某些特定的应用场景下仍然具有其独特的优势。选择哪种数据结构取决于具体的应用需求和性能要求。


http://www.ppmy.cn/ops/117231.html

相关文章

使用Okhttp-服务器不支持缓存的解决办法

使用Okhttp-服务器不支持缓存的解决办法

使用 OkHttp 创建一个缓存拦截器&#xff0c;以确保无论网络状态如何&#xff0c;都能优先获取缓存的数据。 1. 创建拦截器 首先&#xff0c;我们需要创建一个拦截器&#xff0c;用于处理请求和响应的缓存逻辑&#xff1a; import okhttp3.Interceptor; import okhttp3.Requ…
阅读更多...
Session和Cookie是什么？有什么区别？分布式Session问题又是什么？

Session和Cookie是什么？有什么区别？分布式Session问题又是什么？

Session和Cookie是什么&#xff1f;有什么区别&#xff1f;分布式Session问题又是什么&#xff1f; Cookie&#xff1a;是服务器发送到浏览器并保存在本地的数据。在浏览器下一次向同一服务器再次发送请求时&#xff0c;将Cookie也发送给服务器&#xff0c;并以此来判定这个请…
阅读更多...
VScode 常用操作

VScode 常用操作

1.VScode 无法格式化 未勾选Format on Type:
阅读更多...
Prometheus监控k8s环境构建

Prometheus监控k8s环境构建

传统架构中比较流行的监控工具有 Zabbix、Nagios 等&#xff0c;这些监控工具对于 Kubernetes 这类云平台的监控不是很友好&#xff0c;特别是当 Kubernetes 集群中有了成千上万的容器后更是如此&#xff0c;本章节学习下一代的云原生监控平台---Prometheus。 一、基于kuberne…
阅读更多...
（11）(2.1.2) DShot ESCs（四）

（11）(2.1.2) DShot ESCs（四）

文章目录 前言 6 混合ESC协议 7 IOMCU DShot限制 8 参数说明 前言 DShot 是一种数字 ESC 协议&#xff0c;它允许快速、高分辨率的数字通信&#xff0c;可以改善飞行器控制&#xff0c;这在多旋翼和 quadplane 应用中特别有用。 6 混合ESC协议 虽然 ArduPilot 自动驾驶仪…
阅读更多...
PHP 中传值与传引用的区别

PHP 中传值与传引用的区别

在 PHP 中&#xff0c;理解传值与传引用的区别对于编写高效、可维护的代码至关重要。 一、基础概念 1. 传值&#xff08;Pass by Value&#xff09; 在 PHP 中&#xff0c;默认情况下&#xff0c;参数是通过值传递的。这意味着函数内部对参数所做的任何修改都不会影响到函数…
阅读更多...
前端独立实现页面是否有发布

前端独立实现页面是否有发布

1、自动更新js (AutoUpdate.js) import { Modal } from "antd"let lastSrcs; const scriptReg /\<script.*src["](?<src>[^"])/gm; async function extractNewScripts() {const html await fetch(/?_timnestamp Date.now()).then(res > …
阅读更多...
Unity DOTS Baking System与Baking World

Unity DOTS Baking System与Baking World

最近DOTS终于发布了正式的版本, 我们来分享一下DOTS里面Baking阶段&#xff0c;Baking System&#xff0c;Baking World的关键概念&#xff0c;方便大家上手学习掌握Unity DOTS开发。Unity在Baking也是基于ECS模式开发设计的&#xff0c;所以Baking的时候也会有Baking System与…
阅读更多...
最新文章

Copyright @ 2022~2023