我理解二叉搜索树是如何实现的,但我不确定在大多数编程语言已经内置到其标准库中的哈希表中使用它有什么好处.
有人可以提供二叉搜索树可解决的现实问题的例子吗？
如何将二叉树就地转换为二叉搜索树,即我们不能使用任何额外的空间.
algorithm tree binary-tree binary-search-tree data-structures
对于给定的二叉树,找到最大的子树,它也是二叉搜索树？
例:
输入:
10
/ \
50 150
/ \ / \
25 75 200 20
/ \ / \ / \ / \
15 35 65 30 120 135 155 250
输出:
50
/ \
25 75
/ \ /
15 35 65
我正在阅读Peter Brass的高级数据结构.
在关于搜索树的章节的开头,他说有两种搜索树模型 - 一种是节点包含实际对象(如果树用作字典的值),另一种是所有对象存储在叶子和内部节点仅用于比较.
第二个模型比第一个模型有什么优势？
是否有可能在BST上进行迭代按顺序遍历,其中BST的节点有父指针(根的父节点null),而不使用visited标志或stack？
我用谷歌搜索,没有找到答复.重点是,我怎么能知道 - 在某个节点 - 我刚刚来到它而已经完成了它下面的一切？
iteration algorithm tree-traversal inorder binary-search-tree
我知道有一些方法可以从预先遍序遍历(作为数组)构造树.考虑到有序和预订遍历,更常见的问题是构造它.在这种情况下,虽然顺序遍历是多余的,但它确实使事情变得更容易.任何人都可以告诉我如何进行后期遍历？迭代和递归解决方案都是必需的.
我尝试使用堆栈迭代地执行它,但根本无法正确地获得逻辑,因此得到了一个可怕的凌乱的树.同样去递归.
我已经探索了T树和B-/B +树的定义.从网上的论文中我了解到B-tree在分层内存中表现更好,例如磁盘驱动器和缓存内存.
我无法理解的是为什么T树甚至用于平坦记忆？
它们被宣传为AVL树的节省空间的替代品.
在最坏的情况下,T树的所有叶节点只包含一个元素,并且所有内部节点都包含允许的最小量,接近满.这意味着平均只使用分配空间的一半.除非我弄错了,当B树的节点半满时,这与B树的最坏情况相同.
假设两个树都在节点中本地存储密钥,但是使用指针来引用记录,唯一的区别是B树必须存储每个分支的指针.这通常会导致高达50%的开销或更少(超过T树),具体取决于密钥的大小.实际上,这接近于AVL树中预期的开销,假设没有父指针,嵌入在节点中的记录,嵌入在记录中的键.这是阻止我们使用B树的预期效率增益吗？
T树通常在AVL树之上实现.AVL树比B树更平衡.这可以与T树的应用相关联吗？
在研究遍历二叉搜索树的任何算法的复杂性时,我看到两种表达同一事物的不同方式:
版本#1:最坏情况下的遍历算法比较树的每个高度一次; 因此复杂性是O(h).
版本#2:最坏情况下的遍历算法比较树的每个高度一次; 因此复杂性是O(logN).
在我看来,相同的逻辑在起作用,但不同的作者使用其中任何一个logN或h.有人可以向我解释为什么会这样吗？
使用数组实现Hashtable时,我们继承了数组的常量时间索引.使用二进制搜索树实现Hashtable的原因是什么,因为它提供了使用O(logn)的搜索？为什么不直接使用二进制搜索树？
我已经创建了一个算法,其目的应该是,在BST中给定两个节点A和B,它通过简单地移动指针来切换两者中的角色(或树中的位置).在我对BST的表示中,我使用双链接连接(即A.parent == B和(B.left == A)或(B.right == A)).我不确定它是否完全正确.我在两种情况下划分了算法.
A和B直接连接(A是B的父级,B是B的父级)
所有其他情况
对于以前的每个案例,我都创建了一个嵌套函数.我想首先考虑算法的正确性,如果我能以某种方式改进它.这是代码:
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 …