[[357058]]

大家好，今天和大家聊一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，叫做Treap。

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

Treap的基本原理

既然是平衡二叉搜索樹，關(guān)鍵點(diǎn)就在于平衡，那么重點(diǎn)自然是如何維護(hù)樹的平衡。

在Treap當(dāng)中，維護(hù)平衡非常簡單，只有一句話，就是通過維護(hù)小頂堆的形式來維持樹的平衡。Treap也正是因此得名，因?yàn)樗荰ree和Heap的結(jié)合體。

我們來看下Treap當(dāng)中節(jié)點(diǎn)的結(jié)構(gòu)：

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是我抽象出來的樹結(jié)構(gòu)通用的Node，當(dāng)中包含key、value、lchild、rchild和father。TreapNode其實(shí)就是在此基礎(chǔ)上增加了一個(gè)priority屬性。

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

Treap的增刪改查

插入

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

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

答案很簡單，因?yàn)槲覀冊诓迦氲臅r(shí)候，需要對每一個(gè)插入的Node隨機(jī)附上一個(gè)priority。堆就是用來維護(hù)這個(gè)priority的，保證樹根一定擁有最小的priority。正是由于這個(gè)priority是隨機(jī)的，我們可以保證整棵樹蛻化成線性的概率降到無窮低。

當(dāng)我們插入元素之后發(fā)現(xiàn)破壞了堆的性質(zhì)，那么我們需要通過旋轉(zhuǎn)操作來維護(hù)。舉個(gè)簡單的例子，在下圖當(dāng)中，如果B節(jié)點(diǎn)的priority比D要小，為了保證堆的性質(zhì)，需要將B和D進(jìn)行互換。由于直接互換會破壞BST的性質(zhì)，所以我們采取旋轉(zhuǎn)的操作。

旋轉(zhuǎn)之后我們發(fā)現(xiàn)B和D互換了位置，并且旋轉(zhuǎn)之后的A和E的priority都是大于D的，所以旋轉(zhuǎn)之后我們整棵樹依然維持了性質(zhì)。

右旋的情況也是一樣的，其實(shí)我們觀察一下會發(fā)現(xiàn)，要交換左孩子和父親需要右旋，如果是要交換右孩子和父親，則需要左旋。

整個(gè)插入的操作其實(shí)就是基礎(chǔ)的BST插入過程，加上旋轉(zhuǎn)的判斷。

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的插入，也就是和當(dāng)前節(jié)點(diǎn)比大小，決定插入在左邊還是右邊。注意一下，這里我們在插入完成之后，增加了maintain的邏輯，其實(shí)也就是比較一下，剛剛進(jìn)行的插入是否破壞了堆的性質(zhì)。可能有些同學(xué)要問我了，這里為什么只maintain了一次?有可能插入的priority非常小，需要一直旋轉(zhuǎn)到樹根不是嗎?

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

查詢

查詢很簡單，不用多說，就是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) 

刪除

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

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

對于這兩種情況之外，我們就沒辦法直接刪除了，因?yàn)楸厝粫绊懚训男再|(zhì)。這里有一個(gè)很巧妙的做法，就是可以先將要?jiǎng)h除的節(jié)點(diǎn)旋轉(zhuǎn)，將它旋轉(zhuǎn)成葉子節(jié)點(diǎn)或者是鏈節(jié)點(diǎn)，再進(jìn)行刪除。

在這個(gè)過程當(dāng)中，我們需要比較一下它兩個(gè)孩子的優(yōu)先級，確保堆的性質(zhì)不會受到破壞。

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: 
            # 如果是鏈節(jié)點(diǎn)，葉子節(jié)點(diǎn)的情況也包括了 
            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: 
                # 根據(jù)兩個(gè)孩子的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') 

修改

修改的操作也非常簡單，我們直接查找到對應(yīng)的節(jié)點(diǎn)，修改它的value即可。

旋轉(zhuǎn)

我們也貼一下旋轉(zhuǎn)操作的代碼，其實(shí)這里的邏輯和之前SBT當(dāng)中介紹的旋轉(zhuǎn)操作是一樣的，代碼也基本相同：

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當(dāng)中存儲的都是引用，所以我們在旋轉(zhuǎn)操作之后必須要重新覆蓋一下父節(jié)點(diǎn)當(dāng)中當(dāng)中的值才會生效。負(fù)責(zé)我們修改了node的引用，但是father當(dāng)中還是存儲的舊的地址，一樣沒有生效。

后記

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

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

最后，還是老規(guī)矩，我把完整的代碼放在了paste當(dāng)中，大家感興趣可以點(diǎn)擊閱讀原文查看，代碼里都有詳細(xì)的注釋，大家應(yīng)該都能看明白。

本文轉(zhuǎn)載自微信公眾號「 TechFlow」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系 TechFlow公眾號。