nginx 데이터 구조 3 - 확장된 레드-블랙 트리-PHP 튜토리얼-php.cn

집

백엔드 개발

PHP 튜토리얼

nginx 데이터 구조 3 - 확장된 레드-블랙 트리

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Jul 30, 2016 pm 01:31 PM

gtnodeparent

평소 부업 마니아 스타일을 이어가며 상상했던 레드블랙 트리 확장 버전을 하룻밤 만에 완성했습니다.

rbtree.h:

/*
 * Copyright (C) Bipedal Bit
 * Verson 1.0.0.2
 */

#ifndef _RBTREE_H_INCLUDED_
#define _RBTREE_H_INCLUDED_

/* the node structure of the red-black tree */
typedef struct rbtree_node_s rbtree_node_t;
/* Using type int means its range is -0x7fffffff-1~0x7fffffff. */
typedef int rbtree_key_t;
/* Abstract type is complicated to achieve with C so I use char* instead. */
typedef char* rbtree_data_t;

struct rbtree_node_s
{
	/* key of the node */
	rbtree_key_t	key;
	/* pointer of the parent of the node */
	rbtree_node_t*	parent;
	/* pointer of the left kid of the node */
	rbtree_node_t*	left;
	/* pointer of the right kid of the node */
	rbtree_node_t*	right;
	/* color of the node */
	unsigned char	color;
	/* pointer of the value of the node corresponding to the key */
	rbtree_data_t	value;
	/* count of nodes in the subtree whose root is the current node */
	int node_cnt;
};

/* the tree object stucture of the red-black tree */
typedef struct rbtree_s rbtree_t;
/* foundational insert function pointer */
typedef void (*rbtree_insert_p) (rbtree_t* root, rbtree_node_t* node);
/* foundational visit function pointer */
typedef void (*rbtree_visit_p) (rbtree_node_t* node);

struct rbtree_s
{
	/* the pointer of the root node of the tree */
	rbtree_node_t* root;
	/* black leaf nodes as sentinel */
	rbtree_node_t* sentinel;
	/* the polymorphic insert function pointer */
	rbtree_insert_p insert;
};

/* macros */
#define rbtree_init(tree, s, i)		\
rbtree_sentinel_init(s);			\
(tree)->root = s;				\
(tree)->sentinel = s;			\
(tree)->insert = i

#define rbtree_red(node)	((node)->color = 1)
#define rbtree_black(node)	((node)->color = 0)
#define rbtree_is_red(node)	((node)->color)
#define rbtree_is_black(node)	(!rbtree_is_red(node))
 /* copy n2's color to n1 */
#define rbtree_copy_color(n1, n2)	(n1->color = n2->color)
/* sentinel must be black cuz it's leaf node */
#define rbtree_sentinel_init(node)	\
rbtree_black(node);			\
(node)->node_cnt = 0

/* statements of public methods */
void rbtree_insert_value(rbtree_t* tree, rbtree_node_t* node);
void rbtree_insert(rbtree_t* tree, rbtree_node_t* node);
void rbtree_delete(rbtree_t* tree, rbtree_node_t* node);
/* get node by key */
rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key);
/* get node by order number */
rbtree_node_t* rbtree_index(rbtree_t* tree, int index);
int rbtree_height(rbtree_t* tree, rbtree_node_t* node);
int rbtree_count(rbtree_t* tree);
void rbtree_visit(rbtree_node_t* node);
void rbtree_traversal(rbtree_t* tree, rbtree_node_t* node, rbtree_visit_p);

#endif	/* _RBTREE_H_INCLUDED_ */

보시다시피 일련 번호로 노드 검색, 트리 높이 찾기, 노드 수 찾기, 다시 작성 등 여러 기능을 추가했습니다. 액세스 노드 방법.

일련번호로 노드를 찾는 효율성을 높이기 위해 현재 노드가 루트인 하위 트리의 총 노드 수를 나타내는 노드 항목 node_cnt를 추가했습니다. 이렇게 일련번호로 노드를 검색하는 과정은 이진 검색이 되며, 시간 효율성은 키로 검색하는 것과 같으며, 이는 O(log2n)이다.

