标签: binary-tree

鉴于此算法,我想知道是否存在迭代版本.另外,我想知道迭代版本是否更快.

这种伪蟒...

该算法返回对树的根的引用

make_tree(array a)
  if len(a) == 0
        return None;

  node = pick a random point from the array
  calculate distances of the point against the others
  calculate median of such distances
  node.left = make_tree(subset of the array, such that the distance of points is lower to the median of distances)
  node.right = make_tree(subset, such the distance is greater or equal to the median)
  return node

标题大多是不言自明的:链表比二叉树有什么优势？我能想到的唯一一个链表更有效的情况是迭代每个元素,在这种情况下,它仍然非常接近.看起来二进制树在访问数据和插入新元素方面都更快.那么为什么要使用链表呢？

像treap这样的随机二进制搜索树以高概率提供了良好的性能(按O(log n)的顺序),同时避免了像AVL,red-blackm,AA等确定性平衡树所需的复杂(和昂贵)重新平衡操作. .

我们知道,如果我们将随机密钥添加到简单的BST中,我们可以预期它是合理平衡的.一个简单的原因是n个节点的非均衡树的数量远远低于"几乎平衡的"树的数量,因此,插入密钥的随机顺序很可能以可接受的树结束.

在这种情况下,在"计算机程序设计的艺术"中,Knuth给出了一点点多于1.3*lg2(n)作为相当好的路径的平均长度.他还说,从随机树中删除一个随机密钥可以保持其随机性(因此它具有良好的平均平衡).

那么,似乎二进制搜索树以随机顺序插入和删除密钥,很可能为所有三个操作提供O(log n)顺序的性能:搜索,插入和删除.

也就是说,我想知道以下方法是否会提供相同的良好属性:

• 采用已知为"好"的散列函数h(x)(例如,它确保密钥的均匀扩展)
• 使用键上h(x)设置的顺序而不是k上的顺序.
• 如果发生碰撞,请按钥匙订购.如果散列键足够好并且散列函数的范围远大于键的集合,那么这应该是罕见的.

举例来说,按顺序插入的密钥{4,3,5,1,2}的BST将是:

                  4
                 / \
                3   5
               /\
              1  2

假设哈希函数将它们映射到(分别){221,142,12,380,18),我们就会得到.

                    221(4)
                   /   \
              142(3)  380(1)
             /    \
           12(5) 18(2)

关键点是"常规"BST可能会退化,因为键是按照用于将它们存储在树中的相同排序关系插入的(它们的"自然"排序,例如字符串的字母顺序)但是哈希函数在键上引入与"自然"完全无关的排序,因此,应该给出与按随机顺序插入键相同的结果.

一个强有力的假设是哈希函数是"好的",但我认为它不是一个不合理的.

我没有在文献中找到任何类似方法的参考,所以它可能是完全错误的,但我不明白为什么!

你觉得我的推理有什么缺点吗？有人已经尝试过吗？

我的C++程序创建了一个二叉搜索树.我知道如何在预订,后订单和有序中打印出值.

但是,我想做一些更困难的事情.如果有人在纸上画树,我想以他们看的方式打印出值.它的根部位于顶部的中心,它的左下方是儿童的左下方,而右下方是正确的儿童.其余的节点将相应地绘制.

我怎样才能做到这一点？

给定k个整数的整数数组,每个整数包含一个未知正数的元素(每个数组中元素数量不一定相同),其中所有k个数组中的元素总数为n,给出一个合并k个数组的算法单个排序数组,包含所有n个元素.该算法的最坏情况时间复杂度应为O(n∙log k).

我正在看我的书,但它没有解释.它告诉我什么是二叉搜索树,它决定使用字符串.

         Jared
        /     \
 Brittany      Megan
 /      \        /   \
Brett  Doug     Jim  Whitney

因此,据推测,节点大于其左子树,小于其右子树.贾里德怎么比布列塔尼更大？

通常我们需要算法中的树,然后我会得到一个有很多指针和递归的树.
有时我需要更高的速度,我将树放入2D数组,如下所示:

Example of a binary tree stored in an array
+-----------------+
|0eeeeeeeeeeeeeeee| //no pointers needed, parent/child, is y dimension,
|11       dddddddd| //sibbling is x dimension of the array.
|2222         cccc|  //The 123 tree is stored root up.
|33333333       bb|  //Notice how the abc-tree is stored upside down 
|4444444444444444a|  //The wasted space in the middle, is offset by the fact 
+-----------------+  //that you do not need up, down, and sibbling pointers.

我喜欢这个结构,因为它允许我加速使用指针和递归时我没有的选项.

但请注意中间浪费的空间....

如何摆脱/重用浪费的空间？

要求
我只使用这种结构,如果我需要最后一点速度,那么有大量翻译和地址计算的解决方案到达那个空间将没有用.

我想从我分配的二叉树中释放内存,这样做最好的遍历是什么？

typedef struct Node{
struct Node * right;
struct Node * left;
void * data;
}Node;


typedef int (*cmp) (void*,void *);


Node* init(void * element){
    Node * newNode=(Node*)malloc(sizeof(Node));
    newNode->data=element;
    newNode->left=NULL;
    newNode->right=NULL;
    return newNode; 
}

void  insert(void * element, Node** root,cmp compareTo){
    if(*root==NULL){
        *root=init(element);
        return;
    }
    if(compareTo(element,(*root)->data)==1)
        insert(element,&((*root)->left),compareTo);
    else
        insert(element,&((*root)->right),compareTo);
}

所以我有一个功课问题,我应该使用递归方法"找到以指定节点为根的子树中的最小元素"

然后我将此作为我的出发点:

   public TreeNode
{
    int data;
    TreeNode left;
    TreeNode right;
}

和

/**
Finds the minimum value for the subtree that is 
rooted at a given node
@param n The root of the subtree
@return The minimum value 
PRECONDITION: n is not null.
*/
int min(TreeNode n)
{
  // COMPLETE THE BODY OF THIS METHOD
}

现在,我已经编写了一个非常基本的驱动程序,用于将节点插入到树中,并且我已经编写了我的递归方法,但它似乎在计算而不是向下,这是我的方法:

int min(TreeNode n){      
if(n.left != null) {
  n = n.left;
  min(n);
  System.out.println("N is now " + n.value);
 }
    return n.value;
   }

输出我的代码: …

我要寻找一个在满二叉树一定的时间实现最低的共同祖先给出了两个节点(父X小于子2*x和2*X + 1).

我的问题是树中有大量节点和许多查询.是否有一个算法,它预处理,以便可以在恒定的时间内回答查询.

我使用RMQ查看了LCA,但我不能使用该技术,因为我不能在树中使用这个节点的数组.

有人可以给我快速回答许多查询的算法的有效实现,知道它是完整的二叉树,并且节点之间的关系如上所述.

我所做的是从两个给定节点开始,并连续找到它们的父节点(节点/ 2)保持被访问节点的哈希列表.当我们到达已经在哈希列表中的节点时,该节点将是最低的共同祖先.

但是当存在许多查询时,这种算法非常耗时,因为在最坏的情况下,我可能必须遍历高度30(树的最大高度)才能到达根(最坏的情况).