前言：

在很多應(yīng)用場(chǎng)景下，我們不但需要堆的特性，例如快速知道數(shù)據(jù)最大值或最小值，同時(shí)還需要知道元素的排序信息，因此本節(jié)我們看看如何實(shí)現(xiàn)魚(yú)和熊掌如何兼得。假設(shè)我們有一系列數(shù)據(jù)，它的元素由兩部分組成，一部分對(duì)應(yīng)商品的名稱(chēng)，其類(lèi)型為字符串，一部分對(duì)應(yīng)商品的貨存數(shù)量，類(lèi)型為整形，我們既需要將商品根據(jù)其名稱(chēng)排序，同時(shí)我們又需要快速查詢(xún)當(dāng)前貨存最小的商品，我們?nèi)绾卧O(shè)計(jì)相應(yīng)的算法和數(shù)據(jù)結(jié)構(gòu)來(lái)滿(mǎn)足這樣特性呢。

舉個(gè)例子，如下圖：

從上圖看，它對(duì)應(yīng)元素字符串是排序二叉樹(shù)，因此根節(jié)點(diǎn)左子樹(shù)對(duì)應(yīng)元素的字符串都小于根字符串，同時(shí)右子樹(shù)對(duì)應(yīng)的字符串都大于根節(jié)點(diǎn)字符串，同時(shí)每個(gè)元素還對(duì)應(yīng)著相應(yīng)商品的貨存數(shù)量，我們需要及時(shí)掌握當(dāng)前貨存最少的商品，這樣才能在其耗盡之前迅速補(bǔ)貨。但是從上圖可以看到，要保證字符串的排序性就得犧牲對(duì)于商品數(shù)量的小堆性質(zhì)，例如上圖中water對(duì)應(yīng)的貨存與wine對(duì)應(yīng)的貨存違背了小堆的性質(zhì)，現(xiàn)在問(wèn)題是如何在保證字符串排序的情況下，確保數(shù)量同時(shí)能滿(mǎn)足小堆性質(zhì)。

首先我們先定義一下數(shù)據(jù)結(jié)構(gòu):

class Node: 
    def __init__(self, key: str, priority: float): 
        self._key = key 
        self._priority = priority 
        self._left: Node = None 
        self._right: Node = None 
        self._parent: Node = None 
 
    @property 
    def left(self): 
        return self._left 
 
    @property 
    def right(self): 
        return self._right 
 
    @property 
    def parent(self): 
        return self._parent 
 
    @left.setter 
    def left(self, node): 
        self._left = node 
        if node is not None: 
            node.parent = self 
 
    @right.setter 
    def right(self, node): 
        self._right = node 
        if node is not None: 
            node.parent = self 
 
    @parent.setter 
    def parent(self, node): 
        self._parent = node 
 
    def is_root(self) -> bool: 
        if self.parent is None: 
            return True 
        return False 
 
    def __repr__(self): 
        return "({}, {})".format(self._key, self._priority) 
 
    def __str__(self): 
        repr_str: str = "" 
        repr_str += repr(self) 
        if self.parent is not None: 
            repr_str += " parent: " + repr(self.parent) 
        else: 
            repr_str += " parent: None" 
 
        if self.left is not None: 
            repr_str += " left: " + repr(self.left) 
        else: 
            repr_str += " left: None" 
 
        if self.right is not None: 
            repr_str += " right: " + repr(self.right) 
        else: 
            repr_str += " right: None" 
 
        return repr_str 
 
class Treap: 
    def  __init__(self): 
        self.root : Node = None 

