- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我创建了一个算法,其目的应该是,给定 BST 中的两个节点 A 和 B,它通过简单地移动指针来切换两者的角色(或树中的位置)。在我对 BST 的表示中,我使用了双链接连接(即 A.parent == B 和(B.left == A)或(B.right == A))。我不确定它是否完全正确。我把算法分为两种情况。
A 和 B 直接相连(A 是 B 的父级或 B 是 A 的父级)
所有其他情况
对于前面的每个案例,我都创建了一个嵌套函数。我想首先了解您对算法正确性的看法,如果我能以某种方式改进它。这是代码:
def switch(self, x: BSTNode, y: BSTNode, search_first=False):
if not x:
raise ValueError("x cannot be None.")
if not y:
raise ValueError("y cannot be None.")
if x == y:
raise ValueError("x cannot be equal to y")
if search_first:
if not self.search(x.key) or not self.search(y.key):
raise LookupError("x or y not found.")
def switch_1(p, s):
"""Switches the roles of p and s,
where p (parent) is the direct parent of s (son)."""
assert s.parent == p
if s.is_left_child():
p.left = s.left
if s.left:
s.left.parent = p
s.left = p
s.right, p.right = p.right, s.right
if s.right:
s.right.parent = s
if p.right:
p.right.parent = p
else:
p.right = s.right
if s.right:
s.right.parent = p
s.right = p
s.left, p.left = p.left, s.left
if s.left:
s.left.parent = s
if p.left:
p.left.parent = p
if p.parent:
if p.is_left_child():
p.parent.left = s
else:
p.parent.right = s
else: # p is the root
self.root = s
s.parent = p.parent
p.parent = s
def switch_2(u, v):
"""u and v are nodes in the tree
that are not related by a parent-son
or a grandparent-son relantionships."""
if not u.parent:
self.root = v
if v.is_left_child():
v.parent.left = u
else:
v.parent.right = u
elif not v.parent:
self.root = u
if u.is_left_child():
u.parent.left = v
else:
u.parent.right = v
else: # neither u nor v is the root
if u.is_left_child():
if v.is_left_child():
v.parent.left, u.parent.left = u, v
else:
v.parent.right, u.parent.left = u, v
else:
if v.is_left_child():
v.parent.left, u.parent.right = u, v
else:
v.parent.right, u.parent.right = u, v
v.parent, u.parent = u.parent, v.parent
u.left, v.left = v.left, u.left
u.right, v.right = v.right, u.right
if u.left:
u.left.parent = u
if u.right:
u.right.parent = u
if v.left:
v.left.parent = v
if v.right:
v.right.parent = v
if x.parent == y:
switch_1(y, x)
elif y.parent == x:
switch_1(x, y)
else:
switch_2(x, y)
我真的需要 switch
在所有情况下都能正常工作,无论我们选择哪个节点 x
或 y
。我已经做了一些测试,它似乎有效,但我仍然不确定。
编辑
最后,如果它以某种方式有帮助,这里你有我的 BST 的完整实现(我正在做的测试):
编辑 2(只是出于好奇)
@Rishav 评论道:
I do not understand the intention behind this function.. if it is to swap two nodes in the BST, is it not sufficient to swap their data instead of manipulating pointers?
我回答:
Ok, maybe I should have added a little bit more about the reason behind all this "monster" function. I can insert
BSTNode
objects or any comparable objects in my BST. When the user decides to insert any comparable object, the responsibility of creating theBSTNode
is mine, therefore the user has no access to a initialBSTNode
reference, unless they search for the key. But aBSTNode
would only be returned after the insertion of the key, or there's already anotherBSTNode
object in the tree with the same key (or value), but this latter case is irrelevant.The user can also insert a
BSTNode
object in the tree which has an initial (and should remain constant) key (or value). Nevertheless, if I just exchanged the values or keys of the nodes, the user would have a reference to a node with a different key then the key of the node he inserted. Of course, I want to avoid this.
最佳答案
您需要适当的单元测试。我推荐python-nose - 非常易于使用。
至于测试向量,我建议使用两个节点 a 和 b 的所有可能组合:
对于 BST 树,您有 3 种类型的节点:
结合以下其他情况:
以及它们的组合(也在对称情况下)。
然后在交换之后你需要检查所有涉及的节点,即:a,b,a 和 b 的 child ,a 和 b 的 parent ,如果一切按计划进行的话。
我会使用包含所有类型节点的小树来做到这一点。然后遍历节点的所有可能组合并交换节点并检查预期结果,然后再次交换以使树恢复到其原始状态。
[编辑]
如果您的问题是如何避免所有繁琐的工作。您可以考虑寻找一些完善的 BST 实现并将结果与您的函数进行比较。可以通过使用准备好的树并生成该树的所有可能节点对来自动创建向量。
[/编辑]
至于函数的不需要的输入。你需要发挥你的想象力,尽管在我看来你已经涵盖了大多数情况。除了 Austin Hastings 提到的至少一个输入节点不属于树的那个。
我找到了为我的一个私有(private)项目编写的相同函数的旧版本,也许你会发现它有用:
def swap( a, b ):
if a == b: return
if a is None or b is None: return
#if a not in self or b not in self: return
if b.parent == a:
a, b = b, a
#swap connections naively
a.parent, b.parent = b.parent, a.parent
a.left, b.left = b.left, a.left
a.right, b.right = b.right, a.right
if b.parent == b: #b was the p of a
b.parent = a
if a.parent is not None:
if a.parent.left == b: a.parent.left = a
else: a.parent.right = a
else:
self.root = a
if b.parent is not None:
if b.parent.left == a: b.parent.left = b
else: b.parent.right = b
else:
self.root = b
if a.right is not None: a.right.parent = a
if a.left is not None: a.left.parent = a
if b.right is not None: b.right.parent = b
if b.left is not None: b.left.parent = b
和性能优化版本:
def swap_opt( a, b ):
if a == b: return
if a is None or b is None: return
#if a not in self or b not in self: return
if b.p == a:
a, b = b, a
#swap connections naively
a.p, b.p = b.p, a.p
a.l, b.l = b.l, a.l
a.r, b.r = b.r, a.r
if b.p == b: #b was the p of a
b.p = a
if a.l == a:
a.l = b
if a.r is not None: a.r.p = a
else:
a.r = b
if a.l is not None: a.l.p = a
if b.r is not None: b.r.p = b
if b.l is not None: b.l.p = b
if a.p is not None:
if a.p.l == b: a.p.l = a
else: a.p.r = a
else:
#set new root to a
pass
else:
if a.r is not None: a.r.p = a
if a.l is not None: a.l.p = a
if b.r is not None: b.r.p = b
if b.l is not None: b.l.p = b
if a.p is not None:
if a.p.l == b: a.p.l = a
else: a.p.r = a
else:
#set new root to a
pass
if b.p is not None:
if b.p.l == a: b.p.l = b
else: b.p.r = b
else:
#set new root to b
pass
我没有对这段代码进行适当的单元测试——它按我预期的那样工作。我对实现之间的性能差异更感兴趣。swap_opt
处理相邻节点的速度稍快一些,与 swap
的紧凑实现相比,速度提高了大约 5%。 [EDIT2] 但这取决于用于测试和硬件的树 [/EDIT2]
关于python - 交换从树移动指针中随机选择的两个节点的角色的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35141893/
抱歉,问题标题含糊不清!我有一个 ASP.NET 应用程序,可与其他第三方软件配合使用(Burning Glass - 通过 tcp/ip 连接到 Web 应用程序,需要 - 正确配置的 dns 条目
我正在开展一个项目,将一个大型网站分解为更小、更具体的网站。我需要能够将对这些网站的访问限制为仅具有必要权限的用户,并且希望尽可能利用现有的成员资格/角色数据模型。 因此,理想情况下,我想将潜在的多个
抱歉,问题标题含糊不清!我有一个 ASP.NET 应用程序,可与其他第三方软件配合使用(Burning Glass - 通过 tcp/ip 连接到 Web 应用程序,需要 - 正确配置的 dns 条目
我对 FOSUserBundle 中的角色有点困惑。用户实体也有角色列,我们可以通过它为用户分配多个角色。根据发布在 Managing users/roles/groups in FOSUserBun
原谅我的新手问题,但我想按顺序执行三个任务并在剧本中使用两个角色: 任务 角色 任务 角色 任务 这是我到目前为止(任务,角色,任务): --- - name: Task Role Task ho
在触发器中,我想检查哪些角色对 USER() 有效,而不是 CURRENT_USER()。(认识到 CURRENT_USER() 返回触发器的 DEFINER)。 是否有任何类型的 USER_ROLE
我有一套Ansible playbooks 和主要的 yml 文件是这样的 - hosts: all roles: - common - install_nginx 我想在触发剧本
因此,我有以下代码输出安装的所有功能和角色: Import-Module ServerManager $Arr = Get-WindowsFeature | Where-Object {$_.Inst
我已经寻找了一段时间,并且已经手动完成了角色和权限的许多部署,但是有什么方法可以在Sitecore中为角色/权限创建一个程序包(或等效程序包)? 当您没有选择从一个环境到另一个环境进行完全部署时,使用
我想找到或创建一个与所有者或至少贡献者具有相同功能的 azure 角色。但此角色不应该有权创建 azure 资源。 我一直在浏览现有的预定义角色。 最佳答案 这在 Azure RBAC 上下文中没有任
我在文档中找不到答案,也找不到示例:是否可以在 role/defaults/ 中命名除 main.yml 之外的文件?我的意思是,main.yml 是具有默认值的文件的唯一有效名称吗? 最佳答案 根据
我尝试了kubectl get sa default命令,但只看到一些非常基本的值。在k8s中查看与特定服务帐户关联的权限/角色的命令是什么? 最佳答案 以下命令可能会有所帮助。它基本上获得RoleB
有没有办法告诉 Spring 在我制作的自定义用户 bean 中找到用户的角色? http://static.springsource.org/sprin...ns-config.html 因此,如果
在我的 playbook 中运行几次 Play 后,我想验证我的应用程序的部署。 在我的角色之一中,我有以下任务,将创建的 ec2 实例添加到“已启动”的主机: - name: Add new ins
我按如下方式将用户添加到角色(请注意,我在我的机器上运行下面显示的代码): Roles.AddUserToRole(oMU.UserName, "Role1"); 使用以下代码我检查用户是否在
我目前在为 postgresql 创建角色时遇到问题,这是我已经做过的,但自昨晚以来取得了任何进展 simplybel@simplybel:~$ sudo -u postgres createuser
一个项目现在有超过 200 个类,每个文件一个类,将它们划分到目录中似乎是恰当的。现在我正在考虑两种不同的策略; a) 按角色或层分组 repositories/ UserRepository
您如何为用户、角色和应用特定实体提供种子?似乎 IdentityModel 以它自己的上下文为目标? internal sealed class Configuration : DbMigration
摩尔庄园手游在六一儿童节上线之后,网上的争议声还是很多的,有夸赞的,称其找回了童年的回忆,也有吐槽的,觉得3d的设计很晕,没有以前的感觉,想要删除账号,那么大家知道怎么去注销吗,步骤流程是什么样的?
在 XP SP2 虚拟机中运行 Oracle 11gR1。完全披露:这是一项任务。 我试图在用户被授予 DBA 角色时进行审计,并在事件发生时发送电子邮件。 我相信命令 AUDIT DBA;将审核对
我是一名优秀的程序员,十分优秀!