我在 getMinimal() 方法中遇到无限循环问题。它的工作原理是这样的: 1)取节点, 2)如果节点左侧还有其他节点 - 转到其他节点。 3)重复直到节点左侧有某物 4)返回最小节点。
但有时它会无限循环,例如从 1000 到 400,然后到 4,然后..到 1000!我不知道我在哪里犯了错误。我多次检查了这段代码,每个指向父/左/右节点的“指针”都没有问题!请帮忙。 算法适用于“手写”树 - ~20 个节点。我想在更好的情况下测试它 - 2500 个节点,由随机库生成(从 -10k 到 10k)。
import random
class Node:
def __init__(self, val):
self.val = val
self.parent = None
self.right = None
self.left = None
# Class of node.
def str(self):
return str(self.val)
class MyTree:
def __init__(self, node):
self.root = node
def insert(self, node):
current = self.root
a = True
while a:
if node.val > current.val:
if current.right is not None:
current = current.right
continue
else:
current.right = node
node.parent = current
a = False
if node.val <= current.val:
if current.left is not None:
current = current.left
continue
else:
current.left = node
node.parent = current
a = False
def search(self, node):
current = self.root
while node.val != current.val:
if node.val > current.val:
current = current.right
continue
elif node.val <= current.val:
current = current.left
continue
if node.val == current.val:
return current
else:
print("There is no such node!")
def delete(self, node):
if isinstance(node, (float, int)):
node = self.search(node)
if node is self.root:
self.__deleteRoot()
return
else:
if node.right is None and node.left is None:
self.__deleteNN(node)
return
if node.right is None and node.left is not None:
self.__deleteLN(node)
return
if node.right is not None and node.left is None:
self.__deleteNR(node)
return
if node.right is not None and node.left is not None:
self.__deleteLR(node)
return
def __deleteNN(self, node):
if node.parent.left is node:
node.parent.left = None
if node.parent.right is node:
node.parent.right = None
def __deleteLN(self, node):
parent = node.parent
son = node.left
# parent replaced
if parent.left is node:
parent.left = son
if parent.right is node:
parent.right = son
son.parent = parent
def __deleteNR(self,node):
parent = node.parent
son = node.right
# replace parent
if parent.left is node:
parent.left = son
if parent.right is node:
parent.right = son
son.parent = parent
def __deleteLR(self, node):
minimal = self.getMinimal(node.right)
if minimal.parent.left is minimal:
minimal.parent.left = None
if minimal.parent.right is minimal:
minimal.parent.right = None
# parent of minimal done..
if node.parent.left is node:
node.parent.left = minimal
if node.parent.right is node:
node.parent.right = minimal
minimal.right = node.right
minimal.left = node.left
def getMinimal(self, node):
k = node
while k.left is not None:
k = k.left
return k
def getMax(self):
current = self.root
while current.right:
current = current.right
return current
def __trav(self, node):
if not node:
return
print(node.val)
self.__trav(node.left)
self.__trav(node.right)
def printTrav(self):
self.__trav(self.root)
def __deleteRoot(self):
if self.root.left is None and self.root.right is None:
self.root = None
return
if self.root.left is None and self.root.right is not None:
# left empty,right full
self.root.right.parent = None
self.root = self.root.right
return
if self.root.left is not None and self.root.right is None:
# right empty, left full
self.root.left.parent = None
self.root = self.root.left
return
# node has both children
if self.root.left is not None and self.root.right is not None:
temp = self.getMinimal(self.root.right) # minimal from right subtree
# sometimes it could be like this..
# r
# \
# x
if temp.parent.left is temp:
temp.parent.left = None
else:
temp.parent.right = None
self.root.left.parent = temp
self.root.right.parent = temp
temp.right = self.root.right
temp.left = self.root.left
self.root = temp
self.root.parent = None
return
def search(self, val):
node = self.root
if node.val == val:
return node
if val > node.val and node.right is not None:
node = node.right
if val < node.val and node.left is not None:
node = node.left
else:
print("There's no such value!")
return
def printMax(self):
print(self.getMax().val)
def printMin(self):
print(self.getMinimal(self.root).val)
arr=[None]*2500
for x in range(2500):
arr[x]=Node(random.randint(-10000,10000))
myTree = MyTree(arr[0])
for x in range(1,2500):
myTree.insert(arr[x])
for x in range(2500):
myTree.delete(arr[x])
最佳答案
您两次定义 search
很可疑。
尽管如此,这就是我如何调试它。我会修改你的程序以从文件中读取,尝试运行,然后检测无限循环并退出。现在写入随机文件,直到出现导致崩溃的文件为止。
一旦你有了一个显示错误的随机文件,下一步就是将其最小化。这是一个可以让您做到这一点的安全带。
import itertools
flatten = itertools.chain.from_iterable
# bug_found should be a function that takes a list of elements and runs your test.
# example should be an array that demonstrates the bug.
def find_minimal (bug_found, example):
parts = [example]
while 1 < max(len(part) for part in parts):
i = 0
while i < len(parts):
if 1 == len(parts[i]):
i = i + 1
else:
part = parts.pop(i)
# Divide in 2.
mid = len(part)/2
part1 = part[0:mid]
part2 = part[mid:len(part)]
# Do we need part1?
parts.insert(i, part1)
if bug_found(flatten(parts)):
i = i + 1
parts.insert(i, part2)
else:
parts[i] = part2
# Do we need part2?
if bug_found_func(flatten(parts)):
i = i + 1
else:
parts.pop(i)
return list(flatten(parts))
只要让它运行,一段时间后它可能会找到一个小例子。这将极大地帮助调试。
关于python - 连接到父循环的 BST,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59111461/