當(dāng)前問(wèn)題是，當(dāng)上圖所示的矛盾出現(xiàn)時(shí)，我們?nèi)绾握{(diào)整，使得字符串依然保持排序性質(zhì)，同時(shí)貨存數(shù)值能滿(mǎn)足小堆性質(zhì)。我們需要根據(jù)幾種情況采取不同操作，首先看第一種，如下圖：

從上圖看到，一種情況是父節(jié)點(diǎn)與左孩子在數(shù)值上違背了堆的性質(zhì)，此時(shí)我們執(zhí)行一種叫右旋轉(zhuǎn)操作，

其步驟是：

1. Beer節(jié)點(diǎn)逆時(shí)針旋轉(zhuǎn)，替換其父節(jié)點(diǎn);
2. 父節(jié)點(diǎn)Cabbage順時(shí)針旋轉(zhuǎn)，成為Beer的右孩子節(jié)點(diǎn);
3. 原來(lái)Beer的右孩子節(jié)點(diǎn)轉(zhuǎn)變?yōu)?code>Cabbage的左孩子節(jié)點(diǎn);

完成后結(jié)果如下圖所示：

可以看到，此時(shí)字符串依然保持排序二叉樹(shù)性質(zhì)，同時(shí)數(shù)值對(duì)應(yīng)的小堆性質(zhì)也得到了滿(mǎn)足。

我們看看代碼實(shí)現(xiàn)：

class Treap: 
    def __init__(self): 
        self._root: Node = None 
 
    def right_rotate(self, x: Node): 
        if x is None or x.is_root() is True: 
            return 
 
        y = x.parent 
        if y.left != x:  # 必須是左孩子才能右旋轉(zhuǎn) 
            return 
 
        p = y.parent 
        if p is not None:  # 執(zhí)行右旋轉(zhuǎn) 
            if p.left == y: 
                p.left = x 
            else: 
                p.right = x 
        else: 
            self._root = x 
 
        y.left = x.right 
        x.right = y 

接下來(lái)我們構(gòu)造一些數(shù)據(jù)測(cè)試一下上面的實(shí)現(xiàn)是否正確：

def setup_right_rotate(): 
    flour: Node = Node("Flour", 10) 
    cabbage: Node = Node("Cabbage", 77) 
    beer: Node = Node("Beer", 76) 
    bacon: Node = Node("Bacon", 95) 
    butter: Node = Node("Butter", 86) 
 
    flour.parent = None 
    flour.left = cabbage 
    flour.right = None 
    cabbage.left = beer 
 
 
    beer.left = bacon 
    beer.right = butter 
 
    return flour, beer 
 
def print_treap(n: Node): 
    if n is None: 
        return 
 
    print(n) 
    print_treap(n.left) 
    print_treap(n.right) 
 
treap = Treap() 
root, x , cabbage = setup_right_rotate() 
print("---------before right rotate---------:") 
print_treap(root) 
treap.right_rotate(x) 
print("-------after right rotate-------") 
print_treap(root) 

上面代碼執(zhí)行后輸出內(nèi)容如下：

---------before right rotate---------:
(Flour, 10) parent: None left: (Cabbage, 77) right: None
(Cabbage, 77) parent: (Flour, 10) left: (Beer, 76) right: (Eggs, 129)
(Beer, 76) parent: (Cabbage, 77) left: (Bacon, 95) right: (Butter, 86)
(Bacon, 95) parent: (Beer, 76) left: None right: None
(Butter, 86) parent: (Beer, 76) left: None right: None
(Eggs, 129) parent: (Cabbage, 77) left: None right: None
-------after right rotate-------
(Flour, 10) parent: None left: (Beer, 76) right: None
(Beer, 76) parent: (Flour, 10) left: (Bacon, 95) right: (Cabbage, 77)
(Bacon, 95) parent: (Beer, 76) left: None right: None
(Cabbage, 77) parent: (Beer, 76) left: (Butter, 86) right: (Eggs, 129)
(Butter, 86) parent: (Cabbage, 77) left: None right: None
(Eggs, 129) parent: (Cabbage, 77) left: None right: None

