アルゴリズム-[ツリーを検索]
6693 ワード
ツリー
ツリーは、次の性質を持つツリーです.左サブツリーが空でない場合、左サブツリー上のすべてのノードの値は、そのルートノードの値以下または等しい. 右サブツリーが空でない場合、右サブツリー上のすべてのノードの値は、そのルートノードの値以上です. 左,右サブツリーもそれぞれ二叉ルックアップツリーである. キー値が等しいノードはありません.
複雑度:
アルゴリズム#アルゴリズム#
へいきん
へいきん
スペース
O(n)
O(n)
検索
O(log n)
O(n)
挿入
O(log n)
O(n)
削除
O(log n)
O(n)
ノードの定義
検索アクション
二叉ルックアップツリー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:削除されたノードの左サブツリーと右サブツリーが空でない場合、削除されたノードの右の子供に左の子供がいない場合、この右の子供は削除されたノードを置き換えるために使用されます.削除されたノードの右の子は、削除されたノードの左のサブツリーのすべてのノードよりも大きく、削除されたノードの親ノードよりも大きいか小さいため、削除されたノードが左の子か右の子かによっても異なります.したがって,削除されたノードを右の子で置き換え,二叉ルックアップツリーの性質に合致する.削除されたノードの右の子に左の子がいる場合は、削除されたノードの右の子の左の子ツリーの一番下のノードで置き換える必要があります.つまり、削除されたノードの右の子ツリーの最小値のノードで置き換えます.
ループステップ
最初の順序、中の順序、後の順序
コード実装
転載:二叉検索ツリーのpython実装
公衆番号:アルゴリズム手記
ツリーは、次の性質を持つツリーです.
複雑度:
アルゴリズム#アルゴリズム#
へいきん
へいきん
スペース
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をルックアップするプロセスは、以下のとおりである.
挿入アクション
ノードsを2つのフォークルックアップツリーbに挿入するアルゴリズム.
ケース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実装
公衆番号:アルゴリズム手記