＃datastructure-Java

SplayTree-Pythonの実装



Splaytree Python Implementation



記事のディレクトリ

参照：https：//www.geeksforgeeks.org/splay-tree-set-2-insert-delete/

スプレーツリーの特徴

二分探索木（BST）操作の最悪の場合の時間計算量はO（n）です。最悪の事態は、木が傾いているときに起こります。 AVLと赤黒木を通して、最悪の場合の時間計算量O（ログ）を取得できます。
実際のアプリケーションでは、AVLや赤黒木よりもうまくいくことができますか？
AVLや赤黒木と同様に、スプレー木も自己平衡BSTです。 スプレーツリーの主なアイデアは、最近アクセスしたアイテムをツリーのルートに配置することです。これにより、最近検索したアイテムにO（1）時間で再びアクセスできるようになります。 。アイデアは、引用された場所を使用することです（通常のアプリケーションでは、 訪問の80％はアイテムの20％です ）。数百万または数十億のキーがあるが、頻繁にアクセスされるキーはごくわずかであるという状況を想像してみてください。これは、多くの実際のアプリケーションで発生する可能性が非常に高いです。すべてのスプレーツリー操作の平均実行時間はO（log n）です。ここで、nはツリー内のエントリの数です。最悪の場合、操作には（n）時間がかかります。



探す

検索またはスプレー操作は、検索されたキーをツリーのルート位置に移動するだけでなく、BSTのバランスを取ります。

インサート

スプレーツリーにキーkを挿入するさまざまなケースを次に示します。



  1. ルートはなし：新しいノードを割り当てて、ルートノードとして返すだけです。
  2. 与えられたキーkを広げます。kがすでに存在する場合、それは新しいルートになります。存在しない場合は、最後にアクセスしたリーフノードが新しいルートになります。
  3. 新しいルートのキーがkと同じである場合、kはすでに存在するため、操作を実行しないでください。
  4. それ以外の場合は、新しいノードにメモリを割り当て、ルートキーをkと比較します。
  5. kがrootのキーよりも小さい場合、rootは新しいノードの右の子であり、rootの左の子を新しいノードの左の子にコピーし、rootの左の子をNoneにコピーします。
  6. kがrootのキーより大きい場合、rootは新しいノードの左の子ノードとして使用され、rootの右の子ノードを新しいノードの右の子ノードとしてコピーし、rootの右の子ノードをNoneとしてコピーします。
  7. 新しいノードをツリーの新しいルートとして返します。

誘導

  1. スプレー木は局所性が良い。頻繁に訪れるアイテムは簡単に見つかります
  2. すべてのスプレーツリー操作には、平均してO（ログ）時間がかかります。一連の操作（空のツリーから開始すると仮定）では、各操作の平均実行時間はO（log n）であることを厳密に示すことができます。
  3. AVLや赤黒木と比較すると、各ツリーノードに追加のフィールドが必要ないため、スプレーツリーは単純です。
  4. AVLツリーとは異なり、スプレーツリーは読み取り専用操作（検索など）で変更できます。

コード

class Node(object): def __init__(self,key): self.key = key self.left = None self.right = None class SplayTree(object): def __init__(self): self.root = None self.size = 0 def RightRotate(self,x): # x is the root node y = x.left x.left = y.right y.right = x return y def LeftRotate(self,x): # x is the root node y = x.right x.right = y.left y.left = x return y def splay(self,root,key): ''' If the key exists in the tree, place the key at the root of the tree If the key does not exist, the last item accessed will be placed at the root of the tree ''' if root is None or root.key == key: # If there is no root or the root of the tree is key, splay the root return root if root.key > key: # key in the left subtree if root.left is None: # Left subtree is empty, then return to the only visited root node return root if root.left.key > key: # Zig-Zig (Left Left) # First recursively move the key to the root of the left subtree of the left subtree root.left.left = self.splay(root.left.left,key) # Right-hand root rotation for the first time, and right-hand rotation is possible only after performing else root = self.RightRotate(root) elif root.left.key < key: # Zig-Zag (Left Right) root.left.right = self.splay(root.left.right,key) root.left = self.LeftRotate(root.left) # LR situation: the root after adjustment is right-handed return root if root.left is None else self.RightRotate(root) else: # key in the right subtree if root.right is None: # The right subtree is empty, it returns the only visited root node return root if root.right.key > key: # Zig-Zag (Right Left) # First recursively move the key to the root of the left subtree of the right subtree root.right.left = self.splay(root.right.left,key) if root.right.left: root.right = self.RightRotate(root.right) elif root.right.key < key: # Zag-Zag (Right Right) root.right.right = self.splay(root.right.right,key) root = self.LeftRotate(root) # RL situation: left-handed root after adjustment return root if root.right is None else self.LeftRotate(root) def search(self,key): self.root = self.splay(self.root,key) def insert(self,key): self.size += 1 return self._insert(self.root,key) def _insert(self,root,key): if root is None: # Data gap situation return Node(key) # Like accessing the node to be accessed is placed on the root node root = self.splay(root,key) if root.key == key: # If the root node == key, then directly return to the root node return root new = Node(key) if root.key > key: # If the key of the root node> key, then the root node is taken as its right subtree, and the left subtree of the root node is taken as the left subtree of new new.right = root new.left = root.left root.left = None else: new.left = root new.right = root.right root.right = None return new # Return to the new root node def preorder(self, subtree): if subtree is not None: print(subtree.key, end=' ') self.preorder(subtree.left) self.preorder(subtree.right) if __name__=='__main__': sp = SplayTree() sp.root = sp.insert(100) sp.root =sp.insert(50) sp.root =sp.insert(200) sp.root =sp.insert(40) sp.root =sp.insert(30) sp.root =sp.insert(20) sp.root =sp.insert(25) print('Preorder Traversal:') sp.preorder(sp.root) # 25 20 30 40 50 100 200 sp.search(200) print(' nCurrent root node:',sp.root.key) # 200 print('Preorder Traversal:') sp.preorder(sp.root) # 200 30 25 20 50 40 100