标签: binary-search-tree

我们总是看到(二元搜索)树上的操作具有O(logn)最差情况下的运行时间,因为树高是logn.我想知道我们是否被告知算法的运行时间是logn的函数,例如m + nlogn,我们可以得出结论它必须涉及(增强的)树吗？

编辑:感谢您的评论,我现在意识到分治和二叉树在视觉/概念上是如此相似.我从来没有在两者之间建立联系.但我想到一个案例,其中O(logn)不是一个分治算法,它涉及一棵没有BST/AVL /红黑树属性的树.

这是具有查找/联合操作的不相交的集合数据结构,其运行时间为O(N + MlogN),其中N是元素的数量,M是查找操作的数量.

如果我错过了,请告诉我,但我看不出分治在这里如何发挥作用.我只是在这个(不相交的集合)情况下看到它有一个没有BST属性的树,而运行时间是logN的函数.所以我的问题是为什么/为什么我不能从这个案例中进行推广.

我是一个Python人.学习C语言,我一直在尝试在C中实现二进制搜索树.我写下了代码,我已经尝试了几个小时但是,无法按预期获得输出.请帮忙!

请指正.

#include<stdlib.h>
#include<stdio.h>

typedef int ElementType;

typedef struct TreeNode {
  ElementType element;
  struct TreeNode *left, *right;
} TreeNode;

TreeNode *createTree(){
    //Create the root of tree
    TreeNode *tempNode;
    tempNode = malloc(sizeof(TreeNode));
    tempNode->element = 0;
    tempNode->left = NULL;
    tempNode->right = NULL;
    return tempNode;
}

TreeNode *createNode(ElementType X){
    //Create a new leaf node and return the pointer
    TreeNode *tempNode;
    tempNode = malloc(sizeof(TreeNode));
    tempNode->element = X;
    tempNode->left = NULL;
    tempNode->right = NULL;
    return tempNode;
}

TreeNode *insertElement(TreeNode *node, ElementType X){
    //insert element to …

我现在已经解决了这个问题一段时间,我无法理解逻辑.假设我有一个类似于以下内容的二叉树:

        8                    1 * 0 =  0
      /   \
     4    12                 2 * 1 =  2
    / \   / \
   2   6 10 14               4 * 2 =  8
                                    ----
                                     10

我想找到每个节点的深度,并将这些数字加在一起以获得总数.我现在得到的代码看起来像这样:

private int totalDepth(Node node, int depth) 
{
    if(node == null) 
    {
        return 0;
    }

    return totalDepth(node.left, depth + 1) + totalDepth(node.right, depth + 1);
}

我想这会在遍历右侧之前以递增的方式在树的左侧(8 - > 4 - > 2)向每个级别添加一个,但它不能正常工作.

我已经通过多种方式调整了这种方法,但似乎无法确定我所遗漏的内容.任何帮助将不胜感激.

是否有这样一个数字序列(1-7,所有使用的数字,每个只有一次),它们会形成相等的AVL和splay树？

据我所知,AVL树和二进制搜索树之间的时间复杂度在平均情况下是相同的,在最坏的情况下AVL击败BST.这给了我一个提示,即AVL总是优于BST以各种可能的方式与它们进行交互,在平衡实现方面可能会增加一些复杂性.

是否有任何理由首先应该使用BST而不是AVL？

从集合{1,2,3,4,5,6,7}中的每个密钥排列生成(通过连续插入节点)BST.有多少个排列决定了两个高度的树木？

很长一段时间以来,我一直坚持这个简单的问题.任何暗示任何人.

那么答案是80.

我在编写用于从树中删除节点的代码时遇到了问题.

给定BST和键值,找到树中的键并删除它.

所以这是我的想法,首先,如果BST为零则返回nil,如果BST只有一个节点根,则返回nil.

然后,如果BST中的密钥与给定密钥匹配,请检查该节点具有的叶数.如果节点根本没有子节点,则从第一个前任(根)重新创建一个bst到该节点的最后一个前导,并共享不是前一个节点的所有其余数据.

如果节点有一个子节点,则将其视为没有子节点的节点,但只需将子节点添加到最后一个节点.

因为节点有两个孩子,我必须找到一些没有任何子节点的节点来替换它们的位置.

在编写代码时出现了困难的部分,我现在不知道如何重新创建和共享树的数据.

有人可以提供一些提示或线索吗？

关于螺纹二进制搜索树的解释(如果你知道它们,请跳过它):

我们知道在具有n个节点的二叉搜索树中,有n + 1个左右指针包含null.为了使用包含null的内存,我们按如下方式更改二叉树 -

对于树中的每个节点z:

如果left [z] = NULL,我们在left [z]中输入tree-predecessor(z)的值(即指向包含前任键的节点的指针),

如果right [z] = NULL,我们在右[z]中输入tree-successor(z)的值(同样,这是指向包含后继键的节点的指针).

像这样的树称为线程二进制搜索树,新链接称为线程.

我的问题是: 螺纹二进制搜索树的主要优点是什么(与"常规"二叉搜索树相比).在网上快速搜索告诉我,迭代地实现有序遍历有助于,而不是递归地实现.

这是唯一的区别吗？还有其他方法可以使用线程吗？

这是如此有意义的优势吗？如果是这样,为什么？递归遍历也花费O(n)时间,所以..

非常感谢你.

我正在尝试编写一种从二进制搜索树中删除节点的方法.这是我删除节点的方法.

public void delete(int deletionNodeValue) {
    Node<Integer> nodeToBeDeleted = getNode(deletionNodeValue);
    if(nodeToBeDeleted == null) return; // No node with such value exists throw an error
    if(isLeafNode(nodeToBeDeleted)) {
        nodeToBeDeleted = null;
    } else if (nodeToBeDeleted.getNumChildren() == 1) {
        bypassNode(nodeToBeDeleted);
    }else {
        replace(nodeToBeDeleted, getSuccessor(nodeToBeDeleted.getValue()));
    }
}

我在叶子节点上检查了这个方法,但是在调试之后我发现执行的nodeToBeSelected=null发生,实际上没有删除节点.因为我仍然可以搜索已删除的值,程序仍然设法获取它.

tree.add(5);
tree.delete(5);
System.out.println(tree.getNode(5).getValue()); // Output : 5, should've been deleted

这是我的getNode()方法

public Node<Integer> getNode(int searchValue) {
    Node<Integer> currentNode = root;
    while(currentNode != null) {
        int currentNodeValue = currentNode.getValue();
        if(searchValue == currentNodeValue)
            return currentNode;
        else …

我正在尝试解决以下问题：

首先，我们有一个BST 与根0，没有别的。我们不加ň等给出的数字一个其中：

例如，我们不开始在树上添加n = 7个数字：
19 3 5 25 21 -4 2
在添加所有数字之后，目标是按照添加顺序找到每个节点的父级：
0 19 3 19 25 0 3

我的第一种方法是在添加节点的同时构建树并同时打印父节点：

    private static TreeNode treeInsert(TreeNode root, TreeNode newNode) {
    TreeNode y = null;
    TreeNode x = root;
    while (x != null) {
        y = x;
        if (newNode.key < x.key) x = x.left;
        else x = x.right;

    }
    newNode.parent = y;

    if (y == null) root = newNode;
    else if (newNode.key < y.key) …