對(duì)比右旋轉(zhuǎn)前后輸出的二叉樹(shù)看，旋轉(zhuǎn)后的二叉樹(shù)打印信息的確跟上面我們旋轉(zhuǎn)后對(duì)應(yīng)的圖像是一致的。接下來(lái)我們實(shí)現(xiàn)左旋轉(zhuǎn)，先把上圖中cabbage節(jié)點(diǎn)對(duì)應(yīng)的值改成75，這樣它與父節(jié)點(diǎn)就違背了小堆性質(zhì)：

我們要做的是：

1. 把cabbage節(jié)點(diǎn)向“左”旋轉(zhuǎn)到beer的位置;
2. beer的父節(jié)點(diǎn)設(shè)置為cabbage;
3. beer的右孩子設(shè)置為cabbage的左孩子;
4. cabbage的左孩子變成beer;左旋轉(zhuǎn)后二叉樹(shù)

成形如下：

從上圖看，左旋轉(zhuǎn)后，字符串依然保持二叉樹(shù)排序性，同時(shí)數(shù)值的排放也遵守小堆原則，我們看相應(yīng)的代碼實(shí)現(xiàn)：

class Treap: 
   ... 
 
    def left_rotate(self, x : Node): 
        if x is None or x.is_root() is True: 
            return 
 
        y = x.parent 
        if y.right is not x: # 只有右孩子才能左旋轉(zhuǎn) 
            return 
 
        p = y.parent 
        if p is not None: 
            if p.left is y: 
                p.left = x 
            else: 
                p.right = x 
        else: 
            self._root = x 
 
        y.right = x.left 
        x.left = y 

為了測(cè)試上面代碼實(shí)現(xiàn)，我們首先把cabbage的值修改，然后調(diào)用上面代碼:

cabbage._priority = 75 
print("-------before left rotate--------") 
print_treap(root) 
treap.left_rotate(cabbage) 
print("-------after left rotate---------") 
print_treap(root) 

代碼運(yùn)行后輸出結(jié)果為:

-------before left rotate--------
(Flour, 10) parent: None left: (Beer, 76) right: None
(Beer, 76) parent: (Flour, 10) left: (Bacon, 95) right: (Cabbage, 75)
(Bacon, 95) parent: (Beer, 76) left: None right: None
(Cabbage, 75) parent: (Beer, 76) left: (Butter, 86) right: (Eggs, 129)
(Butter, 86) parent: (Cabbage, 75) left: None right: None
(Eggs, 129) parent: (Cabbage, 75) left: None right: None
-------after left rotate---------
(Flour, 10) parent: None left: (Cabbage, 75) right: None
(Cabbage, 75) parent: (Flour, 10) left: (Beer, 76) right: (Eggs, 129)
(Beer, 76) parent: (Cabbage, 75) left: (Bacon, 95) right: (Butter, 86)
(Bacon, 95) parent: (Beer, 76) left: None right: None
(Butter, 86) parent: (Beer, 76) left: None right: None
(Eggs, 129) parent: (Cabbage, 75) left: None right: None

輸出結(jié)果的描述與上圖左旋轉(zhuǎn)后的結(jié)果是一致的。由于Treap相對(duì)于元素的key是排序二叉樹(shù)，因此在給定一個(gè)字符串后，我們很容易查詢(xún)字符串是否在Treap中，其本質(zhì)就是排序二叉樹(shù)的搜索，其實(shí)現(xiàn)我們暫時(shí)忽略。

雖然查詢(xún)很簡(jiǎn)單，但是插入節(jié)點(diǎn)則稍微麻煩，因?yàn)椴迦牒?，新?jié)點(diǎn)與其父節(jié)點(diǎn)可能會(huì)違背小堆性質(zhì)，因此在完成插入后，我們還需使用上面實(shí)現(xiàn)的左旋轉(zhuǎn)或右旋轉(zhuǎn)來(lái)進(jìn)行調(diào)整。

到此這篇關(guān)于Python使用treap實(shí)現(xiàn)雙索引的方法的文章就介紹到這了,更多相關(guān)Python使用treap實(shí)現(xiàn)雙索引內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論