순회 방법은 재귀적 순회를 사용합니다. 기본 노드 액세스 방법은 비어 있는 방법이며 사용자가 직접 재정의할 수 있습니다.

rbtree.c:

/*
 * Copyright (C) Bipedal Bit
 * Verson 1.0.0.2
 */

#include <stddef.h>
#include "rbtree.h"

/* inline methods */
/* get the node with the minimum key in a subtree of the red-black tree */
static inline rbtree_node_t*
rbtree_subtree_min(rbtree_node_t* node, rbtree_node_t* sentinel)
{
    while(node->left != sentinel)
    {
        node = node->left;
    }

    return node;
}

/* replace the node "node" in the tree with node "tmp" */
static inline void rbtree_replace(rbtree_t* tree,
    rbtree_node_t* node, rbtree_node_t* tmp)
{
    /* upward: p[node] parent = node->parent;

    if (node == tree->root)
    {
        tree->root = tmp;
    }
    else if (node == node->parent->left)
    {
        /* downward: left[p[node]] parent->left = tmp;
    }
    else
    {
        /* downward: right[p[node]] parent->right = tmp;
    }

    node->parent = tmp;
}

/* change the topologic structure of the tree keeping the order of the nodes */
static inline void rbtree_left_rotate(rbtree_t* tree, rbtree_node_t* node)
{
    /* node as the var x in CLRS while tmp as the var y */
    rbtree_node_t* tmp = node->right;

    /* fix node_cnt */
    node->node_cnt = node->left->node_cnt + tmp->left->node_cnt + 1;
    tmp->node_cnt = node->node_cnt + tmp->right->node_cnt + 1;

    /* replace y with left[y] */
    /* downward: right[x] right = tmp->left;
    /* if left[[y] is not NIL it has a parent */
    if (tmp->left != tree->sentinel)
    {
        /* upward: p[left[y]] left->parent = node;
    }

    /* replace x with y */
    rbtree_replace(tree, node, tmp);
    tmp->left = node;
}

static inline void rbtree_right_rotate(rbtree_t* tree, rbtree_node_t* node)
{
    rbtree_node_t* tmp = node->left;

    /* fix node_cnt */
    node->node_cnt = node->right->node_cnt + tmp->right->node_cnt + 1;
    tmp->node_cnt = node->node_cnt + tmp->left->node_cnt + 1;

    /* replace y with right[y] */
    node->left = tmp->right;
    if (tmp->right != tree->sentinel)
    {
        tmp->right->parent = node;
    }

    /* replace x with y */
    rbtree_replace(tree, node, tmp);
    tmp->right = node;
}

/* static methods */
/* fix the red-black tree after the new node inserted */
static void rbtree_insert_fixup(rbtree_t* tree, rbtree_node_t* node)
{
    while(rbtree_is_red(node->parent))
    {
        if (node->parent == node->parent->parent->left)
        {
            /* case 1: node's uncle is red */
            if (rbtree_is_red(node->parent->parent->right))
            {
                rbtree_black(node->parent);
                rbtree_black(node->parent->parent->right);
                rbtree_red(node->parent->parent);
                node = node->parent->parent;
                /* Then we can consider the whole subtree */
                /* which is represented by the new "node" as the "node" before */
                /* and keep looping till "node" become the root. */
            }
            /* case 2: node's uncle is black */
            else
            {
                /* ensure node is the left kid of its parent */
                if (node == node->parent->right)
                {
                    node = node->parent;
                    rbtree_left_rotate(tree, node);
                }
                /* case 2 -> case 1 */
                rbtree_black(node->parent);
                rbtree_red(node->parent->parent);
                rbtree_right_rotate(tree, node->parent->parent);
            }
        }
        /* same as the "if" clause before with "left" and "right" exchanged */
        else
        {
            if (rbtree_is_red(node->parent->parent->left))
            {
                rbtree_black(node->parent);
                rbtree_black(node->parent->parent->left);
                rbtree_red(node->parent->parent);
                node = node->parent->parent;
            }
            else
            {
                if (node == node->parent->left)
                {
                    node = node->parent;
                    rbtree_right_rotate(tree, node);
                }
                rbtree_black(node->parent);
                rbtree_red(node->parent->parent);
                rbtree_left_rotate(tree, node->parent->parent);
            }
        }
    }
    /* ensure the root node being black */
    rbtree_black(tree->root);
}

static void rbtree_delete_fixup(rbtree_t* tree, rbtree_node_t* node)
{
    rbtree_node_t* brother = NULL;

    while(node != tree->root && rbtree_is_black(node))
    {
        if (node == node->parent->left)
        {
            brother = node->parent->right;
            if (rbtree_is_red(brother))
            {
                rbtree_black(brother);
                rbtree_red(node->parent);
                rbtree_left_rotate(tree, node->parent);
                /* update brother after topologic change of the tree */
                brother = node->parent->right;
            }

            if (rbtree_is_black(brother->left) && rbtree_is_black(brother->right))
            {
                rbtree_red(brother);
                /* go upward and keep on fixing color */
                node = node->parent;
            }
            else
            {
                if (rbtree_is_black(brother->right))
                {
                    rbtree_black(brother->left);
                    rbtree_red(brother);
                    rbtree_right_rotate(tree, brother);
                    /* update brother after topologic change of the tree */
                    brother = node->parent->right;
                }
                rbtree_copy_color(brother, node->parent);
                rbtree_black(node->parent);
                rbtree_black(brother->right);
                rbtree_left_rotate(tree, node->parent);
                /* end the loop and ensure root is black */
                node = tree->root;
            }
        }
        /* same as the "if" clause before with "left" and "right" exchanged */
        else
        {
            brother = node->parent->left;
            if (rbtree_is_red(brother))
            {
                rbtree_black(brother);
                rbtree_red(node->parent);
                rbtree_left_rotate(tree, node->parent);
                brother = node->parent->left;
            }

            if (rbtree_is_black(brother->left) && rbtree_is_black(brother->right))
            {
                rbtree_red(brother);
                node = node->parent;
            }
            else
            {
                if (rbtree_is_black(brother->left))
                {
                    rbtree_black(brother->right);
                    rbtree_red(brother);
                    rbtree_right_rotate(tree, brother);
                    brother = node->parent->left;
                }
                rbtree_copy_color(brother, node->parent);
                rbtree_black(node->parent);
                rbtree_black(brother->left);
                rbtree_left_rotate(tree, node->parent);
                node = tree->root;
            }
        }
    }

    rbtree_black(node);
}

/* public methods */
void rbtree_insert_value(rbtree_t* tree, rbtree_node_t* node)
{
    /* Using ** to know wether the new node will be a left kid */
    /* or a right kid of its parent node. */
    rbtree_node_t** tmp = &tree->root;
    rbtree_node_t* parent;

    while(*tmp != tree->sentinel)
    {
        parent = *tmp;

        /* update node_cnt */
        (parent->node_cnt)++;

        tmp = (node->key key) ? &parent->left : &parent->right;
    }

    /* The pointer knows wether the node should be on the left side */
    /* or on the right one. */
    *tmp = node;
    node->parent = parent;
    node->left = tree->sentinel;
    node->right = tree->sentinel;
    rbtree_red(node);
}

void rbtree_visit(rbtree_node_t* node)
{
    /* visiting the current node */
}

void rbtree_insert(rbtree_t* tree, rbtree_node_t* node)
{
    rbtree_node_t* sentinel = tree->sentinel;

    /* if the tree is empty */
    if (tree->root == sentinel)
    {
        tree->root = node;
        node->parent = sentinel;
        node->left = sentinel;
        node->right = sentinel;
        rbtree_black(node);

        return;
    }

    /* generally */
    tree->insert(tree, node);
    rbtree_insert_fixup(tree, node);
}

void rbtree_delete(rbtree_t* tree, rbtree_node_t* node)
{
    rbtree_node_t* sentinel = tree->sentinel;
    /* wether "node" is on the left side or the right one */
    rbtree_node_t** ptr_to_node = NULL;
    /* "cover" is the node which is going to cover "node" */
    rbtree_node_t* cover = NULL;
    /* wether we lossing a red node on the edge of the tree */
    int loss_red = rbtree_is_red(node);
    int is_root = (node == tree->root);

    /* get "cover" & "loss_red"  */
    /* sentinel in "node"'s kids */
    if (node->left == sentinel)
    {
        cover = node->right;
    }
    else if (node->right == sentinel)
    {
        cover = node->left;
    }
    /* "node"'s kids are both non-sentinel */
    else
    {
        /* update "node" & "loss_red" & "is_root" & "cover" */
        cover = rbtree_subtree_min(node->right, sentinel);
        node->key = cover->key;
        node->value = cover->value;
        node = cover;
        loss_red = rbtree_is_red(node);
        is_root = 0;
        /* move "cover"'s kids */
        /* "cover" can only be a left kid */
        /* and can only have a right non-sentinel kid */
        /* because of function "rbtree_subtree_min" */
        cover = node->right;
    }

    if (is_root)
    {
        /* update root */
        tree->root = cover;
    }
    else
    {
        /* downward link */
        if (node == node->parent->left)
        {
            node->parent->left = cover;
        }
        else
        {
            node->parent->right = cover;
        }
    }
    /* upward link */
    cover->parent = node->parent;
    /* "cover" may be a sentinel */
    if (cover != sentinel)
    {
        /* set "cover" */
        cover->left = node->left;
        cover->right = node->right;
        rbtree_copy_color(cover, node);
    }

    /* clear "node" since it's useless */
    node->key = -1;
    node->parent = NULL;
    node->left = NULL;
    node->right = NULL;
    node->value = NULL;

    /* update node_cnt */
    rbtree_node_t* tmp = cover->parent;
    while(tmp != sentinel)
    {
        (tmp->node_cnt)--;
        tmp = tmp->parent;
    }

    if (loss_red)
    {
        return;
    }

    /* When lossing a black node on edge */
    /* the fifth rule of red-black tree will be broke. */
    /* So the tree need to be fixed. */
    rbtree_delete_fixup(tree, cover);
}

/* find the node in the tree corresponding to the given key value */
rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key)
{
    rbtree_node_t* tmp = tree->root;
    /* next line is just fot test */
    // int step_cnt = 0;

    /* search the binary tree */
    while(tmp != tree->sentinel)
    {
        /* next line is just fot test */
        // step_cnt++;
        if(key == tmp->key)
        {
            /* next line is just for test */
            // printf("step count: %d, color: %s, ", step_cnt, rbtree_is_red(tmp) ? "red" : "black");
            return tmp;
        }

        tmp = (key key) ? tmp->left : tmp->right;
    }

    return NULL;
}

/* find the node in the tree corresponding to the given order number */
rbtree_node_t* rbtree_index(rbtree_t* tree, int index)
{
    if (index = rbtree_count(tree))
    {
        return NULL;
    }

    rbtree_node_t* tmp = tree->root;
    int left_cnt = 0;
    int sub_left_cnt;

    while(tmp->node_cnt > 0)
    {
        sub_left_cnt = tmp->left->node_cnt;
        if (left_cnt + sub_left_cnt == index)
        {
            return tmp;
        }

        if (left_cnt + sub_left_cnt right;
        }
        else
        {
            tmp = tmp->left;
        }
    }
}

/* get the height of the subtree */
int rbtree_height(rbtree_t* tree, rbtree_node_t* node)
{
    if (node == tree->sentinel)
    {
        return 0;
    }

    int left_height = rbtree_height(tree, node->left);
    int right_height = rbtree_height(tree, node->right);
    int sub_height = (left_height > right_height) ? left_height : right_height;
    return sub_height+1;
}

/* get the count of nodes in the tree */
int rbtree_count(rbtree_t* tree)
{
    return tree->root->node_cnt;
}

/* visit every node of the subtree whose root is given in order */
void rbtree_traversal(rbtree_t* tree, rbtree_node_t* node, rbtree_visit_p visit)
{
    if (node != tree->sentinel)
    {
        rbtree_traversal(tree, node->left, visit);
        visit(node);
        rbtree_traversal(tree, node->right, visit);
    }
}

</stddef.h>

스트레스 테스트를 해보자.

test.c:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "rbtree.h"

int main(int argc, char const *argv[])
{
	double duration;
	double room;

	rbtree_t t = {};
	rbtree_node_t s = {};
	rbtree_init(&t, &s, rbtree_insert_value);

	const int cnt = 1key = %d\n", no, rbtree_index(&t, no)->key);

	long time2 = clock();
	room = 48.0*cnt/(1 이전 버전의 스트레스 테스트 결과:
<pre name="code">Inserting 1048576 nodes costs 48.00MB and spends 0.425416 seconds.
Searching 1024 nodes among 1048576 spends 0.001140 seconds.
Hash 1024 times spends 0.000334 seconds.
Deleting 1024 nodes among 1048576 spends 0.000783 seconds.

확장 버전 스트레스 테스트 결과:

Inserting 1048576 nodes costs 48.00MB and spends 0.467859 seconds.
Searching 1024 nodes among 1048576 spends 0.001188 seconds.
Indexing 1024 nodes among 1048576 spends 0.001484 seconds.
Hash 1024 times spends 0.000355 seconds.
Deleting 1024 nodes among 1048576 spends 0.001417 seconds.
The height of the tree is 28. Getting it spends 0.021669 seconds.
Traversal the tree spends 0.023913 seconds.
Count of nodes in the tree is 1047552.

비교 내용을 찾을 수 있습니다:

1. 삽입 시 node_cnt 항목이 하나 더 유지되므로 노드 삽입이 조금 느려집니다.

2. 키로 노드를 찾는 속도에는 변화가 없습니다.

3. 해시 조회 속도에는 변화가 없습니다.

4. 노드를 삭제하는 데 거의 두 배의 시간이 걸립니다. 삭제할 때마다 node_cnt를 완전히 업데이트해야 하기 때문입니다. 이는 키별 쿼리와 거의 동일합니다.

5. 일련번호로 쿼리하는 것은 키로 쿼리하는 것보다 약간 느립니다. 왜냐하면 올바른 하위 트리를 입력할 때마다 하나를 더 추가해야 하기 때문입니다.

6. 본질적으로 트리를 순회하는 것이므로 순회하는 데 걸리는 시간은 트리 높이를 찾는 것과 동일하며, 시간 효율성은 O(n) 정도입니다. 특정 지점은 2n입니다. 노드에 액세스하여 각각 노드를 스택에 밀어넣을 때와 스택에서 튀어나올 때.

max, min, mid가 어디인지 묻지 마세요. 일련번호로 확인할 수 있나요?

저작권 안내: 이 글은 해당 블로거의 원본 글이므로 블로거의 허락 없이 복제할 수 없습니다.

위 내용은 내용의 측면을 포함하여 nginx 데이터 구조 3 - 확장된 레드-블랙 트리를 소개합니다. PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.

성명

본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

뜨거운 도구

SecLists는 최고의 보안 테스터의 동반자입니다. 보안 평가 시 자주 사용되는 다양한 유형의 목록을 한 곳에 모아 놓은 것입니다. SecLists는 보안 테스터에게 필요할 수 있는 모든 목록을 편리하게 제공하여 보안 테스트를 더욱 효율적이고 생산적으로 만드는 데 도움이 됩니다. 목록 유형에는 사용자 이름, 비밀번호, URL, 퍼징 페이로드, 민감한 데이터 패턴, 웹 셸 등이 포함됩니다. 테스터는 이 저장소를 새로운 테스트 시스템으로 간단히 가져올 수 있으며 필요한 모든 유형의 목록에 액세스할 수 있습니다.