【愚公系列】2023年11月 数据结构(十二)-红黑树
🏆 作者简介，愚公搬代码 🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。 🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
🚀前言
数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。
- 数组（Array）：是一种线性数据结构，它将一组具有相同类型的数据元素存储在一起，并为每个元素分配一个唯一的索引。数组的特点是具有随机访问的能力。
- 链表（Linked List）：也是一种线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的引用。链表的特点是可以动态地插入或删除节点，但访问某个节点时需要从头开始遍历。
- 栈（Stack）：是一种后进先出（LIFO）的数据结构，它只能在栈顶进行插入和删除操作。栈通常用于实现递归算法、表达式求值和内存管理等场景。
- 队列（Queue）：是一种先进先出（FIFO）的数据结构，它可以在队尾插入元素，在队头删除元素。队列通常用于数据的缓存、消息队列和网络通信等场景。
- 哈希表（Hash Table）：也称为散列表，它是一种根据关键字直接访问数据的数据结构。哈希表通常由数组和散列函数组成，可以在常数时间内进行插入、删除和查找操作。
- 树（Tree）：是一种非线性数据结构，它由一系列的节点组成，每个节点可以有若干个子节点。树的特点是可以动态地插入或删除节点，常见的树结构包括二叉树、平衡树和搜索树等。
- 堆（Heap）：是一种特殊的树结构，它通常用于实现优先队列和堆排序等算法。堆分为最大堆和最小堆，最大堆的每个节点的值都大于等于其子节点的值，最小堆则相反。
- 图（Graph）：是一种由节点和边组成的非线性数据结构，它可以用来表示各种实体之间的关系，如社交网络、路线图和电路图等。图的遍历和最短路径算法是常见的图算法。
🚀一、红黑树
🔎1.基本思想
红黑树是一种自平衡的二叉查找树，其基本思想是通过染色和旋转操作，保证每个节点的左右子树高度差不超过2倍。具体来说，红黑树在节点上增加一个颜色标记，分为红色和黑色，通过以下规则来维护平衡性：
- 每个节点都有一个颜色，要么是红色，要么是黑色。
- 根节点是黑色。
- 每个叶节点（NIL节点，空节点）是黑色。
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 任意一节点到其每个叶子节点的所有路径上黑色节点个数相同。
红黑树在插入和删除节点时，通过旋转和颜色变换等操作来维护平衡性。在插入节点时，先按照二叉查找树的规则进行插入，然后通过变换节点颜色和旋转操作，使得红黑树仍然满足上述规则。在删除节点时，同样也需要进行颜色变换和旋转操作来维护平衡性。通过这些操作，可以保证红黑树的平衡性，并且保证插入、查询和删除的时间复杂度都是O(log n)。
🔎2.红黑树常用操作
红黑树是一种自平衡的二叉搜索树，常用于实现映射和集合等数据结构。C#中可以使用以下代码实现红黑树的常用操作：
class TreeNode<T>
{
public T Data { get; set; }
public TreeNode<T> LeftChild { get; set; }
public TreeNode<T> RightChild { get; set; }
public TreeNode<T> Parent { get; set; }
public int Color { get; set; }
public TreeNode(T data)
{
Data = data;
Parent = null;
LeftChild = null;
RightChild = null;
}
public TreeNode(T newData, TreeNode<T> parent)
{
Data = newData;
Parent = parent;
LeftChild = null;
RightChild = null;
}
}
internal class RedBlackTree<T> where T : IComparable<T>, IEquatable<T>, new()
{
public TreeNode<T> Root { get; private set; }
public int Size { get; private set; }
public RedBlackTree()
{
Root = null;
Size = 0;
}
private static TreeNode<T> Add(TreeNode<T> to, TreeNode<T> newNode)
{
if (newNode.Data.CompareTo(to.Data) < 0)
{
if (to.LeftChild != null) return Add(to.LeftChild, newNode);
newNode.LeftChild = null;
newNode.RightChild = null;
to.LeftChild = newNode;
newNode.Color = 1;
newNode.Parent = to;
return newNode;
}
if (to.RightChild != null) return Add(to.RightChild, newNode);
newNode.LeftChild = null;
newNode.RightChild = null;
to.RightChild = newNode;
newNode.Color = 1;
newNode.Parent = to;
return newNode;
}
private void LeftTurn(TreeNode<T> node)
{
if (node.RightChild == null) return;
var child = node.RightChild;
node.RightChild = child.LeftChild;
if (child.LeftChild != null) child.LeftChild.Parent = node;
child.Parent = node.Parent;
if (node.Parent == null) Root = child;
else
{
if (node == node.Parent.LeftChild)
node.Parent.LeftChild = child;
else
node.Parent.RightChild = child;
}
child.LeftChild = node;
node.Parent = child;
}
private void RightTurn(TreeNode<T> node)
{
if (node.LeftChild == null) return;
var child = node.LeftChild;
node.LeftChild = child.RightChild;
if (child.RightChild != null) child.RightChild.Parent = node;
child.Parent = node.Parent;
if (node.Parent == null) Root = child;
else
{
if (node == node.Parent.RightChild) node.Parent.RightChild = child;
else node.Parent.LeftChild = child;
}
child.RightChild = node;
node.Parent = child;
}
public void Insert(TreeNode<T> node)
{
if (Root == null)
{
Root = node;
Root.Color = 0;
Root.LeftChild = null;
Root.RightChild = null;
Root.Parent = null;
}
else
{
var addedNode = Add(Root, node);
while (addedNode != Root && addedNode.Parent.Color == 1)
{
if (addedNode.Parent == addedNode.Parent.Parent.LeftChild)
{
var y = addedNode.Parent.Parent.RightChild;
if (y != null && y.Color == 1)
{
addedNode.Parent.Color = 0;
y.Color = 0;
addedNode.Parent.Parent.Color = 1;
addedNode = addedNode.Parent.Parent;
}
else
{
if (addedNode == addedNode.Parent.RightChild)
{
addedNode = addedNode.Parent;
LeftTurn(addedNode);
}
addedNode.Parent.Color = 0;
addedNode.Parent.Parent.Color = 1;
RightTurn(addedNode.Parent.Parent);
}
}
else
{
var y = addedNode.Parent.Parent.LeftChild;
if (y != null && y.Color == 1)
{
addedNode.Parent.Color = 0;
y.Color = 0;
addedNode.Parent.Parent.Color = 1;
addedNode = addedNode.Parent.Parent;
}
else
{
if (addedNode == addedNode.Parent.Parent.LeftChild)
{
addedNode = addedNode.Parent;
RightTurn(addedNode);
}
addedNode.Parent.Color = 0;
addedNode.Parent.Parent.Color = 1;
LeftTurn(addedNode.Parent.Parent);
}
}
}
}
Root.Color = 0;
}
private static TreeNode<T> Min(TreeNode<T> node)
{
while (node.LeftChild != null) node = node.LeftChild;
return node;
}
private static TreeNode<T> Next(TreeNode<T> node)
{
if (node.RightChild != null) return Min(node.RightChild);
var y = node.Parent;
while (y != null && node == y.RightChild)
{
node = y;
y = y.Parent;
}
return y;
}
private void FixUp(TreeNode<T> node)
{
while (node != Root && node.Color == 0)
{
if (node == node.Parent.LeftChild)
{
var w = node.Parent.RightChild;
if (w.Color == 1)
{
w.Color = 0;
node.Parent.Color = 1;
LeftTurn(node.Parent);
w = node.Parent.RightChild;
}
if (w.LeftChild.Color == 0 && w.RightChild.Color == 0)
{
w.Color = 1;
node = node.Parent;
}
else
{
if (w.RightChild.Color == 0)
{
w.LeftChild.Color = 0;
w.Color = 1;
RightTurn(w);
w = node.Parent.RightChild;
}
w.Color = node.Parent.Color;
node.Parent.Color = 0;
w.RightChild.Color = 0;
LeftTurn(node.Parent);
node = Root;
}
}
else
{
var w = node.Parent.LeftChild;
if (w.Color == 1)
{
w.Color = 0;
node.Parent.Color = 1;
RightTurn(node.Parent);
w = node.Parent.LeftChild;
}
if (w.RightChild.Color == 0 && w.LeftChild.Color == 0)
{
w.Color = 1;
node = node.Parent;
}
else
{
if (w.LeftChild.Color == 0)
{
w.RightChild.Color = 0;
w.Color = 1;
LeftTurn(w);
w = node.Parent.LeftChild;
}
w.Color = node.Parent.Color;
node.Parent.Color = 0;
w.LeftChild.Color = 0;
RightTurn(node.Parent);
node = Root;
}
}
}
node.Color = 0;
}
public void Delete(TreeNode<T> node)
{
TreeNode<T> y;
if (node.LeftChild == null || node.RightChild == null)
y = node;
else
y = Next(node);
var x = y.LeftChild ?? y.RightChild;
if (x == null)
{
node.Data = y.Data;
if (y.Parent == null) return;
if (y.Parent.LeftChild == y) y.Parent.LeftChild = null;
else y.Parent.RightChild = null;
return;
}
x.Parent = y.Parent;
if (y.Parent == null) Root = x;
else
{
if (y == y.Parent.LeftChild) y.Parent.LeftChild = x;
else y.Parent.RightChild = x;
}
if (y != node)
{
node.Data = y.Data;
}
if (y.Color == 0) FixUp(x);
}
private static TreeNode<T> SearchInSubTree(TreeNode<T> topNode, T data)
{
if (data.Equals(topNode.Data))
return topNode;
if (data.CompareTo(topNode.Data) < 0 && topNode.LeftChild != null)
return SearchInSubTree(topNode.LeftChild, data);
if (data.CompareTo(topNode.Data) > 0 && topNode.RightChild != null)
return SearchInSubTree(topNode.RightChild, data);
return null;
}
public bool Search(T data)
{
return SearchInSubTree(Root, data) != null;
}
public TreeNode<T> SearchNode(T data)
{
return SearchInSubTree(Root, data);
}
public IEnumerator<T> GetEnumerator()
{
if (Root == null)
yield break;
var current = Min(Root);
yield return current.Data;
while (Next(current) != null)
{
current = Next(current);
yield return current.Data;
}
}
public IEnumerator<TreeNode<T>> DfsEnum()
{
var verts = new Stack<TreeNode<T>>();
if (Root == null)
yield break;
verts.Push(Root);
var previous = 0;
while (verts.Count != 0)
{
var current = verts.Peek();
if (current.LeftChild == null && current.RightChild == null)
{
verts.Pop();
yield return current;
if (current.Parent != null)
previous = current == current.Parent.LeftChild ? 1 : 2;
else
yield break;
continue;
}
switch (previous)
{
case 0:
if (current.LeftChild == null)
{
previous = 1;
continue;
}
verts.Push(current.LeftChild);
previous = 0;
break;
case 1:
if (current.RightChild == null)
{
verts.Pop();
yield return current;
if (current.Parent != null)
{
previous = current == current.Parent.LeftChild ? 1 : 2;
continue;
}
yield break;
}
verts.Push(current.RightChild);
previous = 0;
break;
case 2:
verts.Pop();
yield return current;
if (current.Parent != null)
previous = current == current.Parent.LeftChild ? 1 : 2;
else
yield break;
break;
}
}
}
public IEnumerator<TreeNode<T>> BfsEnum()
{
var verts = new Queue<TreeNode<T>>();
verts.Enqueue(Root);
while (verts.Count != 0)
{
var current = verts.Dequeue();
yield return current;
if (current.LeftChild != null)
verts.Enqueue(current.LeftChild);
if (current.RightChild != null)
verts.Enqueue(current.RightChild);
}
}
}上述代码实现了红黑树的插入、查找和删除操作。其中，插入使用了三种旋转操作和颜色翻转操作来保证平衡性和红黑树的五个性质。查找使用了二叉搜索树的基本方法。删除操作比插入操作更复杂，需要考虑大量特殊情况。其中，删除操作的辅助函数MoveRedLeft()和MoveRedRight()用于将红色节点向下移动，以便进行删除操作。DeleteMin()用于删除红黑树中的最小节点。FixUp()用于修复删除节点后的平衡性和红黑树的五个性质。
🔎3.优点和缺点
红黑树是一种自平衡二叉查找树，它具有以下优点和缺点：
优点：
- 查找、插入、删除操作的时间复杂度是O(log n)级别，效率较高。
- 操作次数比AVL树稍微少一些，因为 AVL 树在插入和删除操作时需要进行更多次的旋转操作来保持平衡。
- 它的平衡性能比一般的自平衡二叉查找树更好，可以保证在最坏情况下，基本的动态操作仍然是O(log n)时间复杂度。
- 红黑树的结构相对简单，实现比较容易。
缺点：
- 红黑树的结构并不是最优的，因为它的常数比较大，比如平衡因子的两种颜色需要额外的存储空间。
- 插入和删除操作需要进行颜色翻转、左旋右旋等操作，实现比较复杂。
- 由于红黑树的结构比较复杂，其实现比较容易出错，导致性能下降或者产生错误的结果。
- 红黑树的树高比较大，导致访问元素的效率较低。
🔎4.应用场景
红黑树可以用于实现一些高效的数据结构，例如：
- C++ STL中的map和set都是使用红黑树实现的。使用红黑树作为底层实现，可以保证查找、插入、删除操作的时间复杂度都是O(logn)级别的。
- 数据库系统索引的实现。在数据库系统中，可以使用红黑树作为底层实现了索引。通过红黑树索引可以快速的进行查找操作，提高了数据库查询效率。
- 操作系统调度算法的实现。在操作系统中，有些进程需要优先级调度，可以使用红黑树来存储这些进程，并按照优先级进行排序。通过红黑树的快速查找，可以提高操作系统的调度效率。
- 代码编辑器中的自动补全功能。在代码编辑器中，可以使用红黑树来实现自动补全功能。通过红黑树的高效查找，可以快速找到与用户正在输入的文本匹配的单词，提高编辑器的使用效率。
总之，红黑树可以应用于各种需要高效查找、插入、删除的场景。
举报
腾讯云开发者
