标签: binary-search-tree

我已经创建了一个算法,其目的应该是,在BST中给定两个节点A和B,它通过简单地移动指针来切换两者中的角色(或树中的位置).在我对BST的表示中,我使用双链接连接(即A.parent == B和(B.left == A)或(B.right == A)).我不确定它是否完全正确.我在两种情况下划分了算法.

1. A和B直接连接(A是B的父级,B是B的父级)

2. 所有其他情况

对于以前的每个案例,我都创建了一个嵌套函数.我想首先考虑算法的正确性,如果我能以某种方式改进它.这是代码:

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 …

在相应的多集包含元素的类型对象上应用next()和prev()函数的时间复杂度是多少？multiset<int>::iteratorN

据我所知,在STL中,多集合被实现为一个平衡的二进制搜索树,因此我希望每次操作时的复杂度为O(log N)(在最坏的情况下),以防我们遍历树直到找到合适的价值,但我有预感,这应该是平均O(1).

但是,如果树实现如下 - 当x在平衡二叉搜索树中插入元素时,我们还可以检索树中小于x的最大数字,并且树中的最小数字大于xO(log N).因此在理论上,我们可以让树中的每个节点都保持指向它next和prev元素的指针next(),prev()然后在每个查询的恒定时间内运行.

什么人可以分享一些关于什么的光？

我刚刚完成了面试,我正在努力解决这个问题,这对我来说是一个非常难的问题.

问题是:编写一个函数,它给出一个整数流(无序),构建一个平衡的搜索树.现在,您不能等待输入结束(它是一个流),因此您需要动态平衡树.

我的第一个答案是使用红黑树,这当然可以完成这项工作,但我必须假设他们没想到我会在15分钟内实施一棵红黑树.

那么,对于这个我不知道的问题有什么简单的解决方案吗？

谢谢,

戴夫

我一直在谷歌上看这个并阅读SDK文档中的Collections条目,但没有透露任何信息.iOS SDK是否有开箱即用的BST(任何变体)实现？

一个主要的开发平台缺少一些基本的东西似乎很奇怪.他们的哈希实现是否那么神奇？或者开发人员假设没有人会对有订单的东西进行插入/删除？

我NSSet现在可以使用,因为我知道我们大多数人(包括我自己)并没有真正在iOS上编写任何需要保证访问时间的大量计算,但它仍然在啃着我.

鉴于以下问题:

"从数字流中存储最大的5000个数字"

我们想到的解决方案是二进制搜索树,它保持树中节点数量的计数,以及一旦计数达到5000就对最小节点的引用.当计数达到5000时,可以将每个要添加的新数字进行比较树中最小的项目.如果更大,则可以添加新数字,然后移除最小的数字并计算新的最小数量(这应该非常简单,已经具有前一个最小值).

我对这个解决方案的关注是二叉树自然会出现偏差(因为我只是在一边删除).

有没有办法解决这个问题,不会造成一个非常歪斜的树？

如果有人想要它,我已经为我的解决方案包括伪代码到目前为止:

process(number)
{
  if (count == 5000 && number > smallest.Value)
  {
    addNode( root, number)
    smallest = deleteNodeAndGetNewSmallest ( root, smallest)
  }
}

deleteNodeAndGetNewSmallest( lastSmallest)
{
  if ( lastSmallest has parent)
  {
    if ( lastSmallest has right child)
    {
      smallest = getMin(lastSmallest.right)
      lastSmallest.parent.right = lastSmallest.right
    }
    else
    {
      smallest = lastSmallest.parent
    }
  }
  else 
  {
    smallest = getMin(lastSmallest.right)
    root = lastSmallest.right
  }
  count--
  return smallest
}

getMin( node)
{
  if (node has left)
    return getMin(node.left) …

我正在学习算法和数据结构,并训练我正在尝试使用objective-c设计和实现二叉树.

到目前为止,我有以下类:

• main - 用于检测
• Node - 树的节点
• BinaryTree - 适用于与树相关的所有方法

BinaryTree我实施的第一类方法之一是insertNode:forRoot:.

- (void)insertNodeByRef:(Node **)node forRoot:(Node **)root{

    if (head == NULL) {
        head = *node;
    }
    // Case 2 root is null so can assign the value of the node to it
    if (root == NULL) {
        root = node;
    } else {
        if (node.data > root.data) { // to the right
            [self insertNode:node forRoot:root.right];
        } else if (node.data < root.data) { //or to the left
            [self …

维基百科关于AVL树的文章的第三段说:"由于AVL树更加严格平衡,因此对于查找密集型应用程序来说,它们比红黑树更快."

因此,不应该使用AVL树而不是红黑树来实现TreeMap(因为基于散列的数据结构会有更多的查找密集型应用程序)？

我在采访中被要求打印二叉树的边界.例如.

      1
   /    \
  2      3
 /  \   /  \
4    5 6    7
    /   \     \
   8     9     10

答案是:1,2,4,8,9,10,7,3

我给出了以下答案.

第一种方法:

我使用Bool变量来解决上述问题.

void printLeftEdges(BinaryTree *p, bool print) {
   if (!p) return;
   if (print || (!p->left && !p->right))
       cout << p->data << " ";
   printLeftEdges(p->left, print);
   printLeftEdges(p->right, false);
}

void printRightEdges(BinaryTree *p, bool print) {
   if (!p) return;
   printRightEdges(p->left, false);
   printRightEdges(p->right, print);
   if (print || (!p->left && !p->right))
   cout << p->data << " ";
}

void printOuterEdges(BinaryTree …

在给定一定数量的节点的情况下,是否有公式来计算AVL树的最大和最小高度？

例如:
教科书问题:
3个节点,5个节点和7个节点的AVL树的最大/最小高度是多少？
教科书答案:
3个节点的AVL树的最大/最小高度为2/2,5个节点的最大/最小高度为3/3,7个节点的最大/最小高度为4/3

我不知道他们是否通过一些神奇的公式计算出来,或者他们是否为每个给定的高度绘制了AVL树并确定了它.

我用c ++实现了二叉搜索树.而不是使用裸指针指向我使用的节点的孩子std::shared_ptr.树的节点如下实现

struct treeNode;
typedef std::shared_ptr<treeNode> pTreeNode;

struct treeNode {
    T key;
    pTreeNode left;
    pTreeNode right;
    treeNode(T key) : key(key), left(nullptr), right(nullptr) {}
};

从BST中删除节点时,其中一种情况是节点只有一个子节点.该子节点简单地替换该节点,如下所示:

             |        remove node                  
            node      --------->     |
               \                    right 
              right                

在类似的Java实现中,这可以编码为:

node = node.getRight();

在我的C++实现中,它是:

node = node->right;

其中node是type pTreeNode.

在pTreeNode(std::shared_ptr<TreeNode>)上调用=运算符时,node将调用析构函数.指向底层的共享指针的数量TreeNode是1,因此TreeNode被破坏释放其内存.当TreeNode(默认)调用析构函数,每个成员都毁灭了.这肯定会导致pTreeNode right成员被摧毁.问题node->right在于分配给的是什么node.在测试我的BST时,它似乎工作正常,没有错误/内存泄漏.

• 我在做什么不安全？
• 如果它不安全,我该怎么做才能解决这个问题？

我认为可能有用的"黑客"是制作另一个指针以增加其引用计数.这是一个适当的解决方案吗？

//increase reference to node->right by 1 so it doesn't get …