2
私はバイナリ検索ツリーを持っており、このツリーの高さを取得しようとしています。 insert_element（self、value）を実行するたびにインクリメントするself.height属性があり、remove_element（self、value）が発生するとデクリメントされます。しかし、私は、メソッドの1つが発生するたびに増減することに気づき、ノードが高さを変更しない同じ高さにあった場合は考慮しません。バイナリ検索ツリーで一定の時間内に高さを取得する方法は？
class Binary_Search_Tree:
class __BST_Node:
def __init__(self, value):
self.value = value
self.lchild = None
self.rchild = None
def __init__(self):
self.__root = None
self.height = 0
def insert_element(self, value):
self._insert(self.__root, value)
def _insert(self, root, value):
node = Binary_Search_Tree.__BST_Node(value)
if root == value:
raise ValueError("Value already exists")
if self.__root is None:
self.__root = Binary_Search_Tree.__BST_Node(value)
self.height += 1
return self.__root
else:
if root.value > node.value:
if root.lchild is None:
root.lchild = node
self.height += 1
return root.lchild
else:
self._insert(root.lchild, value)
elif root.value < node.value:
if root.rchild is None:
root.rchild = node
self.height += 1
return root.rchild
else:
self._insert(root.rchild, value)
return root
def remove_element(self, value):
self.__root = self._remove(self.__root, value)
self.height -= 1
return self.__root
def _remove(self, root, value):
if self.__root is None:
raise ValueError("Tree is empty")
if root.value != value:
raise ValueError("No such value")
if root.value == value:
if root.lchild is None and root.rchild is None:
root = None
self.height -= 1
return root
elif root.lchild is None or root.rchild is None:
if root.lchild is None:
self.height -= 1
return root.rchild
if root.rchild is None:
self.height -= 1
return root.lchild
elif root.lchild and root.rchild:
parent = root
successor = root.rchild
while successor.lchild:
parent = successor
successor = successor.lchild
root.value = successor.value
if parent.lchild == successor:
parent.lchild = successor.rchild
self.height -= 1
return parent.lchild
else:
parent.rchild = successor.rchild
self.height -= 1
return parent.rchild
else:
if root.value > value:
if root.lchild:
root.lchild = self._remove(root.lchild, value)
elif root.value < value:
if root.rchild:
root.rchild = self._remove(root.rchild, value)
return root
def in_order(self):
if self.__root is not None:
self._in(self.__root)
def _in(self, root):
if root is None:
return
if root is not None:
self._in(root.lchild)
print(str(root.value))
self._in(root.rchild)
def get_height(self):
print(str(self.height))
def __str__(self):
return self.in_order()
if __name__ == '__main__':
pass
回答があります（https://stackoverflow.com/a/15193346/3350448）。 – PidgeyUsedGust
一方、 'if root == value：'を挿入すると、既存の値を間違って処理します。また、ノード要素を実際に作成してから、値を比較してどこにあるべきかを評価するべきではありません。 –