搜尋
首頁後端開發php教程nginx的資料結構3-擴展紅黑樹

    發揚我一貫的支線任務狂魔的作風,一晚上就完成了之前設想的紅黑樹擴展版本。

    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,代表目前結點為根的子樹上的結點總數。這樣以序號找出結點的過程將會是二分查找,時間效率與依key查找相同,都是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.依key找出結點速度沒有變化。

    3.哈希查找速度沒有變化。

    4.刪除結點花的時間幾乎是原來的兩倍,因為每次刪除後都要一路向上更新node_cnt,幾乎相當於包含了一次按key查詢。

    5.依序號查詢比按key查詢略慢,因為每次進入右子樹需要多做一次加法。

    6.遍歷花的時間與求樹高相同,因為它們的實質都是遍歷樹,時間效率O(n)數量級,具體點為2n次結點訪問,分別為結點入棧和出棧時。

    別問我max、min、mid在哪,能按序號查詢了這些還是問題嗎?

版權聲明:本文為部落客原創文章,未經部落客允許不得轉載。

以上就介紹了nginx的資料結構3-擴充紅黑樹,包含了方面的內容,希望對PHP教學有興趣的朋友有幫助。

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
您如何防止與會議有關的跨站點腳本(XSS)攻擊?您如何防止與會議有關的跨站點腳本(XSS)攻擊?Apr 23, 2025 am 12:16 AM

要保護應用免受與會話相關的XSS攻擊,需採取以下措施:1.設置HttpOnly和Secure標誌保護會話cookie。 2.對所有用戶輸入進行輸出編碼。 3.實施內容安全策略(CSP)限制腳本來源。通過這些策略,可以有效防護會話相關的XSS攻擊,確保用戶數據安全。

您如何優化PHP會話性能?您如何優化PHP會話性能?Apr 23, 2025 am 12:13 AM

优化PHP会话性能的方法包括:1.延迟会话启动,2.使用数据库存储会话,3.压缩会话数据,4.管理会话生命周期,5.实现会话共享。这些策略能显著提升应用在高并发环境下的效率。

什麼是session.gc_maxlifetime配置設置?什麼是session.gc_maxlifetime配置設置?Apr 23, 2025 am 12:10 AM

theSession.gc_maxlifetimesettinginphpdeterminesthelifespanofsessiondata,setInSeconds.1)它'sconfiguredinphp.iniorviaini_set().2)abalanceisesneededeededeedeedeededto toavoidperformance andunununununexpectedLogOgouts.3)

您如何在PHP中配置會話名?您如何在PHP中配置會話名?Apr 23, 2025 am 12:08 AM

在PHP中,可以使用session_name()函數配置會話名稱。具體步驟如下:1.使用session_name()函數設置會話名稱,例如session_name("my_session")。 2.在設置會話名稱後,調用session_start()啟動會話。配置會話名稱可以避免多應用間的會話數據衝突,並增強安全性,但需注意會話名稱的唯一性、安全性、長度和設置時機。

您應該多久再生一次會話ID?您應該多久再生一次會話ID?Apr 23, 2025 am 12:03 AM

會話ID應在登錄時、敏感操作前和每30分鐘定期重新生成。 1.登錄時重新生成會話ID可防會話固定攻擊。 2.敏感操作前重新生成提高安全性。 3.定期重新生成降低長期利用風險,但需權衡用戶體驗。

如何在PHP中設置會話cookie參數?如何在PHP中設置會話cookie參數?Apr 22, 2025 pm 05:33 PM

在PHP中設置會話cookie參數可以通過session_set_cookie_params()函數實現。 1)使用該函數設置參數,如過期時間、路徑、域名、安全標誌等;2)調用session_start()使參數生效;3)根據需求動態調整參數,如用戶登錄狀態;4)注意設置secure和httponly標誌以提升安全性。

在PHP中使用會議的主要目的是什麼?在PHP中使用會議的主要目的是什麼?Apr 22, 2025 pm 05:25 PM

在PHP中使用會話的主要目的是維護用戶在不同頁面之間的狀態。 1)會話通過session_start()函數啟動,創建唯一會話ID並存儲在用戶cookie中。 2)會話數據保存在服務器上,允許在不同請求間傳遞數據,如登錄狀態和購物車內容。

您如何在子域中分享會議?您如何在子域中分享會議?Apr 22, 2025 pm 05:21 PM

如何在子域名間共享會話?通過設置通用域名的會話cookie實現。 1.在服務器端設置會話cookie的域為.example.com。 2.選擇合適的會話存儲方式,如內存、數據庫或分佈式緩存。 3.通過cookie傳遞會話ID,服務器根據ID檢索和更新會話數據。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

Dreamweaver Mac版

Dreamweaver Mac版

視覺化網頁開發工具

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中