【数据结构】红黑树（定义性质、插入、查找、删除）解析+完整代码

server/2024/12/2 19:58:40/

3.3 红黑树

3.3.1 定义和性质

  • 为什么发明红黑树？

    平衡二叉树和红黑树的时间复杂度相同，但是平衡二叉树的平衡特性容易被破坏，需要频繁调整树的形态。

    红黑树RBT：插入/删除很多时候不会破坏红黑特性，无需频繁调整树的形态，即需要调整，也可在常数级时间内完成。

    • 平衡二叉树：适用于以查为主，少插入删除的场景；

      红黑树，适用于频繁插入、删除的场景，实用性更强。

  • 定义

    • 红黑树是二叉排序树 ==》左子树结点<=根结点<= 右子树结点

    • 与普通BST相比，有什么要求？ ==》

      1.每个结点不是红色就是黑色；

      2.根结点是黑色；

      3.叶结点（外部结点、NULL结点、失败结点）均是黑色；

      4.不存在连续两个红色结点（父子不能同为红色）；

      5.对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同。

    • 黑高

      结点的黑高bh——从某结点出发（不含该结点），到达任一空叶结点的路径上黑结点总数。

  • 性质

    1.从根结点到叶结点的最长路径不大于最短路径的2倍；

    证明：任何一条查找失败路径上黑结点数都相同，而路径上不能连续出现两个红结点，即红结点只能穿插在各个黑结点中间。

    ​ 则最长路径为红结点穿插在黑结点间，最短路径是没有红结点。

    2.有n个内部节点的红黑树高度 h < = 2 l o g 2 ( n + 1 ) h<=2log_2(n+1) h<=2log2​(n+1)

    ​ ==》 红黑树查找操作时间复杂度 O ( l o g 2 n ) O(log_2n) O(log2​n)

    证明：若红黑树总高度=h，则根结点黑高>=h/2，因此内部结点数 n > = 2 h / 2 − 1 n>=2^{h/2}-1 n>=2h/2−1，由此推出 h < = 2 l o g 2 ( n + 1 ) h<=2log_2(n+1) h<=2log2​(n+1)

  • 与黑高相关的推论

    • 根结点黑高为h的红黑树，内部结点数（关键字）至少有多少个？

      内部结点数最少的情况——总共h层黑结点的满树形态。

      结论：若根结点黑高为h，内部结点数（包含关键字的结点）最少有 2 h − 1 2^h-1 2h−1个

      在这里插入图片描述

3.3.2 查找
  • 与BST、AVL相同，从根出发，左小右大，若查找到一个空叶结点，则查找失败。
3.3.3 插入

  • 方法

    • 先查找，确定插入位置（原理同二叉排序树），插入新结点；

    • 若新结点是根——染黑色；

    • 若新结点非根——染为红色；

      • 若插入新结点后依然满足红黑树定义，则插入结束
      • 若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义
        • 黑叔：旋转+染色
          • LL型：右单旋，父换爷+染色
          • RR型：左单旋，父换爷+染色
          • LR型：左右双旋，儿换爷+染色
          • RL型：右左双旋，儿换爷+染色
        • 红叔：染色+变新

    在这里插入图片描述

  • 口诀

    左根右——RBT是一种BST，需满足左<根<右

    根叶黑——根结点和叶结点一定是黑色

    不红红——任何一条查找路径上不能连续出现两个红结点

    黑路同——从任一结点出发，达到任一空叶结点的路径上经过的黑结点数量相同

  • 例题

    在这里插入图片描述

    • 插入20

      把20作为根结点插入，并且满足根结点为黑的特性，把该结点染黑。

    在这里插入图片描述

    • 插入10

      因为新结点是非根结点，为了满足任一路径上黑结点数相同，所以染为红色插入。

    • 插入5

      新结点是非根结点，染成红色插入，

      但是违反了父子不能同为红的特性，所以要看叔叔结点是什么颜色；

      叔叔结点是黑色（黑叔），则要进行旋转+染色；

      因为新结点是LL型，所以旋转时遵循右单旋，父换爷；

      旋转后，根据红黑树特性染色。

    • 插入30

      新结点插入后违反父子不能同为红的特性，

      叔叔是红色（红叔），则遵循染色+变新，即叔父爷染色（改变颜色），爷变成新结点。

    • 插入40

      插入后违反父子不能同为红的特性；

      叔叔是黑色，新结点是RR型，

      则要左单旋，父换爷+染色

    • 插入57

    • 插入3

      不会破坏特性，所以不需要变

    • 插入2

    • 最后结果

3.3.4 删除

  • 重点

    1.红黑树删除操作的时间复杂度= O ( l o g 2 n ) O(log_2n) O(log2​n)；

    2.在红黑树中删除结点的处理方式和二叉排序树的一样；

    3.按第2步删除结点后，可能破坏红黑树特性，此时需要调整结点颜色、位置，使其再次满足红黑树特性。

