Python の高度なアルゴリズムとデータ構造: treap を使用してデュアル インデックスを実装する (パート 1)

\

上記で紹介したヒープ構造では、データを部分的にしかソートできません。つまり、一部の要素のソートしか知ることができません。たとえば、ルート ノードから開始して左の子または右の子に沿って移動すると、トラバースされた要素が増加 (小さなヒープ) または減少 (大きなヒープ) 関係にあることがわかりますが、左のサブツリーと右のサブツリーのノード間のソート関係を知ることはできません。

多くのアプリケーション シナリオでは、データの最大値や最小値をすばやく知るなどのヒープ特性だけでなく、要素のソート情報も知る必要があります。したがって、このセクションでは、両方の長所を実現する方法について説明します。要素が 2 つの部分から構成される一連のデータがあるとします。1 つの部分は製品名に対応し、その型は文字列です。もう 1 つの部分は製品の在庫数に対応し、その型は整数です。製品を名前で並べ替える必要があり、同時に、現在の在庫が最も少ない製品をすばやく照会する必要があります。このような特性を満たすために、対応するアルゴリズムとデータ構造をどのように設計すればよいでしょうか。

たとえば、次のようになります。

上図から、対応する要素の文字列がソートされたバイナリツリーであることがわかります。したがって、ルートノードの左側のサブツリーの要素に対応する文字列はルート文字列よりも小さく、右側のサブツリーに対応する文字列はルートノードの文字列よりも大きくなります。同時に、各要素は対応する製品の在庫数にも対応しています。在庫が最も少ない製品を追跡して、在庫切れになる前に迅速に補充できるようにする必要があります。しかし、上図からわかるように、文字列の順序性を保証するためには、商品の数量の小ヒープ特性を犠牲にしなければなりません。例えば、上図の水に対応する在庫とワインに対応する在庫は、小ヒープ特性に違反しています。ここで問題となるのは、文字列の順序性を確保しながら、数量が小ヒープ特性を満たすようにするにはどうすればよいかということです。

まず、データ構造を定義しましょう。

クラス ノード:
    def __init__(self,キー: str, 優先度: float ):
        self._key =キー 
        self._priority = 優先度
        self._left: ノード = なし
        self._right: ノード = なし
        self._parent: ノード = なし
 
    @財産
    def left (自分):
 self._leftを返す
 
    @財産
    def right (自分):
 self._rightを返す
 
    @財産
    親(自分)を定義します。
 self._parentを返す
 
    @left .setter
    def left (self, ノード):
        self._left = ノード
        ノードが なしではない:
            ノード.親 = 自分
 
    @right .setter
    def right (self, ノード):
        self._right = ノード
        ノードが なしではない:
            ノード.親 = 自分
 
    @親セッター
    親を定義します(自分自身、ノード):
        self._parent = ノード
 
    def is_root(self) -> bool:
        self.parentがNone の場合:
戻る 真実 
戻る 間違い  
 
    __repr__(self)を定義します:
戻る  "({}, {})" .format(self._key, self._priority) 
 
    __str__(自分)を定義します:
        repr_str: str = ""  
        repr_str += repr(自分自身)
        self.parentが なしではない:
            repr_str += " 親: " + repr(self.parent)
それ以外：
            repr_str += " 親: なし "   
 
        自分自身が左の場合 は なしではない:
            repr_str += " 左: " + repr ( self.left )
それ以外：
            repr_str += " 左: なし "   
 
        自己が正しい場合 は なしではない:
            repr_str += " 右: " + repr ( self.right )
それ以外：
            repr_str += " 右: なし"   
 
 repr_strを返す
 
クラスTreap:
    __init__(self)を定義します。
        self.root: ノード = なし

現在の問題は、上図のような矛盾が発生した場合に、文字列がソート特性を維持し、インベントリ値が小さなヒープ特性を満たすようにどのように調整するかということです。いくつかの状況に応じて異なるアクションを取る必要があります。以下に示すように、最初のものを見てみましょう。

上の図から、親ノードと左の子ノードが数値的にヒープの性質に違反している状況が 1 つあることがわかります。このとき、右回転操作を実行します。手順は次のとおりです。1. Beer ノードが反時計回りに回転して、親ノードを置き換えます。2. 親ノード Cabbage が時計回りに回転して、Beer の右の子ノードになります。3. Beer の元の右の子ノードが Cabbage の左の子ノードに変換されます。完了後の結果は、次の図のようになります。

このとき文字列はソートされた二分木の性質を維持しており、数値に対応する小さなヒープの性質も満たされていることがわかります。コードの実装を見てみましょう:

クラスTreap:
    __init__(self)を定義します。
        self._root: ノード = なし
 
    def right_rotate(self, x: ノード):
        xがNoneまたはx.is_root()が 真実：
戻る  
 
        y = x.親
        if y.left != x: # 右に回転するには左の子である必要があります
戻る  
 
        p = y.親
        pが  not None: # 右回転を実行する
            p.left == yの場合:
                p.左= x
それ以外：
                p.右= x
それ以外：
            自己._root = x 
 
        y.左= x.右 
        x.右= y

