标签: binary-search-tree

给定一个整数数组arr = [5, 6, 1].当我们以相同的顺序构造具有此输入的BST时,我们将以"5"作为根,"6"作为右子,"1"作为左子.

现在,如果我们的输入改为[5,1,6],我们的BST结构仍然是相同的.

因此,给定一个整数数组,如何找到输入数组的不同排列数,导致与原始数组顺序上形成的BST相同的BST？

我想知道在计算机科学背景下对"祖先"定义的共识是什么.

我只是问,因为在算法导论,第二版,p.259有一个Tree-Successor(x)看似奇怪的算法的描述.在寻找节点x的后继者时,

[...]如果节点的右子树X是空的,X有一个继任Ÿ,然后ÿ是最低的始祖X,其左子也是祖先X.

在具有关键根二叉搜索树2和孩子1和3,的继任者1是其母公司2.在这种情况下,x是x的后继者y的左子.根据这本书的定义,x必须是它自己的祖先,除非我遗漏了什么.

关于这一点,我没有在勘误表中找到任何内容.

我想知道什么是最好的:数组或二进制搜索树(插入,删除,查找最大和最小)以及如何改进它们？

给定两个大小为N的未排序数组,我们将确定从它们构造的二进制搜索树是否相等.

因此,数组的元素被选中并插入到基本(无平衡,无红黑,无任何)二叉搜索树中.直接给出两个数组,我们可以确定它们是否会产生相同的二进制搜索树.

有一个明显的O(N ²)最坏情况时间复杂度解决方案:构造两棵树,并比较它们的相等性.

是否有O(N)或O(N log N)解决方案？

我试图提取的问题的想法是:BST的构造取决于元素的相对位置.例如,如果在一个数组中有一个紧邻20的值为51的元素,则在另一个数组中必须没有20到51之间的元素才能使树相等(否则20的右子将是该数字,而不是51 ).

我尝试了几种方法:

1. 天真的方法:构建2棵树并进行比较.
2. 我使用了一个有趣的变体,我将数组分成2个(一个较小的子数组和一个比数组大的子数组),并递归地将左数组传递给左子,另一个传递给右.就地和厚脸皮,但仍然是O(N ²).
3. 一位朋友尝试将最长的子序列应用于它并找到它然后进行比较,但这是不正确的.
4. 我正在试图用LinkedHashMap解决它,但我很难证明它的正确性.

帮助,以及解决这个问题的任何提示将非常感激.

我买了一本关于计算几何的好书.在这里和那里阅读时,我经常偶然发现使用这种特殊的二叉搜索树.这些树是平衡的,应该只在叶节点中存储数据,而内部节点应该只存储值以引导搜索到叶子.

下图显示了此树的示例(其中叶子是矩形,内部节点是圆圈).

我有两个问题:

1. 不在内部节点中存储数据有什么好处？

2. 出于学习的目的,我想实现这样一棵树.因此,我认为使用AVL树作为基础可能是一个好主意,但这是一个好主意吗？

任何有用的资源都非常受欢迎.

我最近完成了为我正在开发的项目实现二进制搜索树.它进展顺利,我学到了很多东西.但是,现在我需要实现一个常规的二进制树...由于某种原因我难以理解.

我正在寻找一种方法来做我的InsertNode函数..

通常在BST中,您只需检查数据<root然后插入左侧,反之亦然.但是,在普通的二进制树中,它只是从左到右填充,一次一个级别.

任何人都可以帮我实现一个函数,只是从左到右添加一个新的节点没有特定的顺序？

这是我的BST插入:

void Insert(Node *& root, int data)
{
  if(root == nullptr)
  {
    Node * NN = new Node;
    root = NN;
  }
  else
  {
    if(data < root->data)
    { 
      Insert(root->left, data);
    }
    else
    {
      Insert(root->right, data);
    }
  }
}

给定BST,找到从root开始的所有节点序列,它们基本上会给出相同的二叉搜索树.

比如,给出一个bst

  3
 /  \
1    5

答案应该是3,1,5和3,5,1.

另一个例子

       5
     /   \
    4     7
   /     / \
  1     6   10

产出将是

5,4,1,7,6,10

5,4,7,6,10,1

5,7,6,10,4,1

等等

然而,这里的不变量是父母的索引必须始终小于其子项.我很难实现它.

什么是Scala 2.10.x中应该使用的标准平衡二叉搜索树实现？我环顾四周,它似乎已AVLTree被删除,并RedBlack已被弃用(Since version 2.10.0) use TreeMap or TreeSet instead.但是,TreeMap并TreeSet没有提供我需要的功能,因为我需要能够遍历树并基于此构建更复杂的数据结构.

是否有任何新类提供了不被弃用的普通平衡二叉树功能？

我不擅长以编程方式实现启发式搜索算法/提到的Dijkstra算法/ A*搜索算法.然而,在解决我的一篇文章中提到的问题(矩阵操作:逻辑没有获得更高阶NXN矩阵数据的正确答案)时,我发现了解决问题的方法中的一个缺陷.问题陈述如下.

问题陈述

有一个NxN矩阵,分为N*N个单元.每个单元格都有一个预定义值.这将作为输入.迭代必须发生K次,这也是在测试输入中给出的.我们必须确保在每次迭代时选择行/列的最佳/最小值.最终输出是每次迭代结束时保存的最佳值的累积和.

步骤1.总结单个行和列,找到行和列的最小总和(它可以是行或列,只需要最小行或列)

步骤2.分别存储上面找到的总和

第3步.增加min的元素.总和行或列.由1

从1到Kth值重复步骤1,2,3

在每次迭代时添加总和(在步骤2中指定)

输出是在第K次迭代上获得的总和.

样本数据

2, 4 //input data N,K
[1, 3] //matrix' first row
[2, 4] //matrix' second row

输出数据 22

我的守则

void matrixManipulation() throws IOException {
            int N = Reader.nextInt();
            int[][] matrix = new int[N][N];
            int K = Reader.nextInt();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    matrix[i][j] = Reader.nextInt();
                }
            }


            int[] row = new int[N];
            int[] …

  type BSTree a = BinaryTree a

  data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
                      deriving Show

  flattenTree :: BinaryTree a -> [a]
  flattenTree  tree = case tree of
      Null -> []
      Node left val right -> (flattenTree left) ++ [val] ++ (flattenTree right)

  isBSTree :: (Ord a) => BinaryTree a -> Bool
  isBSTree btree = case btree of
      Null -> False
      tree -> (flattenTree tree) == sort (flattenTree tree)

我想做的是编写一个函数来确定给定的树是否是二叉搜索树，我的方法是将所有值分组到一个列表中并导入Data.List，然后对列表进行排序以查找它们是否相等，但是有点复杂。我们可以不导入其他模块就能做到吗？