*完整代码 红黑树
#include <stdio.h>
#include <stdlib.h>#define RED 0
#define BLACK 1// 定义红黑树节点的结构
struct Node {int data;           // 节点存储的数据int color;          // 节点的颜色，红色为0，黑色为1struct Node *left, *right, *parent;    // 左子节点、右子节点、父节点指针
};typedef struct Node Node;    // 将结构体 Node 重命名为 Node// 创建一个新节点，并初始化数据
Node* createNode(int data) {// 分配内存空间给新节点Node* newNode = (Node*)malloc(sizeof(Node));// 初始化新节点的数据和颜色（红色）newNode->data = data;newNode->color = RED;// 将左右子节点和父节点指针都设置为 NULLnewNode->left = newNode->right = newNode->parent = NULL;return newNode;
}// 在给定节点处执行左旋转
void rotateLeft(Node **root, Node *x) {// 将 x 的右子节点保存在 y 中Node *y = x->right;// 将 x 的右子节点设置为 y 的左子节点x->right = y->left;// 如果 y 的左子节点非空，则更新其父节点指针指向 xif (y->left != NULL)y->left->parent = x;// 将 y 的父节点指针指向 x 的父节点y->parent = x->parent;// 如果 x 是根节点，则将根节点更新为 yif (x->parent == NULL)(*root) = y;// 如果 x 是其父节点的左子节点，则将 y 设为 x 的父节点的左子节点else if (x == x->parent->left)x->parent->left = y;// 如果 x 是其父节点的右子节点，则将 y 设为 x 的父节点的右子节点elsex->parent->right = y;// 将 x 设为 y 的左子节点y->left = x;// 将 x 的父节点设为 yx->parent = y;
}// 在给定节点处执行右旋转
void rotateRight(Node **root, Node *y) {// 将 y 的左子节点保存在 x 中Node *x = y->left;// 将 y 的左子节点设置为 x 的右子节点y->left = x->right;// 如果 x 的右子节点非空，则更新其父节点指针指向 yif (x->right != NULL)x->right->parent = y;// 将 x 的父节点指针指向 y 的父节点x->parent = y->parent;// 如果 y 是根节点，则将根节点更新为 xif (y->parent == NULL)(*root) = x;// 如果 y 是其父节点的左子节点，则将 x 设为 y 的父节点的左子节点else if (y == y->parent->left)y->parent->left = x;// 如果 y 是其父节点的右子节点，则将 x 设为 y 的父节点的右子节点elsey->parent->right = x;// 将 y 设为 x 的右子节点x->right = y;// 将 y 的父节点设为 xy->parent = x;
}// 修正插入操作可能导致的红黑树性质违反
void fixViolation(Node **root, Node *z) {// 当插入节点不是根节点且父节点为红色时，需要进行修正while (z != *root && z->parent->color == RED) {// 当父节点是祖父节点的左子节点时if (z->parent == z->parent->parent->left) {Node *y = z->parent->parent->right; // 获取叔父节点// 当叔父节点存在且为红色时，进行情况1的处理if (y != NULL && y->color == RED) {z->parent->color = BLACK; // 将父节点设为黑色y->color = BLACK; // 将叔父节点设为黑色z->parent->parent->color = RED; // 将祖父节点设为红色z = z->parent->parent; // 将 z 移动到祖父节点处} else {// 当叔父节点不存在或为黑色时，进行情况2的处理if (z == z->parent->right) { // 如果 z 是父节点的右子节点z = z->parent; // 将 z 移动到父节点处rotateLeft(root, z); // 左旋转}z->parent->color = BLACK; // 将父节点设为黑色z->parent->parent->color = RED; // 将祖父节点设为红色rotateRight(root, z->parent->parent); // 右旋转}} else { // 当父节点是祖父节点的右子节点时，与上述情况对称Node *y = z->parent->parent->left;if (y != NULL && y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else {if (z == z->parent->left) {z = z->parent;rotateRight(root, z);}z->parent->color = BLACK;z->parent->parent->color = RED;rotateLeft(root, z->parent->parent);}}}(*root)->color = BLACK; // 将根节点设为黑色
}// 插入新节点到红黑树中
void insert(Node **root, int data) {Node *newNode = createNode(data); // 创建新节点Node *parent = NULL;Node *current = *root;while (current != NULL) { // 寻找插入位置parent = current;if (newNode->data < current->data)current = current->left;elsecurrent = current->right;}newNode->parent = parent; // 设置新节点的父节点if (parent == NULL)*root = newNode; // 如果树为空，则将新节点设为根节点else if (newNode->data < parent->data)parent->left = newNode; // 如果新节点值小于父节点值，则设为左子节点elseparent->right = newNode; // 否则设为右子节点fixViolation(root, newNode); // 修正插入可能导致的红黑树性质违反
}// 在红黑树中查找指定值的节点
Node* search(Node *root, int data) {while (root != NULL) {if (data < root->data)root = root->left; // 在左子树中查找else if (data > root->data)root = root->right; // 在右子树中查找elsereturn root; // 找到节点}return NULL; // 未找到节点
}// 寻找以给定节点为根的子树中的最小值节点
Node* minValueNode(Node* node) {Node* current = node;while (current->left != NULL)current = current->left; // 不断向左遍历直到最左叶节点return current; // 返回最小值节点
}// 修正双黑节点情况
void fixDoubleBlack(Node **root, Node *x) {if (x == *root) // 如果 x 是根节点，直接返回return;Node *sibling = NULL; // 声明一个指向兄弟节点的指针while (x != *root && x->color == BLACK) { // 当 x 不是根节点且颜色为黑色时执行循环if (x == x->parent->left) { // 如果 x 是父节点的左子节点sibling = x->parent->right; // 获取兄弟节点if (sibling->color == RED) { // 如果兄弟节点为红色sibling->color = BLACK; // 将兄弟节点设为黑色x->parent->color = RED; // 将父节点设为红色rotateLeft(root, x->parent); // 左旋转sibling = x->parent->right; // 更新兄弟节点}if (sibling->left->color == BLACK && sibling->right->color == BLACK) { // 如果兄弟节点的两个子节点都为黑色sibling->color = RED; // 将兄弟节点设为红色x = x->parent; // 将 x 移动到父节点处} else {if (sibling->right->color == BLACK) { // 如果兄弟节点的右子节点为黑色sibling->left->color = BLACK; // 将兄弟节点的左子节点设为黑色sibling->color = RED; // 将兄弟节点设为红色rotateRight(root, sibling); // 右旋转sibling = x->parent->right; // 更新兄弟节点}sibling->color = x->parent->color; // 将兄弟节点的颜色设为父节点的颜色x->parent->color = BLACK; // 将父节点设为黑色sibling->right->color = BLACK; // 将兄弟节点的右子节点设为黑色rotateLeft(root, x->parent); // 左旋转x = *root; // 将 x 设为根节点}} else { // 如果 x 是父节点的右子节点，与上述情况对称sibling = x->parent->left;if (sibling->color == RED) {sibling->color = BLACK;x->parent->color = RED;rotateRight(root, x->parent);sibling = x->parent->left;}if (sibling->right->color == BLACK && sibling->left->color == BLACK) {sibling->color = RED;x = x->parent;} else {if (sibling->left->color == BLACK) {sibling->right->color = BLACK;sibling->color = RED;rotateLeft(root, sibling);sibling = x->parent->left;}sibling->color = x->parent->color;x->parent->color = BLACK;sibling->left->color = BLACK;rotateRight(root, x->parent);x = *root;}}}x->color = BLACK; // 将最终 x 设为黑色
}// 替换节点
void transplant(Node **root, Node *u, Node *v) {if (u->parent == NULL) // 如果 u 是根节点*root = v; // 将根节点设为 velse if (u == u->parent->left) // 如果 u 是其父节点的左子节点u->parent->left = v; // 将 v 设为其父节点的左子节点else // 如果 u 是其父节点的右子节点u->parent->right = v; // 将 v 设为其父节点的右子节点if (v != NULL) // 如果 v 不为空v->parent = u->parent; // 将 v 的父节点设为 u 的父节点
}// 删除节点函数
void deleteNode(Node **root, int data) {Node *z = search(*root, data); // 在树中查找值为 data 的节点if (z == NULL) { // 如果未找到节点printf("Node with value %d not found\n", data); // 输出未找到节点的信息return; // 返回}Node *y = z; // 将 y 设为 zNode *x; // 声明一个指向后继节点的指针 xint yOriginalColor = y->color; // 保存 y 的颜色if (z->left == NULL) { // 如果 z 的左子节点为空x = z->right; // 将 x 设为 z 的右子节点transplant(root, z, z->right); // 将 z 替换为其右子节点} else if (z->right == NULL) { // 如果 z 的右子节点为空x = z->left; // 将 x 设为 z 的左子节点transplant(root, z, z->left); // 将 z 替换为其左子节点} else { // 如果 z 既有左子节点又有右子节点y = minValueNode(z->right); // 找到 z 的右子树中的最小值节点 yyOriginalColor = y->color; // 保存 y 的颜色x = y->right; // 将 x 设为 y 的右子节点if (y->parent == z) // 如果 y 是 z 的直接子节点x->parent = y; // 将 x 的父节点设为 yelse {transplant(root, y, y->right); // 将 y 替换为其右子节点y->right = z->right; // 将 y 的右子节点设为 z 的右子节点y->right->parent = y; // 更新 y 的右子节点的父节点}transplant(root, z, y); // 将 z 替换为 yy->left = z->left; // 将 y 的左子节点设为 z 的左子节点y->left->parent = y; // 更新 y 的左子节点的父节点y->color = z->color; // 将 y 的颜色设为 z 的颜色}if (yOriginalColor == BLACK) // 如果 y 的原始颜色为黑色fixDoubleBlack(root, x); // 修正双黑节点情况free(z); // 释放删除的节点的内存
}// 中序遍历函数
void inorder(Node *root) {if (root == NULL) // 如果根节点为空return; // 返回inorder(root->left); // 递归遍历左子树printf("%d ", root->data); // 输出当前节点的值inorder(root->right); // 递归遍历右子树
}int main() {Node *root = NULL;insert(&root, 7);insert(&root, 3);insert(&root, 18);insert(&root, 10);insert(&root, 22);insert(&root, 8);insert(&root, 11);insert(&root, 26);insert(&root, 2);insert(&root, 6);insert(&root, 13);printf("Inorder traversal of the tree: ");inorder(root);printf("\n");deleteNode(&root, 18);printf("Inorder traversal after deletion of 18: ");inorder(root);printf("\n");int searchData = 10;Node *searchResult = search(root, searchData);if (searchResult != NULL)printf("%d found in the tree.\n", searchData);elseprintf("%d not found in the tree.\n", searchData);int searchData2 = 18;Node *searchResult2 = search(root, searchData2);if (searchResult2 != NULL)printf("%d found in the tree.\n", searchData2);elseprintf("%d not found in the tree.\n", searchData2);return 0;
}

http://www.ppmy.cn/server/41787.html

相关文章

C++初探_类模板

C++初探_类模板

1.定义与使用 代码&#xff1a; #include <iostream> using namespace std;template <class Type> // class 为变量类型名&#xff0c;Type为变量&#xff0c;是个泛型标识符 class Stack { private:enum {MAX 10};Type items[MAX];... public:Stock(); };templ…
阅读更多...
制作跳动的爱心网页效果

制作跳动的爱心网页效果

html <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>跳动的爱心</title> <link rel&q…
阅读更多...
AI视频教程下载：用ChatGPT制作 YouTube视频的指南

AI视频教程下载：用ChatGPT制作 YouTube视频的指南

课程大纲&#xff1a; 面向 YouTuber 的 ChatGPT YouTube关键词研究 YouTube标题 YouTube缩略图 YouTube社区帖子 组织您的 YouTube 视频 本课程将通过两个不同领域的YouTube视频&#xff0c;展示如何使用Chat GPT来创建关键词、标题、缩略图、描述和社区帖子。 关键词研…
阅读更多...
第二天：深入部署与配置

第二天：深入部署与配置

探索Docker世界&#xff1a;深入部署与配置 引言一、Docker深入部署二、Docker配置与优化三、实践案例四、总结 引言 经过第一天的Docker基础学习&#xff0c;我们已经对Docker有了初步的认识。今天&#xff0c;我们将进一步深化对Docker部署的理解&#xff0c;探讨如何在实际…
阅读更多...
【Java基础】权限修饰符

【Java基础】权限修饰符

一个java文件中只能有一个被public修饰的类&#xff0c;且该类名与java文件的名字一样 同一个类同一个包不同包有继承不同包无继承private✔❌❌❌默认✔✔❌❌protected✔✔✔❌public✔✔✔✔
阅读更多...
【Golang】 在 Gin 框架中添加网关中间件

【Golang】 在 Gin 框架中添加网关中间件

文章目录 前言一、*gin.Engine 解释二、代码实现三、总结 前言 在 Web 开发中&#xff0c;网关是一个重要的组件&#xff0c;它可以用来处理跨域请求&#xff0c;负载均衡&#xff0c;认证&#xff0c;日志记录&#xff0c;请求限速等。在使用 Go 语言的 Gin 框架进行开发时&a…
阅读更多...
C#反编译太容易了，转qt怎么样?

C#反编译太容易了，转qt怎么样?

在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「qt的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01;方案1&#xff1a;随机报错 反编都…
阅读更多...
IPsec VPN简介

IPsec VPN简介

什么是IPsec&#xff1f; IPsec&#xff08;Internet Protocol Security&#xff09;是为IP网络提供安全性的协议和服务的集合&#xff0c;它是VPN&#xff08;Virtual Private Network&#xff0c;虚拟专用网&#xff09;中常用的一种技术。其实就是一种协议簇&#xff08;类…
阅读更多...
最新文章

Copyright @ 2022~2023