binary-search-tree相关内容

c ++从二叉搜索树中删除具有两个孩子的特定节点

我目前正在开发一个程序来处理 C++ 中的 BST.我的所有函数都在工作，除了 removeNode，它删除树中给定键值的节点.我认为前两种情况可行，但第三种情况给我带来了麻烦.我知道如何删除有两个孩子的节点的逻辑，但目前代码对我不起作用.这是节点 结构节点{整数键；节点*左；节点*对；}; 这里是删除函数的代码，以一个节点在底部有多个子节点的情况 node* Tree::removeKey ..

发布时间：2022-01-05 19:02:00 c++ tree binary-tree binary-search-tree C/C++开发

在 Haskell 中查找树是否是二叉搜索树

type BSTree a = BinaryTree adata BinaryTree a = Null |节点 (BinaryTree a) a (BinaryTree a)导出显示flattenTree :: 二叉树 a ->[一个]flattenTree 树 = 案例树空 ->[]节点左 val 右 ->(flattenTree 左) ++ [val] ++ (flattenTree 右) ..

发布时间：2022-01-05 18:55:56 haskell tree binary-tree binary-search-tree predicate 其他开发

二元运算符“>"的错误操作数类型?

我正在编写 BST 程序.我收到错误: "二元运算符的错误操作数类型">" 第一种类型:java.lang.Object 第二种类型:java.lang.Object" 这是它给我错误的方法: public void placeNodeInTree(TreeNode current, TreeNode t){如果(当前 == 空)当前 = t;别的{if(current. ..

发布时间：2022-01-05 18:53:16 java tree binary-search-tree Java开发

二叉树的第一个公共祖先

如果我有一个这样的二叉搜索树，那么节点 6 和 1 的最低共同祖先是什么? 解决方案 根据维基百科定义的最低共同祖先我纠正自己: 最低共同祖先(LCA)是图论中的一个概念，计算机科学.设 T 是一棵有 n 个节点的有根树.最低的共同祖先在两个节点 v 和 w 之间定义为最低T 中同时具有 v 和 w 作为后代的节点(我们允许一个节点成为自己的后代). 所以是的，按照这个定义，正 ..

发布时间：2022-01-05 18:50:35 algorithm data-structures tree binary-tree binary-search-tree 其他开发

在二叉搜索树中找到中位数

编写函数 T ComputeMedian() const 的实现，该函数在 O(n) 时间内计算树中的中值.假设树是 BST 但不一定是平衡的.回想一下，n 个数字的中位数定义如下:如果 n 是奇数，则中位数为 x，使得小于 x 的值的数量等于大于 x 的值的数量.如果 n 是偶数，则 1 加上小于 x 的值的数量等于大于 x 的值的数量.例如，给定数字 8、7、2、5、9，中位数为 7，因为有两 ..

发布时间：2022-01-05 18:48:27 algorithm tree binary-search-tree median 其他开发

将 n 个数字插入二叉搜索树的复杂度

我有一个问题，它说“计算将 n 个数字插入二叉搜索树的过程的紧时间复杂度".它并不表示这是否是平衡树.那么，对于这样的问题，可以给出什么样的答案呢?如果这是一棵平衡树，则高度为 logn，插入 n 个数字需要 O(nlogn) 时间.但这是不平衡的，在最坏的情况下甚至可能需要 O(n2) 时间.找到将 n 个数字插入 bst 的紧时间复杂度是什么意思?我错过了什么吗?谢谢 解决方案 即使树 ..

发布时间：2022-01-05 18:45:56 algorithm tree complexity-theory binary-search-tree asymptotic-complexity 其他开发

AVL 树上的二叉搜索树

据我所知 AVL 树和 二叉搜索树 在平均情况下是相同的，在最坏的情况下，AVL 会击败 BST.这给了我一个暗示，即 AVL 在与它们交互的所有可能方式中总是优于 BST，也许在平衡实现方面增加了一点复杂性. 是否有任何理由应该首先使用 BST 而不是 AVL? 解决方案 首先，获得最佳性能不是编程的最终目标.因此，即使选项 B 总是比 A 更快并且消耗的内存更少，但这并不意味着它 ..

发布时间：2022-01-05 18:44:34 performance data-structures tree binary-search-tree avl-tree 其他开发

证明平衡二叉搜索树的高度是 log(n)

二分搜索算法需要 log(n) 时间，因为树的高度(有 n 个节点)将为 log(n). 你将如何证明这一点? 解决方案 现在我没有给出数学证明.尝试理解使用log to base 2的问题.log2是计算机科学中log的正常含义. 首先理解它是二进制对数(log2n)(以2为底的对数).例如， 1 的二进制对数是 0 2 的二元对数是 1 3 的二进制对数是 1 ..

发布时间：2022-01-05 18:38:26 performance tree binary-search-tree 其他开发

将排序后的数组插入二叉搜索树

我想实现一种算法，将排序的数组插入到二叉搜索树中，但我不希望以只向一侧生长的树结束. 你有什么想法吗? 谢谢. 解决方案 这应该会给你一个平衡的树(在 O(n) 中): 为数组中的中间元素构造一个节点并返回它 (这将是基本情况下的根). 从数组左半部分的 1. 开始重复，将返回值分配给根的左子节点. 在数组的右半部分从 1. 开始重复，将返回值分配给根的右孩子. ..

发布时间：2022-01-05 18:28:09 algorithm sorting tree binary-tree binary-search-tree 其他开发

将二分查找展平为单向链表 [C]

我正在尝试将二叉搜索树展平为单向链表. 二叉搜索树: 6/\4 8/\ \1 5 11/10 扁平单向链表: 1 ->4 ->5 ->6 ->8 ->10 ->11 由于某种原因，我似乎无法弄清楚这一点. 我有一个树节点的结构: typedef 结构节点 {整数键；结构节点 *left;结构节点*右；节点； 我有一个函数来为树节点创建和分配内存: Node* newNo ..

发布时间：2022-01-01 18:48:28 c linked-list binary-search-tree 其他开发

链表和二叉搜索树的区别

链表和二叉搜索树的主要区别是什么?BST 只是维护 LinkedList 的一种方式吗?我的导师谈到了 LinkedList 和 BST，但没有比较它们，也没有说明何时更喜欢一个而不是另一个.这可能是一个愚蠢的问题，但我真的很困惑.如果有人能以简单的方式澄清这一点，我将不胜感激. 解决方案 链表: Item(1) ->项目(2) ->第 (3) 项 ->第 (4) 项 ->项目 (5) ..

发布时间：2021-12-22 08:27:27 data-structures linked-list language-agnostic binary-search-tree 其他开发

重新平衡任意 BST?

参考:我被问到这个问题@MS SDE 面试，第三轮.这不是家庭作业的问题.我也考虑了一下，并在下面提到了我的方法. 问题:修改 BST，使其尽可能平衡.不用说，你应该尽可能高效. 提示:面试官说这是一个合乎逻辑的问题，如果你换个思路你就会得到答案.不涉及困难的编码. --> 话虽如此，我不认为他希望我指向 AVL/RB 树. 我的解决方案:我建议，我会做树的中序遍历，将中间元素 ..

发布时间：2021-12-22 08:11:15 algorithm data-structures binary-search-tree 其他开发

如何有效地合并两个 BST?

如何合并两棵保持BST性质的二叉搜索树? 如果我们决定从树中取出每个元素并将其插入到另一个元素中，则该方法的复杂度将是 O(n1 * log(n2))，其中 n1 是我们分裂的树的节点数(比如 T1)，n2 是另一棵树的节点数(比如 T1>T2).此操作后，只有一个 BST 有 n1 + n2 个节点. 我的问题是:我们能做得比 O(n1 * log(n2)) 更好吗? 解决方案 ..

发布时间：2021-12-22 08:02:59 c++ algorithm data-structures merge binary-search-tree C/C++开发

二叉树和二叉搜索树的区别

谁能用一个例子解释二叉树和二叉搜索树的区别? 解决方案 二叉树:每个节点最多有两片叶子的树 1/\2 3 二叉搜索树:用于搜索.一棵二叉树，其中左孩子仅包含值小于父节点的节点，而右孩子仅包含值大于或等于父节点的节点. 2/\1 3 ..

发布时间：2021-12-22 00:04:38 data-structures tree binary-tree binary-search-tree 其他开发

二叉搜索树相对于哈希表的优势

二叉搜索树相对于哈希表的优势是什么? 哈希表可以在 Theta(1) 时间内查找任何元素，并且添加元素同样容易......但我不确定相反的优势. 解决方案 请记住二叉搜索树(基于引用)是内存高效的.他们不会保留比他们需要的更多的内存. 例如，如果一个散列函数的范围是 R(h) = 0...100，那么你需要分配一个包含 100 个(指向)元素的数组，即使你只是散列 20 个元素 ..

发布时间：2021-12-22 00:03:35 data-structures hashtable binary-search-tree 其他开发

给定后序遍历如何构造BST

我知道有一些方法可以从前序遍历(作为数组)构造一棵树.考虑到中序和前序遍历，更常见的问题是构造它.在这种情况下，虽然中序遍历是多余的，但它确实让事情变得更容易.任何人都可以给我一个想法如何为后序遍历做到这一点?需要迭代和递归解决方案. 我尝试使用堆栈迭代地执行此操作，但根本无法获得正确的逻辑，因此得到了一个可怕的凌乱树.递归也是一样. 解决方案 如果你有一个来自 BST 的后序遍历的 ..

发布时间：2021-12-16 08:51:04 algorithm recursion binary-tree binary-search-tree 其他开发

在二叉搜索树中查找高度

我想知道是否有人可以帮助我重新设计这个方法来找到二叉搜索树的高度.到目前为止，我的代码看起来像这样.但是，我得到的答案比实际高度大 1.但是当我从返回语句中删除 +1 时，它比实际高度小 1.我仍然试图用这些 BST.任何帮助将不胜感激. public int findHeight(){if(this.isEmpty()){返回0；}别的{树节点节点 = 根；返回 findHeight(节点)； ..

发布时间：2021-12-16 08:48:53 algorithm recursion binary-search-tree 其他开发

在 BST Python 中删除节点

这是一种在 Python 中为 BST 实现添加和删除功能的可能方法.它有点类似于我在 C++ 中对 BST 的想法.从删除代码中可以明显看出，我想删除一个节点，但由于 C++ 中存在 Python 中缺少按引用传递而无法执行此操作.除了 del currNode 之外，有什么好的替代方法可以删除节点(这不起作用).我还有一个问题要澄清我关于 Python 中按引用传递的想法，当使用 add 函数 ..

发布时间：2021-12-16 08:38:19 python recursion binary-search-tree pass-by-reference Python

Java 泛型问题:类“不在类型变量的范围内"错误.

我正在做一个涉及泛型的类项目. public interface Keyable {公共字符串getKey();}公共接口 DataElement extends Comparable>, Keyable, Serializable {...}公共课程课程实现 DataElement {...}公共接口 SearchTree>&可键控> ..

发布时间：2021-12-15 10:07:08 java generics binary-tree binary-search-tree Java开发

为什么 std::map 实现为红黑树?

为什么 std::map 实现为 红黑树? 有几种平衡的二元搜索树 (BST).选择红黑树的设计权衡是什么? 解决方案 可能两种最常见的自平衡树算法是 红黑树 和AVL 树.为了在插入/更新后平衡树，两种算法都使用旋转的概念，其中树的节点被旋转以执行重新平衡. 虽然在两种算法中插入/删除操作都是 O(log n)，但在红黑树重新平衡旋转的情况下是一个 O(1) 操作，而使用 A ..

发布时间：2021-12-10 15:52:15 c++ dictionary data-structures stl binary-search-tree C/C++开发