C++實(shí)現(xiàn)紅黑樹(shù)應(yīng)用實(shí)例代碼
更新時(shí)間：2021年11月01日 15:03:41 作者：去偽存真
紅黑樹(shù)它一種特殊的二叉查找樹(shù),這意味著它滿(mǎn)足二叉查找樹(shù)的特征,但是也有許多自己的特性,這篇文章主要給大家介紹了關(guān)于C++實(shí)現(xiàn)紅黑樹(shù)的相關(guān)資料,需要的朋友可以參考下
紅黑樹(shù)的應(yīng)用：
1、利用key_value對(duì)，快速查找，O(logn)
- socket與客戶(hù)端id之間，形成映射關(guān)系(socket, id)
- 內(nèi)存分配管理
- 一整塊內(nèi)存，不斷分配小塊
- 每分配一次，就加入到紅黑樹(shù)
- 釋放的時(shí)候，在紅黑樹(shù)找到相應(yīng)的塊，然后去釋放
2、利用紅黑樹(shù)中序遍歷是順序的特性
- 進(jìn)程的調(diào)度
- 進(jìn)程處于等待狀態(tài)，每個(gè)進(jìn)程都有等待的時(shí)間，在未來(lái)某個(gè)時(shí)刻會(huì)運(yùn)行，將這些進(jìn)程利用紅黑樹(shù)組織起來(lái)
- 在某個(gè)時(shí)刻，找到對(duì)應(yīng)時(shí)刻的節(jié)點(diǎn)，然后中序遍歷，就可以把該節(jié)點(diǎn)之前的節(jié)點(diǎn)全部運(yùn)行到。
3、nginx定時(shí)器
為什么使用紅黑樹(shù)不使用哈希表？
- 極少情況下，需要key是有序的，如定時(shí)器
二叉排序樹(shù)（bstree）
- 左子樹(shù) < 根 < 右子樹(shù)
- 中序遍歷結(jié)果是順序的
- 極端情況下，如果順序插入，結(jié)果就成了鏈表
- 為了解決這個(gè)問(wèn)題，引入了紅黑樹(shù)
- 為了解決這個(gè)問(wèn)題，引入了紅黑樹(shù)
紅黑樹(shù)性質(zhì)
- 每個(gè)節(jié)點(diǎn)是紅色的或黑色的
- 根節(jié)點(diǎn)是黑色的
- 葉子節(jié)點(diǎn)是黑色的
- 紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)必須是黑色的
- 對(duì)每個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)到其子孫節(jié)點(diǎn)的所有路徑上的包含相同數(shù)目的黑節(jié)點(diǎn)（黑高相同）
- 最短路徑就是全黑
- 最長(zhǎng)路徑就是黑紅相間
如何證明紅黑樹(shù)的正確性？
- 采用歸納法
左旋與右旋
- 改變?nèi)齻€(gè)方向，六根指針
紅黑樹(shù)的插入：
- 插入節(jié)點(diǎn)的時(shí)候，原先的樹(shù)是滿(mǎn)足紅黑樹(shù)性質(zhì)的
- 插入節(jié)點(diǎn)的顏色是紅色更容易滿(mǎn)足紅黑樹(shù)的性質(zhì)
- 插入的節(jié)點(diǎn)是紅色，且其父節(jié)點(diǎn)也是紅色的時(shí)候，需要調(diào)整
插入有三種情況：
- 叔父節(jié)點(diǎn)是紅色
- 叔父節(jié)點(diǎn)是黑色，且祖父節(jié)點(diǎn)，父節(jié)點(diǎn)和插入節(jié)點(diǎn)不是一條直線(xiàn)
- 叔父節(jié)點(diǎn)是黑色，且祖父節(jié)點(diǎn)，父節(jié)點(diǎn)和插入節(jié)點(diǎn)是一條直線(xiàn)
平衡二叉樹(shù)：
- 內(nèi)部不是color，而是一個(gè)high記錄高度，如果左右子樹(shù)高度相差超過(guò)1，就需要調(diào)整。
紅黑樹(shù)的刪除：
- 什么是刪除節(jié)點(diǎn)? y-> y是z的后繼節(jié)點(diǎn)
- 什么是軸心節(jié)點(diǎn)? x是y的右子樹(shù)
- 如果x是紅色，把x變成黑色
- 如果x是黑色，需要進(jìn)行調(diào)整
刪除y節(jié)點(diǎn)，是什么顏色的時(shí)候需要調(diào)整？
- 黑色需要調(diào)整，刪除黑色破壞了黑高
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define RED 1
#define BLACK 2
typedef int KEY_TYPE;
typedef struct _rbtree_node {
unsigned char color;
struct _rbtree_node *right;
struct _rbtree_node *left;
struct _rbtree_node *parent;
KEY_TYPE key;
void *value;
} rbtree_node;
typedef struct _rbtree {
rbtree_node *root;
rbtree_node *nil;
} rbtree;
rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {
while (x->left != T->nil) {
x = x->left;
}
return x;
}
rbtree_node *rbtree_maxi(rbtree *T, rbtree_node *x) {
while (x->right != T->nil) {
x = x->right;
}
return x;
}
rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {
rbtree_node *y = x->parent;
if (x->right != T->nil) {
return rbtree_mini(T, x->right);
}
while ((y != T->nil) && (x == y->right)) {
x = y;
y = y->parent;
}
return y;
}
void rbtree_left_rotate(rbtree *T, rbtree_node *x) {
rbtree_node *y = x->right; // x --> y , y --> x, right --> left, left --> right
x->right = y->left; //1 1
if (y->left != T->nil) { //1 2
y->left->parent = x;
}
y->parent = x->parent; //1 3
if (x->parent == T->nil) { //1 4
T->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x; //1 5
x->parent = y; //1 6
}
void rbtree_right_rotate(rbtree *T, rbtree_node *y) {
rbtree_node *x = y->left;
y->left = x->right;
if (x->right != T->nil) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == T->nil) {
T->root = x;
} else if (y == y->parent->right) {
y->parent->right = x;
} else {
y->parent->left = x;
}
x->right = y;
y->parent = x;
}
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {
while (z->parent->color == RED) { //z ---> RED
if (z->parent == z->parent->parent->left) {
rbtree_node *y = z->parent->parent->right;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent; //z --> RED
} else {
if (z == z->parent->right) {
z = z->parent;
rbtree_left_rotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rbtree_right_rotate(T, z->parent->parent);
}
}else {
rbtree_node *y = z->parent->parent->left;
if (y->color == RED) {
z->parent->color = BLACK;
y->color = BLACK;
z->parent->parent->color = RED;
z = z->parent->parent; //z --> RED
} else {
if (z == z->parent->left) {
z = z->parent;
rbtree_right_rotate(T, z);
}
z->parent->color = BLACK;
z->parent->parent->color = RED;
rbtree_left_rotate(T, z->parent->parent);
}
}
}
T->root->color = BLACK;
}
void rbtree_insert(rbtree *T, rbtree_node *z) {
rbtree_node *y = T->nil;
rbtree_node *x = T->root;
while (x != T->nil) {
y = x;
if (z->key < x->key) {
x = x->left;
} else if (z->key > x->key) {
x = x->right;
} else { //Exist
return ;
}
}
z->parent = y;
if (y == T->nil) {
T->root = z;
} else if (z->key < y->key) {
y->left = z;
} else {
y->right = z;
}
z->left = T->nil;
z->right = T->nil;
z->color = RED;
rbtree_insert_fixup(T, z);
}
void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {
while ((x != T->root) && (x->color == BLACK)) {
if (x == x->parent->left) {
rbtree_node *w= x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rbtree_left_rotate(T, x->parent);
w = x->parent->right;
}
if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rbtree_right_rotate(T, w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
rbtree_left_rotate(T, x->parent);
x = T->root;
}
} else {
rbtree_node *w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rbtree_right_rotate(T, x->parent);
w = x->parent->left;
}
if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
rbtree_left_rotate(T, w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rbtree_right_rotate(T, x->parent);
x = T->root;
}
}
}
x->color = BLACK;
}
rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {
rbtree_node *y = T->nil;
rbtree_node *x = T->nil;
if ((z->left == T->nil) || (z->right == T->nil)) {
y = z;
} else {
y = rbtree_successor(T, z);
}
if (y->left != T->nil) {
x = y->left;
} else if (y->right != T->nil) {
x = y->right;
}
x->parent = y->parent;
if (y->parent == T->nil) {
T->root = x;
} else if (y == y->parent->left) {
y->parent->left = x;
} else {
y->parent->right = x;
}
if (y != z) {
z->key = y->key;
z->value = y->value;
}
if (y->color == BLACK) {
rbtree_delete_fixup(T, x);
}
return y;
}
rbtree_node *rbtree_search(rbtree *T, KEY_TYPE key) {
rbtree_node *node = T->root;
while (node != T->nil) {
if (key < node->key) {
node = node->left;
} else if (key > node->key) {
node = node->right;
} else {
return node;
}
}
return T->nil;
}
void rbtree_traversal(rbtree *T, rbtree_node *node) {
if (node != T->nil) {
rbtree_traversal(T, node->left);
printf("key:%d, color:%d\n", node->key, node->color);
rbtree_traversal(T, node->right);
}
}
int main() {
int keyArray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15};
rbtree *T = (rbtree *)malloc(sizeof(rbtree));
if (T == NULL) {
printf("malloc failed\n");
return -1;
}
T->nil = (rbtree_node*)malloc(sizeof(rbtree_node));
T->nil->color = BLACK;
T->root = T->nil;
rbtree_node *node = T->nil;
int i = 0;
for (i = 0;i < 20;i ++) {
node = (rbtree_node*)malloc(sizeof(rbtree_node));
node->key = keyArray[i];
node->value = NULL;
rbtree_insert(T, node);
}
rbtree_traversal(T, T->root);
printf("----------------------------------------\n");
for (i = 0;i < 20;i ++) {
rbtree_node *node = rbtree_search(T, keyArray[i]);
rbtree_node *cur = rbtree_delete(T, node);
free(cur);
rbtree_traversal(T, T->root);
printf("----------------------------------------\n");
}
}
總結(jié)
到此這篇關(guān)于C++實(shí)現(xiàn)紅黑樹(shù)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)紅黑樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- C++詳細(xì)實(shí)現(xiàn)紅黑樹(shù)流程詳解
- C++?STL容器詳解之紅黑樹(shù)部分模擬實(shí)現(xiàn)
- C++數(shù)據(jù)結(jié)構(gòu)之紅黑樹(shù)的實(shí)現(xiàn)
- C++超詳細(xì)分析紅黑樹(shù)
- C++數(shù)據(jù)結(jié)構(gòu)紅黑樹(shù)全面分析
- C++?RBTree紅黑樹(shù)的性質(zhì)與實(shí)現(xiàn)
- C++使用一棵紅黑樹(shù)同時(shí)封裝出map和set實(shí)例代碼
- C++紅黑樹(shù)應(yīng)用之手搓set和map
- C++實(shí)現(xiàn)紅黑樹(shù)核心插入實(shí)例代碼
相關(guān)文章
這篇文章主要介紹了while和for可以相互轉(zhuǎn)換的例子,需要的朋友可以參考下2014-02-02
在了解內(nèi)存分區(qū)之前，我們先來(lái)聊一聊為什么要進(jìn)行內(nèi)存分區(qū)。在進(jìn)行了內(nèi)存分區(qū)之后，在不同的區(qū)域存放的數(shù)據(jù)，會(huì)有不同的生命周期，從而會(huì)讓程序員的編程變得更加靈活2022-09-09
本文主要介紹了QT中對(duì)Mat類(lèi)的一些操作詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06
詳解C++的反調(diào)試技術(shù)與繞過(guò)手法
反調(diào)試技術(shù)，惡意代碼會(huì)用它識(shí)別自身是否被調(diào)試，或者讓調(diào)試器失效，給反病毒工程師們制造麻煩，拉長(zhǎng)提取特征碼的時(shí)間線(xiàn)，本章將具體總結(jié)常見(jiàn)的反調(diào)試基礎(chǔ)的實(shí)現(xiàn)原理以及如何過(guò)掉這些反調(diào)試手段，從而讓我們能夠繼續(xù)分析惡意代碼2021-06-06
std::is_object是一種C++類(lèi)型特性,其用途是判斷一個(gè)類(lèi)型是否是一個(gè)對(duì)象類(lèi)型,本文主要介紹了C++中std::is_object的具體使用,感興趣的可以了解一下2024-01-01
本篇文章是對(duì)紅黑樹(shù)的使用詳解。需要的朋友參考下2013-05-05
今天小編就為大家分享一篇關(guān)于C++中箭頭運(yùn)算符的含義與用法講解，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-04-04
利用反射獲得類(lèi)的public static/const成員的值實(shí)例
下面小編就為大家?guī)?lái)一篇利用反射獲得類(lèi)的public static/const成員的值實(shí)例。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-12-12
C語(yǔ)言統(tǒng)計(jì)一篇英文短文中單詞的個(gè)數(shù)實(shí)例代碼
本文通過(guò)實(shí)例代碼給大家介紹的C語(yǔ)言統(tǒng)計(jì)一篇英文短文中單詞的個(gè)數(shù)，代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友參考下吧2018-03-03
Qt實(shí)現(xiàn)SqlRelationalTable關(guān)聯(lián)表組件
在Qt中我們可以通過(guò)拖拽的方式將不同組件放到指定的位置,實(shí)現(xiàn)圖形化開(kāi)發(fā)極大的方便了開(kāi)發(fā)效率,本章將重點(diǎn)介紹SqlRelationalTable關(guān)聯(lián)表組件的常用方法及靈活運(yùn)用,感興趣的可以了解一下2023-12-12