붉 은 검 은 나무 rbtree 실현, 원 액 오리지널 nginx.이 해 를 깊 게 하 라!
//rbtree.h
#ifndef _RBTREE_H_
#define _RBTREE_H_
#include <stdlib.h>
#include <stdio.h>
#include <string>
typedef unsigned int rbtree_key_t;
typedef unsigned char u_char;
typedef struct rbtree_node_s rbtree_node_t;
struct rbtree_node_s
{
rbtree_key_t key;
rbtree_node_t *left;
rbtree_node_t *right;
rbtree_node_t *parent;
u_char color;
string data;//<key,data>
};
typedef struct rbtree_s rbtree_t;
typedef void (*rbtree_insert_pt) (rbtree_node_t *root,// ,
rbtree_node_t *node, rbtree_node_t *sentinel);
struct rbtree_s
{
rbtree_node_t *root;
rbtree_node_t *sentinel;//all leaf nodes point to the sentinel node
rbtree_insert_pt insert;
};
void rbtree_insert_value(rbtree_node_t *temp, rbtree_node_t *node,
rbtree_node_t *sentinel);
#define rbt_red(node) ((node)->color = 1)
#define rbt_black(node) ((node)->color = 0)
#define rbt_is_red(node) ((node)->color)
#define rbt_is_black(node) (!rbt_is_red(node))
#define rbt_copy_color(n1, n2) (n1->color = n2->color)
#define rbtree_sentinel_init(node) rbt_black(node)
#define rbtree_init(tree, s, i) \
rbtree_sentinel_init(s); \
(tree)->root = s; \
(tree)->sentinel = s; \
(tree)->insert = i
#endif
//rbtree.cpp
#include "rbtree.h"
static inline void rbtree_left_rotate(rbtree_node_t **root, rbtree_node_t *sentinel,
rbtree_node_t *node);/*root */
static inline void rbtree_right_rotate(rbtree_node_t **root, rbtree_node_t *sentinel,
rbtree_node_t *node);
void rbtree_insert_fixup(rbtree_node_t **root, rbtree_node_t *sentinel,
rbtree_node_t *node)
{
rbtree_node_t *temp;
while(node != *root && rbt_is_red(node->parent))
{
if(node->parent == node->parent->parent->left)//left
{
temp = node->parent->parent->right;//
//case 1
if(rbt_is_red(temp))
{
rbt_black(node->parent);
rbt_black(temp);
rbt_red(node->parent->parent);
node = node->parent->parent;
}
else//black
{
//case 2
if(node == node->parent->right)//RR
{
node = node->parent;
rbtree_left_rotate(root, sentinel, node);
}
//case 3
rbt_black(node->parent);
rbt_red(node->parent->parent);
rbtree_right_rotate(root, sentinel, node->parent->parent);
}
}
else//symmetric
{
temp = node->parent->parent->left;//
//case 1
if(rbt_is_red(temp))
{
rbt_black(node->parent);
rbt_black(temp);
rbt_red(node->parent->parent);
node = node->parent->parent;
}
else//black
{
//case 2
if(node == node->parent->left)//LL
{
node = node->parent;
rbtree_right_rotate(root, sentinel, node);
}
//case 3
rbt_black(node->parent);
rbt_red(node->parent->parent);
rbtree_left_rotate(root, sentinel, node->parent->parent);
}
}
}
rbt_black(*root);
}
void rbtree_insert(rbtree_t *tree, rbtree_node_t *node)
{
rbtree_node_t **root, *temp, *sentinel;
root = &tree->root;
sentinel = tree->sentinel;
if(*root == sentinel)
{
node->parent = NULL;
node->left = sentinel;
node->right = sentinel;
rbt_black(node);
*root = node;
return;
}
tree->insert(*root, node, sentinel);
/*rbtree-insert-fixup*/
rbtree_insert_fixup(root, sentinel, node);// blance
}
void rbtree_insert_value(rbtree_node_t *temp, rbtree_node_t *node,
rbtree_node_t *sentinel)
{
rbtree_node_t **p;
//
for(;;)
{
p = (node->key < temp->key) ? &temp->left : &temp->right;
if(*p == sentinel)
{
break;
}
temp = *p;
}
*p = node;// *p , , ^-^
node->parent = temp;
node->left = sentinel;
node->right = sentinel;
rbt_red(node);
}
static inline void
rbtree_left_rotate(rbtree_node_t **root, rbtree_node_t *sentinel,
rbtree_node_t *node)
{
rbtree_node_t* tmp;
/*
| |
x y
/ \ / \
a y ---left---> x c
/ \ / \
b c a b
*/
/*node = x*/
tmp = node->right;
node->right = tmp->left;
// ---3
if(tmp->left != sentinel)
{
tmp->left->parent = node;
}
tmp->parent = node->parent;
if(node == *root)
{
*root = tmp;
}
else if(node == node->parent->left)
{
node->parent->left = tmp;
}
else
{
node->parent->right = tmp;
}
tmp->left = node;
node->parent = tmp;
}
static inline void
rbtree_right_rotate(rbtree_node_t **root, rbtree_node_t *sentinel,
rbtree_node_t *node)
{
rbtree_node_t* tmp;
/*
| |
x y
/ \ / \
a y <---right-- x c
/ \ / \
b c a b
*/
/*node = y*/
tmp = node->left;
node->left = tmp->right;
if(tmp->right != sentinel)
{
tmp->right->parent = node;
}
tmp->parent = node->parent;
if(node == *root)
{
*root = tmp;
}
else if(node == node->parent->left)
{
node->parent->left = tmp;
}
else
{
node->parent->right = tmp;
}
tmp->right = node;
node->parent = tmp;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
붉 은 검 은 나무의 독서 노트이 진 트 리 는 동적 정렬 된 데이터 구조 로 삽입, 삭제, 찾기 등 을 지원 하 며 평균 시간 복잡 도 는 O (log (N) 이지 만 일반 이 진 트 리 는 나무 가 한 가지 로 퇴화 하 는 것 을 보장 하지 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.