如何解析平衡二叉搜索樹Treap

這篇文章給大家介紹如何解析平衡二叉搜索樹Treap，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

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

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

Treap的基本原理

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

在Treap當(dāng)中，維護(hù)平衡非常簡單，只有一句話，就是通過維護(hù)小頂堆的形式來維持樹的平衡。Treap也正是因此得名，因為它是Tree和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其實就是在此基礎(chǔ)上增加了一個priority屬性。

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

Treap的增刪改查

插入

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

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

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

當(dāng)我們插入元素之后發(fā)現(xiàn)破壞了堆的性質(zhì)，那么我們需要通過旋轉(zhuǎn)操作來維護(hù)。舉個簡單的例子，在下圖當(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ì)。

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

整個插入的操作其實就是基礎(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的邏輯，其實也就是比較一下，剛剛進(jìn)行的插入是否破壞了堆的性質(zhì)?？赡苡行┩瑢W(xué)要問我了，這里為什么只maintain了一次?有可能插入的priority非常小，需要一直旋轉(zhuǎn)到樹根不是嗎?

的確如此，但是不要忘了，我們這里的maintain邏輯并非只調(diào)用一次。隨著整個遞歸的回溯，在樹上的每一層它其實都會執(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é)點(diǎn)是葉子節(jié)點(diǎn)，這個都很容易想明白，刪除它不會影響任何其他節(jié)點(diǎn)，直接刪除即可。第二種情況是鏈節(jié)點(diǎn)，也就是說它只有一個孩子，那么刪除它也不會引起變化，只需要將它的孩子過繼給它的父親，整個堆和BST的性質(zhì)也不會受到影響。

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

在這個過程當(dāng)中，我們需要比較一下它兩個孩子的優(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ù)兩個孩子的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)操作的代碼，其實這里的邏輯和之前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)中還是存儲的舊的地址，一樣沒有生效。

關(guān)于如何解析平衡二叉搜索樹Treap就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。