原文作者:Rob Landley
原文連結:http://lxr.linux.no/linux+v3.2.1/Documentation/rbtree.txt
red-black tree是什麼?它們有什麼用?
原文連結:http://lxr.linux.no/linux+v3.2.1/Documentation/rbtree.txt
red-black tree是什麼?它們有什麼用?
red-black tree是一種self-balancing binary search tree,用來儲存可被排序的key/value資料組合。與radix trees不同(用來有效地儲存sparse arrays,所以會用長整數的索引來安插/存取/刪除節點),也與hash tables不同(沒有保持在有序的狀態,所以無法輕易地以有序的方式巡訪,並且必須以特定的大小與hash function來微調效能,而rbtresss則可以優雅地擴展並儲存任意的key值)。
(譯註:雖然是很基本的觀念,但小弟還是要囉唆一下。資料結構的選用是因時制宜的。千萬不要以為rbtrees比上述兩種結構好,rbtrees基本上算是對各種操作最四平八穩的結構,但應用時,往往可以挑選更佳的資料結構。舉例來說,如果我們只需要安插/搜尋節點,那麼幾乎沒有什麼資料結構比hash table更合適了,複雜度只要O(1)。)
red-black tree跟AVL trees很像,不過為最糟狀況下的安插與刪除提供了較佳的時間表現(個別最多兩次旋轉與三次旋轉便可讓tree恢復平衡),不過對於搜尋會有一點點的損失(不過還是保持在O(logn))。
引用自Linux Weekly News:
struct mytype {
struct rb_node node;
char *keystring;
當處理一個指向struct rn_node的pointer時,這個資料節點可以透過標準的container_of巨集來存取。另外,每一個資料欄位也可以透過rb_entry(node, type, member)來存取。
在每個rbtree的根部,是一個rb_root的結構,可以透過下列方式完成初始化:
struct rb_root mytree = RB_ROOT;
在rbtree中尋找一個值
(譯註:雖然是很基本的觀念,但小弟還是要囉唆一下。資料結構的選用是因時制宜的。千萬不要以為rbtrees比上述兩種結構好,rbtrees基本上算是對各種操作最四平八穩的結構,但應用時,往往可以挑選更佳的資料結構。舉例來說,如果我們只需要安插/搜尋節點,那麼幾乎沒有什麼資料結構比hash table更合適了,複雜度只要O(1)。)
red-black tree跟AVL trees很像,不過為最糟狀況下的安插與刪除提供了較佳的時間表現(個別最多兩次旋轉與三次旋轉便可讓tree恢復平衡),不過對於搜尋會有一點點的損失(不過還是保持在O(logn))。
引用自Linux Weekly News:
在kernel中有許多red-black trees的應用。deadline與CFQ I/O排程器用rbtrees追蹤請求;ext3檔案系統使用rbtrees紀錄directory entries。Virtual memory areas (VMAs) 也是以rbtrees追蹤、epoll的檔案描述器、密碼學用的key值、以及在"階層式token bucket"的網路封包。
這份文件涵蓋Linux rbtress的使用方式。更多有關red-black tree的原理與實作資訊可參考:
Linux Weekly News上的文章
http://lwn.net/Articles/184495/
維基百科上關於red-black trees的條目
http://en.wikipedia.org/wiki/Red-black_tree
Linux的red-black trees實作
Linux裡的rbtree實作位於"lib/rbtree.c"。使用之前,請"#include <linux/rbtree.h>"。
Linux的rbtree實作針對效能作了最佳化,並且相較於典型的tree的實作,使用了較少的間接層(為了好的cache locality)。每一個struct rb_node的instance都會被嵌入它要處理的資料結構中,而不是透過pointer去區分rb_node與資料結構。使用者也被要求撰寫它們專屬的搜尋與安插functions,而不是使用一個比較的callback function。上鎖的機制也需由rbtree的使用者完成。
建立一個新的rbtree
在rbtree中的資料節點就是那些包含struct rb_node的結構:
struct mytype {
struct rb_node node;
char *keystring;
當處理一個指向struct rn_node的pointer時,這個資料節點可以透過標準的container_of巨集來存取。另外,每一個資料欄位也可以透過rb_entry(node, type, member)來存取。
在每個rbtree的根部,是一個rb_root的結構,可以透過下列方式完成初始化:
struct rb_root mytree = RB_ROOT;
在rbtree中尋找一個值
為你的tree寫一個搜尋動作是很直覺的:從root開始,比較每一個值,然後依狀況從左分支或右分支往下走。範例:
struct mytype *my_search(struct rb_root *root, char *string)
{
struct rb_node *node = root->rb_node;
while (node) {
struct mytype *data = container_of(node, struct mytype, node);
int result;
result = strcmp(string, data->keystring);
if (result < 0)
node = node->rb_left;
else if (result > 0)
node = node->rb_right;
else
return data;
}
return NULL;
}
{
struct rb_node *node = root->rb_node;
while (node) {
struct mytype *data = container_of(node, struct mytype, node);
int result;
result = strcmp(string, data->keystring);
if (result < 0)
node = node->rb_left;
else if (result > 0)
node = node->rb_right;
else
return data;
}
return NULL;
}
將資料安插進rbtree
將資料安插進tree中需要先為新資料搜尋安插的位置,然後安插該節點,然後再平衡("重新上色")tree。
安插部份的搜尋與前面的搜尋不同,需要找到要嫁接的節點位址的pointer。新的節點也需要一個指向其parent的link來完成平衡。
範例:
int my_insert(struct rb_root *root, struct mytype *data)
{
struct rb_node **new = &(root->rb_node), *parent = NULL;
/* Figure out where to put new node */
while (*new) {
struct mytype *this = container_of(*new, struct mytype, node);
int result = strcmp(data->keystring, this->keystring);
parent = *new;
if (result < 0)
new = &((*new)->rb_left);
else if (result > 0)
new = &((*new)->rb_right);
else
return FALSE;
}
/* Add new node and rebalance tree. */
rb_link_node(&data->node, parent, new);
rb_insert_color(&data->node, root);
return TRUE;
}
移除或替換既有的rbtree資料
要從tree移除既有節點,可呼叫:
void rb_erase(struct rb_node *victim, struct rb_root *tree);
範例:
struct mytype *data = mysearch(&mytree, "walrus");
if (data) {
rb_erase(&data->node, &mytree);
myfree(data);
}
要用一個有一樣key值的節點替換既有節點,請呼叫:
void rb_replace_node(struct rb_node *old, struct rb_node *new,
struct rb_root *tree);
以這種方式替換節點無須將tree重新排序:如果新節點沒有與舊節點一樣的key值,該rbtree很有可能會損壞。
巡訪rbtree中的元素(以有序的方式)
有四個functions可以有序的方式迭代一顆rbtree。這可以用在任何的trees,而不需要任何的包裝(除了上鎖以外):
安插部份的搜尋與前面的搜尋不同,需要找到要嫁接的節點位址的pointer。新的節點也需要一個指向其parent的link來完成平衡。
範例:
int my_insert(struct rb_root *root, struct mytype *data)
{
struct rb_node **new = &(root->rb_node), *parent = NULL;
/* Figure out where to put new node */
while (*new) {
struct mytype *this = container_of(*new, struct mytype, node);
int result = strcmp(data->keystring, this->keystring);
parent = *new;
if (result < 0)
new = &((*new)->rb_left);
else if (result > 0)
new = &((*new)->rb_right);
else
return FALSE;
}
/* Add new node and rebalance tree. */
rb_link_node(&data->node, parent, new);
rb_insert_color(&data->node, root);
return TRUE;
}
移除或替換既有的rbtree資料
要從tree移除既有節點,可呼叫:
void rb_erase(struct rb_node *victim, struct rb_root *tree);
範例:
struct mytype *data = mysearch(&mytree, "walrus");
if (data) {
rb_erase(&data->node, &mytree);
myfree(data);
}
要用一個有一樣key值的節點替換既有節點,請呼叫:
void rb_replace_node(struct rb_node *old, struct rb_node *new,
struct rb_root *tree);
以這種方式替換節點無須將tree重新排序:如果新節點沒有與舊節點一樣的key值,該rbtree很有可能會損壞。
巡訪rbtree中的元素(以有序的方式)
有四個functions可以有序的方式迭代一顆rbtree。這可以用在任何的trees,而不需要任何的包裝(除了上鎖以外):
struct rb_node *rb_first(struct rb_root *tree);
struct rb_node *rb_last(struct rb_root *tree);
struct rb_node *rb_next(struct rb_node *node);
struct rb_node *rb_prev(struct rb_node *node);
要開始迭代,請呼叫rb_first()或rb_last(),並將指向root的pointer傳入,結果會回傳tree中的第一個或最後一個節點的pointer。接下來,透過呼叫rb_next()或rb_prev()以獲取目前節點的下一個或前一個節點。當沒有節點時,有可能會回傳NULL。
這些迭代functions回傳被嵌入資料節點的struct rb_node的poniter,所以需用container_of巨集去獲取資料節點,而資料節點的每個欄位可藉由
範例:
struct rb_node *node;
for (node = rb_first(&mytree); node; node = rb_next(node))
printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);
對Augmented rbtrees的支援
Augmented rbtree是一種在每個節點有"一些"額外資訊儲存的rbtree。這種資訊可以用來為rbtree增進新功能。Augmented rbtree是建立在基本rbtree上的可選用功能。想要此功能的rbtree使用者必須在安插與移除時呼叫augmentation functions,並提供augmentation callback。
當安插時,使用者必須在節點已經就定位後呼叫rb_augment_insert()。這會使得augmentation callback在新節點與root之間的每個曾受影響的節點都被喚起。
當要移除節點時,使用者必須先呼叫rb_augment_erase_begin()以獲取在重新平衡後的路徑上的最深節點。然後,在移除該節點後,呼叫rb_augment_erase_end(),並傳進先前獲去的最深節點。這會令augmentation function在每一個被影響的節點被喚起,從最深的節點到root為止。
Interval tree是augmented rbtree的一個例子。可參考"Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein。interval trees的更多細節:
典型的rbtree有一單一的key值,無法直接拿來存一個範圍,像是[lo:hi]。所以無法快速地確認任何的lo:hi是否有重疊,也無法確認是否有一個匹配的lo:hi。
然而,rbtree可以被增強,以有校的方式儲存這樣的區間資訊,使得快速的搜尋與匹配動作變得可能。
這個存於每個節點的"額外資訊"是節點的所有後代的最大hi值。這個資訊可以透過該節點以及它的立即後代(譯註:就是只往下一層的後代)來獲得。這可以用來以O(log n)的效率獲得最低匹配(在所有匹配中,有最低的起始位址),像這樣:
find_lowest_match(lo, hi, node)
{
lowest_match = NULL;
while (node) {
if (max_hi(node->left) > lo) {
// Lowest overlap if any must be on left side
node = node->left;
} else if (overlap(lo, hi, node)) {
lowest_match = node;
break;
} else if (lo > node->lo) {
// Lowest overlap if any must be on right side
node = node->right;
} else {
break;
}
}
return lowest_match;
}
要找到絕對匹配,可以先找到最低匹配,然後沿著接下來的節點來尋找,直到一個節點的起始位址超出了我們要找的hi值。
(譯註:1. augmented tree的實作可以參考./arch/x86/mm/pat_rbtree.c, 2. rbtree的作者同時也是Linux VM的主要實作者,這邊有他的訪談錄)
(譯註:1. augmented tree的實作可以參考./arch/x86/mm/pat_rbtree.c, 2. rbtree的作者同時也是Linux VM的主要實作者,這邊有他的訪談錄)
感謝你的分享 < _ _ >
回覆刪除