[[357058]]

大家好，今天和大家聊一個新的數據結構，叫做Treap。

Treap本質上也是一顆BST(平衡二叉搜索樹)，和我們之前介紹的SBT是一樣的。但是Treap維持平衡的方法和SBT不太一樣，有些許區別，相比來說呢，Treap的原理還要再簡單一些，所以之前在競賽當中不允許使用STL的時候，我們通常都會手寫一棵Treap來代替。

Treap的基本原理

既然是平衡二叉搜索樹，關鍵點就在于平衡，那么重點自然是如何維護樹的平衡。

在Treap當中，維護平衡非常簡單，只有一句話，就是通過維護小頂堆的形式來維持樹的平衡。Treap也正是因此得名，因為它是Tree和Heap的結合體。

我們來看下Treap當中節點的結構：

class TreapNode(TreeNode): 
    """ 
    TreeNode: The node class of treap tree. 
    Paramters:  
        key: The key of node, can be treated as the key of dictionary 
        value: The value of node, can be treated as the value of dictionary 
        priority: The priority of node, specially for treap structure, describe the priority of the node in the treap.  
        lchild: The left child of node 
        rchild: The right child of node 
        father: The parent of node, incase that we need to remove or rotate the node in the treap, so we need father parameter to mark the address of the parent 
    """ 
    def __init__(self, key=None, value=None, lchild=None, rchild=None, father=None, priority=None): 
        super().__init__(key, value, lchild, rchild, father) 
        self._priority = priority 
 
    @property 
    def priority(self): 
        return self._priority 
 
    @priority.setter 
    def priority(self, priority): 
        self._priority = priority 
 
    def __str__(self): 
        return 'key={}, value={}'.format(self.key, self.value) 

這里的TreeNode是我抽象出來的樹結構通用的Node，當中包含key、value、lchild、rchild和father。TreapNode其實就是在此基礎上增加了一個priority屬性。

之所以要增加這個priority屬性是為了維護它堆的性質，通過維護這個堆的性質來保持樹的平衡。具體的操作方法，請往下看。

Treap的增刪改查

插入

首先來講Treap的插入元素的操作，其實插入元素的操作非常簡單，就是普通BST插入元素的操作。唯一的問題是如何維持樹的平衡。

我們前文說了，我們是通過維持堆的性質來保持平衡的，那么自然又會有一個新的問題。為什么維持堆的性質可以保證平衡呢?

答案很簡單，因為我們在插入的時候，需要對每一個插入的Node隨機附上一個priority。堆就是用來維護這個priority的，保證樹根一定擁有最小的priority。正是由于這個priority是隨機的，我們可以保證整棵樹蛻化成線性的概率降到無窮低。

當我們插入元素之后發現破壞了堆的性質，那么我們需要通過旋轉操作來維護。舉個簡單的例子，在下圖當中，如果B節點的priority比D要小，為了保證堆的性質，需要將B和D進行互換。由于直接互換會破壞BST的性質，所以我們采取旋轉的操作。

旋轉之后我們發現B和D互換了位置，并且旋轉之后的A和E的priority都是大于D的，所以旋轉之后我們整棵樹依然維持了性質。

右旋的情況也是一樣的，其實我們觀察一下會發現，要交換左孩子和父親需要右旋，如果是要交換右孩子和父親，則需要左旋。

整個插入的操作其實就是基礎的BST插入過程，加上旋轉的判斷。

def _insert(self, node, father, new_node, left_or_right='left'): 
      """ 
      Inside implement of insert node. 
      Implement in recursion. 
      Since the parameter passed in Python is reference, so when we add node, we need to assign the node to its father, otherwise the reference will lose outside the function. 
      When we add node, we need to compare its key with its father's key to make sure it's the lchild or rchild of its father. 
      """ 
      if node is None: 
          if new_node.key < father.key: 
              father.lchild = new_node 
          else: 
              father.rchild = new_node 
          new_node.father = father 
          return 
      if new_node.key < node.key: 
          self._insert(node.lchild, node, new_node, 'left') 
          # maintain 
          if node.lchild.priority < node.priority: 
              self.rotate_right(node, father, left_or_right) 
      else: 
          self._insert(node.rchild, node, new_node, 'right') 
          # maintain 
          if node.rchild.priority < node.priority: 
              self.rotate_left(node, father, left_or_right) 

前面的邏輯就是BST的插入，也就是和當前節點比大小，決定插入在左邊還是右邊。注意一下，這里我們在插入完成之后，增加了maintain的邏輯，其實也就是比較一下，剛剛進行的插入是否破壞了堆的性質。可能有些同學要問我了，這里為什么只maintain了一次?有可能插入的priority非常小，需要一直旋轉到樹根不是嗎?

的確如此，但是不要忘了，我們這里的maintain邏輯并非只調用一次。隨著整個遞歸的回溯，在樹上的每一層它其實都會執行一次maintain邏輯。所以是可以保證從插入的地方一直維護到樹根的。

查詢

查詢很簡單，不用多說，就是BST的查詢操作，沒有任何變化。

def _query(self, node, key, backup=None): 
       if node is None: 
           return backup 
       if key < node.key: 
           return self._query(node.lchild, key, backup) 
       elif key > node.key: 
           return self._query(node.rchild, key, backup) 
       return node 
 
   def query(self, key, backup=None): 
       """ 
       Return the result of query a specific node, if not exists return None 
       """ 
       return self._query(self.root, key, backup) 

