アルゴリズム-[ツリーを検索]

6693 ワード

ツリー
ツリーは、次の性質を持つツリーです.
  • 左サブツリーが空でない場合、左サブツリー上のすべてのノードの値は、そのルートノードの値以下または等しい.
  • 右サブツリーが空でない場合、右サブツリー上のすべてのノードの値は、そのルートノードの値以上です.
  • 左,右サブツリーもそれぞれ二叉ルックアップツリーである.
  • キー値が等しいノードはありません.

  • 複雑度:
    アルゴリズム#アルゴリズム#
    へいきん
    へいきん
    スペース
    O(n)
    O(n)
    検索
    O(log n)
    O(n)
    挿入
    O(log n)
    O(n)
    削除
    O(log n)
    O(n)
    ノードの定義
    class BinarySearchTree(object):
        def __init__(self, data, left=None, right=None, parent=None):
            self.data = data
            self.left = left
            self.right = right
            self.parent = parent
    

    検索アクション
    二叉ルックアップツリーbでxをルックアップするプロセスは、以下のとおりである.
  • bが空のツリーであれば検索に失敗し、
  • そうでなければ、xがbのルートノードのデータドメインの値に等しい場合、検索は成功する.
  • そうでなければ、xがbのルートノードのデータドメインの値より小さい場合、左サブツリーを検索する.
  • それ以外の場合:右サブツリーを検索します.

  • 挿入アクション
    ノードsを2つのフォークルックアップツリーbに挿入するアルゴリズム.
  • bが空の木である場合、sで指すノードをルートノードとして挿入する、
  • .
  • それ以外の場合:s->dataがbのルートノードのデータドメインの値に等しい場合、
  • が戻る.
  • そうでない場合:s->dataがbのルートノードのデータドメインの値より小さい場合、sが指すノードを左サブツリーに挿入し、
  • .
  • そうでなければ、sが指すノードを右サブツリーに挿入します.(新しい挿入ノードは常にリーフノード)
  • ステップの削除
  • BSTからノードを削除するのは、ノードを挿入するよりも難しい.非リーフノードを削除するには、ノードの削除によるツリーの破断を埋めるために他のノードを選択する必要があります.この破断を埋めるためにノードを選択しないと,BSTの性質要件に反する.
  • 削除ノードアルゴリズムの最初のステップは、削除するノードを特定することであり、前述した検索アルゴリズムを使用することができるため、実行時間はO(log)である­2n).次に、ノードを削除する代わりに適切なノードを選択する必要があります.これには、3つのケースが考えられます.

  • ケース1:削除されたノードがリーフノードである場合,そのノードの左サブツリーと右サブツリーはいずれも空のツリーである.葉の結点を削除して木全体の構造を破壊しないため、両親の結点のポインタを修正するだけでよい.ケース2:削除されたノードが左サブツリーまたは右サブツリーのみである場合、この場合、左サブツリーまたは右サブツリーを親ノードの左サブツリーまたは右サブツリーに直接するだけで、この変更を行っても二叉ルックアップツリーの特性を破壊しません.ケース3:削除されたノードの左サブツリーと右サブツリーが空でない場合、削除されたノードの右の子供に左の子供がいない場合、この右の子供は削除されたノードを置き換えるために使用されます.削除されたノードの右の子は、削除されたノードの左のサブツリーのすべてのノードよりも大きく、削除されたノードの親ノードよりも大きいか小さいため、削除されたノードが左の子か右の子かによっても異なります.したがって,削除されたノードを右の子で置き換え,二叉ルックアップツリーの性質に合致する.削除されたノードの右の子に左の子がいる場合は、削除されたノードの右の子の左の子ツリーの一番下のノードで置き換える必要があります.つまり、削除されたノードの右の子ツリーの最小値のノードで置き換えます.
    ループステップ
    最初の順序、中の順序、後の順序
    コード実装
    class BinarySearchTree(object):
        def __init__(self, data, left=None, right=None, parent=None):
            self.data = data
            self.left = left
            self.right = right
            self.parent = parent
    class BST(object):
        def __init__(self):
            self.root = None
            self.size = 0
        def lenght(self):
            return self.size
        def find(self, key):
            if self.root:
                result = self._find(key, self.root)
                if result:
                    return result
                else:
                    return None
            else:
                None
        def _find(self, key, node):
            if not node:
                return None
            elif node.data == key:
                return node
            elif key < node.data:
                return self._find(key, node.left)
            else:
                return self._find(key, node.right)
        def insert(self, key):
            node = BinarySearchTree(key)
            if not self.root:
                self.root = node
                self.size += 1
            else:
                currentNode = self.root
                while True:
                    if key < currentNode.data:
                        if currentNode.left:
                            currentNode = currentNode.left
                        else:
                            currentNode.left = node
                            node.parent = currentNode
                            self.size += 1
                            break
                    elif key > currentNode.data:
                        if currentNode.right:
                            currentNode = currentNode.right
                        else:
                            currentNode.right = node
                            node.parent = currentNode
                            self.size += 1
                            break
                    else:
                        break
        def findMin(self):
            if self.root:
                return self._findMin(self.root)
            else:
                return None
        def findMax(self):
            if self.root:
                currentNode = self.root
                while currentNode.right:
                    currentNode = currentNode.right
                return currentNode
            else:
                return None
    
        def _findMin(self, node):
            if node:
                currentNode = node
                while currentNode.left:
                    currentNode = currentNode.left
                return currentNode
        def delete(self, key):
            if self.size > 1:
                nodeToDelete = self.find(key)
                if nodeToDelete:
                    self._delete(nodeToDelete)
                    self.size -= 1
                else:
                    raise KeyError('Error, key not in tree')
            elif self.size == 1 and self.root.data == key:
                self.root = BinarySearchTree(None)
                self.size = 0
            else:
                raise KeyError('Error, key not in tree')
        def _delete(self, node):
            if not node.left and node.right: #node   
                if node == node.parent.left: #node        
                    node.parent.left = None
                else:
                    node.parent.right = None
            elif node.right and node.left: #node     
                minNone = self._findMin(node.right)
                node.data = minNone.data
                self._delete(minNone)
            else: #node     
                if node.left: #node    
                    if node.parent and node.parent.left == node: #node        
                        node.left.parent = node.parent
                        node.parent.left = node.left
                    elif node.parent and node.parent.right == node: #node        
                        node.left.parent = node.parent
                        node.parent.right = node.left
                    else:  # node  
                        self.root = node.left
                        node.left.parent = None
                        node.left = None
                else:
                    if node.parent and node.parent.left == node:
                        node.right.parent = node.parent
                        node.parent.left = node.right
                    elif node.parent and node.parent.right == node:
                        node.right.parent = node.parent
                        node.parent.right = node.right
                    else:
                        self.root = node.right
                        node.right.parent = None
                        node.right = None
        def printTree(self):
            if self.size == 0:
                print("Empty Tree")
            else:
                self._printTree(self.root)
        def _printTree(self, node):
            if node: #    
                self._printTree(node.left)
                print(node.data)
                self._printTree(node.right)
    

    転載:二叉検索ツリーのpython実装
    公衆番号:アルゴリズム手記