中文試譯：Red-black Trees (rbtree) in Linux

原文作者：Rob Landley
原文連結：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：

在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;
  }

將資料安插進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，而不需要任何的包裝（除了上鎖以外）：

  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的主要實作者，這邊有他的訪談錄）