刪除

刪除的操作稍微麻煩了一些，由于涉及到了優先級的維護，不過邏輯也不難理解，只需要牢記需要保證堆的性質即可。

首先，有兩種情況非常簡單，一種是要刪除的節點是葉子節點，這個都很容易想明白，刪除它不會影響任何其他節點，直接刪除即可。第二種情況是鏈節點，也就是說它只有一個孩子，那么刪除它也不會引起變化，只需要將它的孩子過繼給它的父親，整個堆和BST的性質也不會受到影響。

對于這兩種情況之外，我們就沒辦法直接刪除了，因為必然會影響堆的性質。這里有一個很巧妙的做法，就是可以先將要刪除的節點旋轉，將它旋轉成葉子節點或者是鏈節點，再進行刪除。

在這個過程當中，我們需要比較一下它兩個孩子的優先級，確保堆的性質不會受到破壞。

def _delete_node(self, node, father, key, child='left'): 
        """ 
        Implement function of delete node. 
        Defined as a private function that only can be called inside. 
        """ 
        if node is None: 
            return 
        if key < node.key: 
            self._delete_node(node.lchild, node, key) 
        elif key > node.key: 
            self._delete_node(node.rchild, node, key, 'right') 
        else: 
            # 如果是鏈節點，葉子節點的情況也包括了 
            if node.lchild is None: 
                self.reset_child(father, node.rchild, child) 
            elif node.rchild is None: 
                self.reset_child(father, node.lchild, child) 
            else: 
                # 根據兩個孩子的priority決定是左旋還是右旋 
                if node.lchild.priority < node.rchild.priority: 
                    node = self.rotate_right(node, father, child) 
                    self._delete_node(node.rchild, node, key, 'right') 
                else: 
                    node = self.rotate_left(node, father, child) 
                    self._delete_node(node.lchild, node, key) 
 
                     
    def delete(self, key): 
        """ 
        Interface of delete method face outside. 
        """ 
        self._delete_node(self.root, None, key, 'left') 

修改

修改的操作也非常簡單，我們直接查找到對應的節點，修改它的value即可。

旋轉

我們也貼一下旋轉操作的代碼，其實這里的邏輯和之前SBT當中介紹的旋轉操作是一樣的，代碼也基本相同：

def reset_child(self, node, child, left_or_right='left'): 
       """ 
       Reset the child of father, since in Python all the instances passed by reference, so we need to set the node as a child of its father node. 
       """ 
       if node is None: 
           self.root = child 
           self.root.father = None 
           return 
       if left_or_right == 'left': 
           node.lchild = child 
       else: 
           node.rchild = child 
       if child is not None: 
           child.father = node 
 
 
def rotate_left(self, node, father, left_or_right): 
       """ 
       Left rotate operation of Treap. 
       Example:  
 
               D 
             /   \ 
            A      B 
                  / \ 
                 E   C 
 
       After rotate: 
 
               B 
              / \ 
             D   C 
            / \ 
           A   E  
       """ 
       rchild = node.rchild 
       node.rchild = rchild.lchild 
       if rchild.lchild is not None: 
           rchild.lchild.father = node 
       rchild.lchild = node 
       node.father = rchild 
       self.reset_child(father, rchild, left_or_right) 
       return rchild 
 
   def rotate_right(self, node, father, left_or_right): 
       """ 
       Right rotate operation of Treap. 
       Example:  
 
               D 
             /   \ 
            A     B 
           / \ 
          E   C 
 
       After rotate: 
 
               A 
              / \ 
             E   D 
                / \ 
               C   B  
       """ 
       lchild = node.lchild 
       node.lchild = lchild.rchild 
       if lchild.rchild is not None: 
           lchild.rchild.father = node 
       lchild.rchild = node 
       node.father = lchild 
       self.reset_child(father, lchild, left_or_right) 
       return lchild 

這里唯一要注意的是，由于Python當中存儲的都是引用，所以我們在旋轉操作之后必須要重新覆蓋一下父節點當中當中的值才會生效。負責我們修改了node的引用，但是father當中還是存儲的舊的地址，一樣沒有生效。

后記

基本上到這里整個Treap的原理就介紹完了，當然除了我們剛才介紹的基本操作之外，Treap還有一些其他的操作。比如可以split成兩個Treap，也可以由兩個Treap合并成一個。還可以查找第K大的元素，等等。這些額外的操作，我用得也不多，就不多介紹了，大家感興趣可以去了解一下。

Treap這個數據結構在實際當中幾乎沒有用到過，一般還是以競賽場景為主，我們學習它主要就是為了提升和鍛煉我們的數據結構能力以及代碼實現能力。Treap它的最大優點就是實現簡單，沒有太多復雜的操作，但是我們前面也說了，它是通過隨機的priority來控制樹的平衡的，那么它顯然無法做到完美平衡，只能做到不落入最壞的情況，但是無法保證可以進入最好的情況。不過對于二叉樹來說，樹深的一點差距相差并不大。所以Treap的性能倒也沒有那么差勁，屬于一個性價比非常高的數據結構。

最后，還是老規矩，我把完整的代碼放在了paste當中，大家感興趣可以點擊閱讀原文查看，代碼里都有詳細的注釋，大家應該都能看明白。

本文轉載自微信公眾號「 TechFlow」，可以通過以下二維碼關注。轉載本文請聯系 TechFlow公眾號。