紅黑樹之插入-創(chuàng)新互聯(lián)
1、紅黑樹
成都創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的札達(dá)網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！(1)、概念
i>每個(gè)結(jié)點(diǎn)不是紅的就是黑的；
ii>根結(jié)點(diǎn)為黑的；
iii>紅結(jié)點(diǎn)的孩子必為黑結(jié)點(diǎn)；
iv>(除了根結(jié)點(diǎn))任一結(jié)點(diǎn)不管通過什么路徑，到達(dá)葉子節(jié)點(diǎn)的黑結(jié)點(diǎn)數(shù)目一定相同；
總結(jié)概括：一頭一腳黑，黑同紅不連：根為黑，到腳(葉子節(jié)點(diǎn))的黑結(jié)點(diǎn)相同，紅結(jié)點(diǎn)不相連；
2、遞歸--->一般先寫if結(jié)束語句
化非遞歸------>用while()循環(huán)和棧;
enum{RED, BLACK}; 這個(gè)枚舉是有值得，分別為0、1；
3、紅黑樹與AVL樹
AVL樹-------->由高度限定平衡，是嚴(yán)格意義上的平衡，絕對(duì)平衡；
RBTree------->由紅黑顏色限定平衡，不是太嚴(yán)格；
4、紅黑樹的插入
全部代碼用C實(shí)現(xiàn)：
(1)、紅黑樹是二叉搜索樹，按二叉搜索樹的大小比較進(jìn)行插入；
(2)、只能插入紅色結(jié)點(diǎn)(黑色的話不滿足黑同)，紅色若相連，通過旋轉(zhuǎn)解決?。。?br />
結(jié)構(gòu)體控制頭：
typedef struct Node{ //紅黑樹結(jié)點(diǎn)類型
Color color; //紅或黑色
Type data; //存儲(chǔ)的數(shù)據(jù)
struct Node *leftChild, *rightChild, *parent; //為了方便操作，左右孩子和父結(jié)點(diǎn)指針
}Node;
typedef struct RBTree{ //紅黑樹類型
Node *root; //根結(jié)點(diǎn)
Node *NIL; //指向一個(gè)空結(jié)點(diǎn)，構(gòu)造了root有父結(jié)點(diǎn);
}RBTree;我的想法是：用一個(gè)指向樹類型的指針，申請(qǐng)一個(gè)樹類型空間，在利用樹類型空間里面的root構(gòu)造一棵樹；
模型示意圖如下：
在產(chǎn)生的結(jié)點(diǎn)中，每個(gè)結(jié)點(diǎn)的左右開始都賦值為NIL；指向空結(jié)點(diǎn)，使root的父為空，便于操作；
只能開始插入時(shí)為紅結(jié)點(diǎn)，最終插入完成，經(jīng)過旋轉(zhuǎn)可為黑色;
對(duì)于要旋轉(zhuǎn)的話，有如下2大種情形：
(1)、錯(cuò)誤的方式
直接將根結(jié)點(diǎn)與左右孩子交換顏色，但是就不滿足根是黑色了;
(2)、正確旋轉(zhuǎn)的兩種方式
i>: 先做一次右單旋轉(zhuǎn)，在交換1結(jié)點(diǎn)和2結(jié)點(diǎn)顏色，如下圖：
ii>:先做一次先左后右的雙旋轉(zhuǎn)，在交換1結(jié)點(diǎn)和4結(jié)點(diǎn)的顏色，如下圖：
先左后右的旋轉(zhuǎn)在這里可以通過：先左旋在右旋實(shí)現(xiàn)；實(shí)際上只寫左和右旋函數(shù)就夠了;
以上的2個(gè)圖在左邊的，實(shí)際上在右邊是為鏡像，一個(gè)道理；
左旋代碼實(shí)現(xiàn)：
void leftRotate(RBTree *t, Node *p){
Node *s = p->rightChild;
p->rightChild = s->leftChild;
if(s->leftChild != t->NIL){
s->leftChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->leftChild = p;
p->parent = s;
}右旋代碼實(shí)現(xiàn)：
void rightRotate(RBTree *t, Node *p){
Node *s = p->leftChild;
p->leftChild = s->rightChild;
if(s->rightChild != t->NIL){
s->rightChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->rightChild = p;
p->parent = s;
}5、插入完整代碼、測(cè)試代碼、測(cè)試結(jié)果
(1)、插入代碼：
#ifndef _RBTREE_H_
#define _RBTREE_H_
#include<malloc.h>
typedef enum{RED, BLACK} Color;
typedef struct Node{
Color color;
Type data;
struct Node *leftChild, *rightChild, *parent;
}Node;
typedef struct RBTree{
Node *root;
Node *NIL;
}RBTree;
Node *createNode(); //創(chuàng)建一個(gè)結(jié)點(diǎn)空間
void initRBTree(RBTree **t); //初始化紅黑樹
void leftRotate(RBTree *t, Node *p); //坐旋轉(zhuǎn)函數(shù)
void rightRotate(RBTree *t, Node *p); //右旋轉(zhuǎn)函數(shù)
void insertFixup(RBTree *t, Node *x); //插入的調(diào)整函數(shù)
bool insert(RBTree *t, Type x); //插入函數(shù)
void showRBTree(RBTree rb); //顯示函數(shù)
void show(RBTree rb, Node *t); //真正的顯示函數(shù)
void show(RBTree rb, Node *t){
if(t != rb.NIL){
show(rb, t->leftChild);
printf("%d : %d\n", t->data, t->color);
show(rb, t->rightChild);
}
}
void showRBTree(RBTree rb){
show(rb, rb.root);
}
bool insert(RBTree *t, Type x){
Node *s = t->root;
Node *p = t->NIL;
while(s != t->NIL){ //找插入位置
p = s;
if(p->data == x){
return false;
}else if(x < p->data){
s = s->leftChild;
}else{
s = s->rightChild;
}
}
Node *q = createNode();
q->data = x;
q->parent = p;
if(p == t->NIL){
t->root = q;
}else if(x < p->data){
p->leftChild = q;
}else{
p->rightChild = q;
}
q->leftChild = t->NIL; //都指向空結(jié)點(diǎn)
q->rightChild = t->NIL;
q->color = RED; //插入結(jié)點(diǎn)顏色為紅
insertFixup(t, q); //調(diào)用一個(gè)調(diào)整函數(shù)
return true;
}
void insertFixup(RBTree *t, Node *x){
Node *s;
while(x->parent->color == RED){
if(x->parent == x->parent->parent->leftChild){ //leftChild
s = x->parent->parent->rightChild;
if(s->color == RED){
x->parent->color = BLACK;
s->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
continue;
}else if(x == x->parent->rightChild){
x = x->parent;
leftRotate(t, x);
}
x->parent->color = BLACK; //交換顏色
x->parent->parent->color = RED;
rightRotate(t, x->parent->parent);
}else{ //rightChild
s = x->parent->parent->leftChild;
if(s->color == RED){
x->parent->color = BLACK;
s->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
continue;
}else if(x == x->parent->leftChild){
x = x->parent;
rightRotate(t, x);
}
x->parent->color = BLACK; //交換顏色
x->parent->parent->color = RED;
leftRotate(t, x->parent->parent);
}
}
t->root->color = BLACK;
}
void rightRotate(RBTree *t, Node *p){
Node *s = p->leftChild;
p->leftChild = s->rightChild;
if(s->rightChild != t->NIL){
s->rightChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->rightChild = p;
p->parent = s;
}
void leftRotate(RBTree *t, Node *p){
Node *s = p->rightChild;
p->rightChild = s->leftChild;
if(s->leftChild != t->NIL){
s->leftChild->parent = p;
}
s->parent = p->parent;
if(p->parent == t->NIL){
t->root = s;
}else if(p == p->parent->leftChild){
p->parent->leftChild = s;
}else{
p->parent->rightChild = s;
}
s->leftChild = p;
p->parent = s;
}
void initRBTree(RBTree **t){
(*t) = (RBTree *)malloc(sizeof(RBTree));
(*t)->NIL = createNode();
(*t)->root = (*t)->NIL;
(*t)->NIL->color = BLACK;
(*t)->NIL->data = -1;
}
Node *createNode(){
Node *p = (Node *)malloc(sizeof(Node));
p->color = BLACK;
p->data = 0;
p->leftChild = p->rightChild = p->parent = NULL;
return p;
}
#endif(2)、測(cè)試代碼：
#include<stdio.h>
typedef int Type;
#include"RBTree.h"
int main(void){
RBTree *rb;
int ar[] = {10, 7, 4, 8, 15, 5, 6, 11, 13, 12,};
//int ar[] = {10, 7, 5};
int n = sizeof(ar)/sizeof(int);
int i;
initRBTree(&rb);
for(i = 0; i < n; i++){
insert(rb, ar[i]);
}
printf("0代表紅，1代表黑\n");
showRBTree(*rb);
return 0;
} (3)、測(cè)試結(jié)果：
6、刪除算法
紅黑樹的刪除思路：
在搜索二叉樹中，永遠(yuǎn)記住刪除結(jié)點(diǎn)，先化為只有左樹或右樹一個(gè)分支在解決；
所以，先找到結(jié)點(diǎn)，在轉(zhuǎn)換為只有一個(gè)分支的，在刪除(只能刪除紅色的結(jié)點(diǎn))，可能通過旋轉(zhuǎn)調(diào)整函數(shù)進(jìn)行平衡！?。?/strong>
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
網(wǎng)頁名稱：紅黑樹之插入-創(chuàng)新互聯(lián)
分享路徑：http://muchs.cn/article18/csgjgp.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、響應(yīng)式網(wǎng)站、網(wǎng)站策劃、網(wǎng)站營銷、關(guān)鍵詞優(yōu)化、企業(yè)建站
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容
- 利用php怎么獲取當(dāng)前時(shí)間的毫秒數(shù)-創(chuàng)新互聯(lián)
- VLAN劃分-創(chuàng)新互聯(lián)
- Kafka緩沖機(jī)制有什么作用-創(chuàng)新互聯(lián)
- 【W(wǎng)indows10】安裝一些更新時(shí)出現(xiàn)問題,但我們稍后會(huì)重試。-創(chuàng)新互聯(lián)
- Hbase的region合并與拆分詳解-創(chuàng)新互聯(lián)
- php讓某ip或ip地址段不能訪問的方法-創(chuàng)新互聯(lián)
- C#中關(guān)于反射和dynamic最佳組合是什么-創(chuàng)新互聯(lián)
- 成都網(wǎng)站建設(shè)：SEO優(yōu)化需要注意的幾個(gè)地方 2022-07-10
- 網(wǎng)站建設(shè)要怎么做才能贏得市場(chǎng) 2022-05-25
- 如何選擇靠譜的泉州網(wǎng)站建設(shè)公司 2020-11-25
- 創(chuàng)新互聯(lián)：網(wǎng)站建設(shè)方案制定后怎樣去評(píng)估 2022-11-23
- 【上海網(wǎng)站建設(shè)】透析定制網(wǎng)站細(xì)說網(wǎng)站建設(shè)流程 2020-11-14
- 成都網(wǎng)站建設(shè)網(wǎng)站增加哪些因素可抓住用戶 2022-08-26
- 成都網(wǎng)站建設(shè)過程中必要細(xì)致哪些地方？ 2015-03-14
- 濱城模板和定制網(wǎng)站建設(shè)有什么區(qū)別？ 2020-12-19
- 深圳網(wǎng)站建設(shè)的流程有哪些 2021-06-06
- 企業(yè)網(wǎng)站建設(shè)必須要了解的操作流程 2022-12-01
- 網(wǎng)站建設(shè)不可忽略的細(xì)節(jié) 2016-11-02
- 網(wǎng)站建設(shè)一般需要多久? 2022-07-12