python - 连接到父循环的 BST
问题描述
我在 getMinimal() 方法中遇到无限循环问题。它以这种方式工作:1)获取节点,2)如果节点左侧有其他节点 - 转到另一个。3)重复直到节点在左侧有某物 4)返回最小节点。
但有时它会在无限循环中工作,例如从 1000 到 400,然后到 4,然后到 1000!我不知道我在哪里犯错。我多次查看此代码,每个指向父/左/右节点的“指针”都可以!请帮忙。算法适用于“手写”树 - ~20nodes。我想在更好的情况下测试它——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))
让它运行,一段时间后它很可能会找到一个小例子。这将极大地帮助调试。
推荐阅读
- activejdbc - 当以编程方式触发运行时异常时,事务不会回滚
- adobe - Photoshop CC 有自动上传功能吗?
- mongodb - 公开一个 Java Spring Boot 方法
- c# - SqlClient.SqlException:对象名称无效
- c++ - 为什么 CAF system.registry() 应该在 put(atom_value) 之后自动调用 erase(atom_value)
- javascript - 使用没有 sheet.js 或 spread.js 的 Javascript 从 xlsx 读取大数据
- cluster-analysis - 相同设置的 Weka 聚类结果不同
- hadoop - 如何在 Hadoop 2.7.6 上安装 Snappy?
- database - 我正在尝试在 sdf 文件中创建函数并出现错误:在错误函数中解析查询令牌时出错
- html - 为什么我的标题没有在纵向上一直穿过?