데이터 구조의 - 레 드 블랙 트 리 의 실현 (C 언어 버 전)
13645 단어 c이 진 트 리두 갈래 찾기 트 리검 붉 은 나무
붉 은 검 은 나 무 는 많은 '균형 트 리' 중의 하나 로 다른 경로 보다 2 배 정도 긴 경로 가 없 기 때문에 균형 에 가깝다.
빨간색 과 검은색 트 리 의 데이터 구조 와 조작 정 의 는 다음 과 같다.
/*file:RBTree.h*/
#ifndef CHIYX_RBTREE_
#define CHIYX_RBTREE_
#ifndef NULL
#define NULL 0
#endif
#define BOOL int
#define TRUE 1
#define FALSE 0
/*
* ：
* (1)
* (2)
* (3) （ NULL ）
* (4) ，
* (5) ，
*/
/*
* ( ):
* n （ ） bh 2lg(n+1)
* : ： x 2(hb(x))( ) - 1
* (1) x 0， x 2 0 - 1 = 0 ， 。
* (2) x ， bh(x) （ ）， bh(x) -1（ ）
* (3) x x ， ， 2 bh(x) -1 - 1
* (4) x 2 (bh(x) -1 ) - 1 + 2 (bh(x) -1 ) - 1 + 1 = 2 (bh(x) ) - 1
* （4）， h / 2 , n >= 2 (h / 2 ) - 1 => h <= 2 lg (n - 1)
*/
/* */
typedef enum color_t {
RED = 0,
BLACK = 1
}color_t;
//
typedef int data_t;
//
typedef struct RBTreeNode {
data_t data;
color_t color;
RBTreeNode *left;
RBTreeNode *right;
RBTreeNode *parent;
}RBTreeNode, *RBTree;
// ， NULL
RBTreeNode *rbSearch(RBTree *rbTree, data_t key);
//
RBTreeNode *rbMinImum(RBTree *rbTree);
//
RBTreeNode *rbMaxImum(RBTree *rbTree);
// x
RBTreeNode *rbSuccessor(RBTreeNode *x);
// x
RBTreeNode *rbPredecessor(RBTreeNode *x);
//
BOOL rbInsertNode(RBTree *rbTree, data_t data);
// data
BOOL rbDeleteNode(RBTree *rbTree, data_t data);
//
void rbInorderTraversal(RBTree *rbTree, void (*visitor)(RBTreeNode *node));
#endif
빨간색 과 검은색 트 리 작업 중 삽입 과 찾기 만 일반 2 진 트 리 와 다 르 게 해 야 합 니 다. 삽입 과 찾기 의 실현 을 보 여 줍 니 다.
/*
* , x
*/
static void rbTreeLeftRotate(RBTree *rbTree, RBTreeNode *x);
/*
* , x
*/
static void rbTreeRightRotate(RBTree *rbTree, RBTreeNode *x);
/*
* ，
*/
static void rbTreeInsertFixup(RBTree *rbTree, RBTreeNode *x);
/*
* ，
*/
static void rbTreeDeleteFixup(RBTree *rbTree, RBTreeNode *parent, RBTreeNode *x);
//
//1. ，
//2. ， ， ，
BOOL rbInsertNode(RBTree *rbTree, data_t data) {
//1.
RBTreeNode *node, *p, *curNode;
node = (RBTreeNode *)malloc(sizeof(RBTreeNode));
if (node == NULL) return FALSE;
node->data = data;
node->color = RED;
node->left = NULL;
node->right = NULL;
curNode = *rbTree;
// , p
p = NULL;
while (curNode != NULL) {
p = curNode;
if (data < curNode->data) {
curNode = curNode->left;
} else {
curNode = curNode->right;
}
}
//
if (p == NULL) {
*rbTree = node;
} else {
if (data < p->data) {
p->left = node;
} else {
p->right = node;
}
}
node->parent = p;
// ： ，
rbTreeInsertFixup(rbTree, node);
return TRUE;
}
BOOL rbDeleteNode(RBTree *rbTree, data_t data) {
RBTreeNode *target, *realDel, *child;
target = rbSearch(rbTree, data);
if (target != NULL) {
//
if (target->left == NULL || target->right == NULL) {
realDel = target;
} else {
realDel = rbSuccessor(target);
}
// ，
if (realDel->left != NULL) {
child = realDel->left;
} else {
child = realDel->right;
}
if (child != NULL) {
child->parent = realDel->parent;
}
if (realDel->parent == NULL) {
*rbTree = child;
} else {
if (realDel->parent->left == realDel) {
realDel->parent->left = child;
} else {
realDel->parent->right = child;
}
}
if (target != realDel) {
target->data = realDel->data;
}
//
if (realDel->color == BLACK) {
rbTreeDeleteFixup(rbTree, realDel->parent, child);
}
free(realDel);
return TRUE;
} else {
return FALSE;
}
}
/*
* 。 （4） ，
* （2）
*/
static void rbTreeInsertFixup(RBTree *rbTree, RBTreeNode *x) {
RBTreeNode *p, *gparent, *uncle;
// 2
while ((p = x->parent) != NULL && p->color == RED){
gparent = p->parent;
// （ ， ）
if (p == gparent->left) {
uncle = gparent->right;
// 1： ， ， ，
// ， x
if (uncle != NULL && uncle->color == RED) {
gparent->color = RED;
p->color = BLACK;
uncle->color = BLACK;
x = gparent;
}
// ， 2
else {
// 2：x ， 3
if (x == p->right) {
// x ， x x‘
x = p;
rbTreeLeftRotate(rbTree, x);
// ， x， x （ x’）
p = x->parent;
}
// ：x ， ， 4， 5
p->color = BLACK;
gparent->color = RED;
// 5
rbTreeRightRotate(rbTree, gparent);
// x->parent->color = BLACK,
}
}
//
else {
uncle = gparent->left;
// 1： ， ， ，
// ， x
if (uncle != NULL && uncle->color == RED) {
gparent->color = RED;
p->color = BLACK;
uncle->color = BLACK;
x = gparent;
}
// 2 3
else {
// 2：x ， 3
if (x == p->left) {
x = p;
rbTreeRightRotate(rbTree, x);
p = x->parent;
}
// ：x ， ， 4， 5
p->color = BLACK;
gparent->color = RED;
// 5
rbTreeLeftRotate(rbTree, gparent);
// x->parent->color = BLACK,
}
}
}
// 2
(*rbTree)->color = BLACK;
}
/*
* ：
* （1） y ， y ， 2
* （2） y ， 4
* （3） y y ， 5。
* ： x 。 5 ， 2 ：
* （1）x ， ， （1），（4）， x ， （2）
* ： x （ ）， ，
* （2）x ， x ， （1）， x ， x
*
*/
static void rbTreeDeleteFixup(RBTree *rbTree, RBTreeNode *parent, RBTreeNode *x) {
RBTreeNode *brother;
while ((x == NULL || x->color == BLACK) && x != *rbTree) {
if (x == parent->left) {
brother = parent->right;
// ， , x （ 5 ）
// 1： , parent ， ， ， brother
//parent ， ， 1 2，3，4
if (brother->color == RED) {
brother->color = BLACK;
parent->color = RED;
// brother parent
rbTreeLeftRotate(rbTree, parent);
// brother， 2，3，4
brother = parent->right; // brohter ， NULL
}
// 2： brother （NULL ）: x brother
// ，brother ，x
if ((brother->left == NULL || brother->left->color == BLACK) &&
(brother->right == NULL || brother->right->color == BLACK)) {
brother->color = RED;
x = parent;
parent = parent->parent;
} else {
// 3： brother ，
if (brother->right == NULL || brother->color == BLACK) {
brother->left->color = BLACK;
brother->color = RED;
// 3 4
rbTreeRightRotate(rbTree, brother);
// brother
brother = parent->right;
}
// 4：brother :
// brother parent ， x 2 parent
// brother ， ，
brother->color = parent->color;
parent->color = BLACK;
brother->right->color = BLACK;
rbTreeLeftRotate(rbTree, parent);
// x ，
x = *rbTree;
}
}
else {
brother = parent->left;
// 1
if (brother->color == RED) {
brother->color = BLACK;
parent->color = RED;
rbTreeRightRotate(rbTree, parent);
brother = parent->left;
}
// 2
if ((brother->left == NULL || brother->left->color == BLACK) &&
(brother->right == NULL || brother->right->color == BLACK)) {
brother->color = RED;
x = parent;
parent = parent->parent;
} else {
// 3：： brother ，
if (brother->left == NULL || brother->left->color == BLACK) {
brother->right->color = BLACK;
brother->color = RED;
rbTreeLeftRotate(rbTree, brother);
// brother
brother = parent->left;
}
// 4： brother
brother->color = parent->color;
parent->color = BLACK;
brother->left->color = BLACK;
rbTreeRightRotate(rbTree, parent);
x = *rbTree;
}
}
}
if (x != NULL) {
x->color = BLACK;
}
}
static void rbTreeLeftRotate(RBTree *rbTree, RBTreeNode *x) {
RBTreeNode *y;
y = x->right;
x->right = y->left;
if (y->left != NULL) {
y->left->parent = x;
}
y->parent = x->parent;
//x
if (x->parent == NULL) {
*rbTree = y;
} else {
if (x->parent->left == x) {
x->parent->left = y;
} else {
x->parent->right = y;
}
}
y->left = x;
x->parent = y;
}
static void rbTreeRightRotate(RBTree *rbTree, RBTreeNode *x) {
RBTreeNode *y;
y = x->left;
x->left = y->right;
if (y->right != NULL) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
*rbTree = y;
} else {
if (x->parent->left == x) {
x->parent->left = y;
} else {
x->parent->right = y;
}
}
y->right = x;
x->parent = y;
}
테스트 코드 는 다음 과 같 습 니 다:
#include <stdio.h>
#include <stdlib.h>
#include "RBTree.h"
#define N 11
void printRBNode(RBTreeNode *node);
int main() {
//
int a[N] = {1, 2, 4, 5, 7, 8, 11, 14, 15, 9, 3}, i;
RBTreeNode *root;
//
root = NULL;
//
for (i = 0; i < N; i++) {
if (!rbInsertNode(&root, a[i])) {
break;
}
}
rbInorderTraversal(&root, printRBNode);
// ,
RBTreeNode *fn, *fin, *sn, *tn;
fn = rbSearch(&root, 4);
sn = rbSearch(&root, 2);
fin = rbSuccessor(fn);
tn = rbSuccessor(sn);
printf("%d, %d, %d, %d
", fn->data, fin->data, sn->data, tn->data);
//
fn = rbPredecessor(fin);
sn = rbPredecessor(tn);
printf("%d, %d, %d, %d
", fn->data, fin->data, sn->data, tn->data);
// :
rbDeleteNode(&root, 14);
rbInorderTraversal(&root, printRBNode);
printf("
");
// :
rbDeleteNode(&root, 15);
rbInorderTraversal(&root, printRBNode);
printf("
");
// :
rbDeleteNode(&root, 5);
rbInorderTraversal(&root, printRBNode);
}
void printRBNode(RBTreeNode *node) {
if (node != NULL) {
printf("data: %d, color: %s, parent: %d
",
node->data, (node->color == RED ? "RED" : "BLACK"),
(node->parent != NULL) ? node->parent->data : -1);
}
}
완전한 코드 는 첨부 파일 을 보고 사실 을 작성 하 는 데 이틀 이 걸 렸 습 니 다. 드디어 해결 하고 이 해 했 습 니 다. - -
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
