标签: binary-search-tree

给定一个带整数值的bst作为键如何在bst中找到最接近该键的节点？BST使用节点对象(Java)表示.最接近的是例如4,5,9,如果钥匙是6,它将返回5 ..

我正在尝试使用GraphViz绘制二叉树,但我有关于左孩子和右孩子的问题.有一种方法可以强迫节点成为正确的孩子吗？这是我的示例代码:

digraph G{
5 -> 3;
5 -> 8;
3 -> 1;
3 -> 4;
8 -> 6;
8 -> 12;
}

我正在努力解决何时使用二叉搜索树以及何时使用字典的概念.

在我的应用程序中,我做了一个小实验,使用了C5库TreeDictionary(我相信是一个红黑二叉搜索树)和C#字典.字典在添加/查找操作时总是更快,并且总是使用更少的内存空间.例如,在16809 <int, float>个条目中,字典使用342 KiB,而树使用723 KiB.

我认为BST应该是更高效的内存,但似乎树的一个节点需要比字典中的一个条目更多的字节.是什么赋予了？BST比词典更好吗？

另外,作为一个附带问题,是否有人知道是否存在更快+更高内存效率的数据结构,用于存储<int, float>字典类型访问对,而不是上述任何一种结构？

我想计算二进制搜索树的每个节点的深度的总和.

元素的各个深度尚未存储.

我正在阅读B树,看起来他们在O(lg n)时间内实现了动态集合操作.红黑树(Java中的TreeMap)也在渐近相同的时间范围内实现相同的操作.所以我想知道是什么让B树对数据库和文件系统更有用

可以从n个不同的元素构造多少个二叉搜索树？我们怎样才能找到一个经过数学验证的公式呢？

示例: 如果我们有3个不同的元素,比如说1,2,3,则有5个二叉搜索树.

我试图找出对熊猫数据框执行搜索和排序的最快方法。以下是我要完成的数据帧之前和之后的数据帧。

之前：

flightTo  flightFrom  toNum  fromNum  toCode  fromCode
   ABC       DEF       123     456     8000    8000
   DEF       XYZ       456     893     9999    9999
   AAA       BBB       473     917     5555    5555
   BBB       CCC       917     341     5555    5555

搜索/排序后：

flightTo  flightFrom  toNum  fromNum  toCode  fromCode
   ABC       XYZ       123     893     8000    9999
   AAA       CCC       473     341     5555    5555

在此示例中，我实质上是在尝试过滤掉最终目的地之间存在的“航班”。应该使用某种类型的dropplicate方法完成此操作，但让我感到困惑的是如何处理所有列。二进制搜索将是实现此目标的最佳方法吗？提示表示赞赏，并努力解决此问题。

可能的边缘情况：

如果数据被交换并且我们的终端连接在同一列怎么办？

flight1  flight2      1Num    2Num     1Code   2Code
   ABC       DEF       123     456     8000    8000
   XYZ       DEF       893     456     9999    9999

搜索/排序后：

flight1  flight2      1Num    2Num     1Code   2Code
   ABC …

我对不同网站上的一些文章非常困惑,这些文章是关于构建Binary Search Tree任何一个遍历(pre,post或in-order),或者它们中任意两个的组合.例如,在这个页面上,它表示给定pre,post或level顺序遍历,以及in-order遍历,可以构造BST.但是在这里和那里,他们向我们展示了BST从pre-order单独构建一个.此外,他们在这里向我们展示了如何构建BST来自给定pre和post-order遍历.在其他一些网站中,我找到了一个BST仅从post-order遍历构建一个解决方案的解决方案.

现在我知道,给定inorder和pre-order遍历,可以独特地形成一个BST.至于我提供的第一个链接,虽然他们说我们不能构造BSTfrom pre-order和post-order,我不能只是对post-order数组进行排序以获得它的inorder遍历,然后使用它和pre-order数组来形成BST？这与第4个链接中的解决方案相同,还是不同？pre-order只有给出,我可以排序,以获得in-order,然后使用它和pre-order得到BST.同样,这是否必须与链接2和3的解决方案不同？

具体来说,什么足以独特地产生BST？如果不需要in-order唯一性,那么我可以简单地对其进行排序以获得遍历,并以BST递归方式从其中构建N个可能的中的一个.

二进制搜索算法需要log(n)时间,因为树的高度(具有n个节点)将是log(n).

你会怎么证明这一点？

这是作业; 请不要只给我代码

我有两种方法:remove(T data)和removeRec(Node<T> node, T data).

在当前状态下,似乎我的代码只删除root了BST 的节点.

@Override
public T remove(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Data is null");
    }
    if (root == null) {
        throw new java.util.NoSuchElementException("BST is empty");
    } else {
        size--;
        BSTNode<T> dummy = new BSTNode<T>(null);
        return removeRec(root, data, dummy).getData(); //This is probably wrong too
    }
}

/**
 * Helper method to recursively search for, and remove the BSTNode with
 * the given data in …