次に、上記の実装が正しいかどうかをテストするためにいくつかのデータを構築します。

 def setup_right_rotate():
    小麦粉: Node = Node( "小麦粉" , 10)
    キャベツ: Node = Node( "キャベツ" , 77)
    ビール: Node = Node( "ビール" , 76)
    ベーコン: Node = Node( "ベーコン" , 95)
    バター: Node = Node( "バター" , 86) 
 
    flour.parent = なし
    小麦粉。左＝キャベツ
    flour.right = なし
    キャベツ.左= ビール
 
 
    ビール.左=ベーコン
    ビール。右はバター
 
小麦粉、ビールを返す
 
 def print_treap(n: ノード):
    nがNone の場合:
戻る  
 
    印刷(n)
    print_treap( n.left )
    print_treap(名詞右) 
 
トレップ = トレップ()
ルート、x、キャベツ = setup_right_rotate()
 print( "---------右回転前---------:" )
 print_treap(ルート)
 treap.right_rotate(x)
 print( "------右回転後-------" )
 print_treap(ルート)

上記のコードを実行した後の出力は次のようになります。

 ---------右回転前---------:  
 (小麦粉、10) 親: なし左: (キャベツ、77)右: なし
(キャベツ、77) 親: (小麦粉、10)左: (ビール、76)右: (卵、129)
 (ビール、76) 親: (キャベツ、77)左: (ベーコン、95)右: (バター、86)
 (ベーコン、95) 親: (ビール、76)左: なし右: なし
(バター、86) 親: (ビール、76)左: なし右: なし
(卵、129) 親: (キャベツ、77)左: なし右: なし
-------右回転後-------  
 (小麦粉、10) 親: なし左: (ビール、76)右: なし
(ビール、76) 親: (小麦粉、10)左: (ベーコン、95)右: (キャベツ、77)
 (ベーコン、95) 親: (ビール、76)左: なし右: なし
(キャベツ、77) 親: (ビール、76)左: (バター、86)右: (卵、129)
 (バター、86) 親: (キャベツ、77)左: なし右: なし
(卵、129) 親: (キャベツ、77)左: なし右: なし

右回転の前後のバイナリ ツリーの出力を比較すると、回転したバイナリ ツリーによって印刷される情報は、上記の回転後の対応する画像と確かに一致しています。次に、左回転を実装します。まず、上図のキャベツノードに対応する値を 75 に変更して、そのノードと親ノードが小さいヒープ プロパティに違反するようにします。

必要な作業は次のとおりです。1. キャベツ ノードをビールの位置に「左」に回転します。2. ビールの親ノードをキャベツに設定します。3. ビールの右の子をキャベツの左の子に設定します。4. キャベツの左の子がビールになります。左回転後、バイナリ ツリーは次のようになります。

上の図から、左回転後も文字列はバイナリツリーソートを維持し、数値出力もスモールヒープ原則に準拠していることがわかります。対応するコード実装を見てみましょう。

クラスTreap:
   ... 
 
    def left_rotate(self, x:ノード):
        xがNoneまたはx.is_root()が 真実：
戻る  
 
        y = x.親
        yが正しい場合 は  not x: # 右の子だけが左に回転できる
戻る  
 
        p = y.親
        pが なしではない:
            p.leftの場合  yは:
                p.左= x
それ以外：
                p.右= x
それ以外：
            自己._root = x 
 
        y.右= x.左 
        x.左= y

上記のコード実装をテストするには、まず cabbage の値を変更してから、上記のコードを呼び出します。

キャベツ._優先度 = 75
 print( "-------左回転前--------" )
 print_treap(ルート)
 treap.left_rotate(キャベツ)
 print( "-------左回転後----------" )
 print_treap(ルート)

コードを実行した後の出力は次のようになります。

 -------左回転前--------  
 (小麦粉、10) 親: なし左: (ビール、76)右: なし
(ビール、76) 親: (小麦粉、10)左: (ベーコン、95)右: (キャベツ、75)
 (ベーコン、95) 親: (ビール、76)左: なし右: なし
(キャベツ、75) 親: (ビール、76)左: (バター、86)右: (卵、129)
 (バター、86) 親: (キャベツ、75)左: なし右: なし
(卵、129) 親: (キャベツ、75)左: なし右: なし
-------左回転後---------  
 (小麦粉、10) 親: なし左: (キャベツ、75)右: なし
(キャベツ、75) 親: (小麦粉、10)左: (ビール、76)右: (卵、129)
 (ビール、76) 親: (キャベツ、75)左: (ベーコン、95)右: (バター、86)
 (ベーコン、95) 親: (ビール、76)左: なし右: なし
(バター、86) 親: (ビール、76)左: なし右: なし
(卵、129) 親: (キャベツ、75)左: なし右: なし

出力結果の説明は、上図の左回転後の結果と一致しています。 Treap は要素のキーを基準にソートされたバイナリ ツリーであるため、文字列を指定すると、その文字列が Treap 内にあるかどうかを簡単に照会できます。その本質はソートされたバイナリ ツリーの検索であり、ここではその実装については無視します。

クエリはシンプルですが、挿入後に新しいノードとその親ノードが小さいヒープのプロパティに違反する可能性があるため、ノードの挿入は少し面倒です。したがって、挿入が完了した後も、上記で実装した左回転または右回転を使用して調整する必要があります。