标签: binary-tree

这类似于最近的一个问题.

我将维护已排序的值列表.我将在列表中插入任意值的项目.每次我插入一个值,我想确定它在列表中的顺序位置(是第1,第2,第1000).什么是最有效的数据结构和算法来实现这一目标？显然有很多算法可以让你这样做,但我没有看到任何方法可以使用简单的STL或QT模板功能轻松做到这一点.理想情况下,我想了解现有的开源C++库或可以执行此操作的示例代码.

我可以想象如何为此目的修改B树或类似的算法,但似乎应该有一个更简单的方法.

EDIT3:

Mike Seymour很好地证实,正如我在原帖中写的那样,使用简单的STL确实无法完成这项任务.所以我正在寻找一个好的btree,平衡树或类似的开源c ++模板,它可以在没有修改或尽可能少修改的情况下完成--Pavel Shved表明这是可能的,但我不想深入实现平衡树我.

(历史应该显示我使用make_heap将Mathieu的代码修改为O(log N)的不成功的努力)

编辑4:

我仍然给信贷帕维尔用于指出B树能够给一个解决方案,这一点,我不得不提,实现这种功能,但并不实现是最简单的方法定制 B-树的C++自己的模板是使用内存数据库.这将为您提供log n并且相当容易实现.

我已经看到这个数据结构谈了很多,但我不清楚什么样的问题需要这样的数据结构(通过替代表示).我从来不需要一个,但也许那是因为我不太喜欢它.你能开导我吗？

在Splay Trees Wikipedia页面上(据优势部分)说:

创建splay树的持久数据结构版本的可能性 - 允许在更新后访问先前版本和新版本.这在函数式编程中很有用,并且每次更新需要分摊O(log n)空间.

这是为什么？函数式编程如何特别利用持久性Splay树？

我有一个存储值的关系的数组,这使得几个树像:

所以,在这种情况下,我的数组将是(root,链接到)

(8,3)(8,10)(3,1)(3,6)(6,4)(6,7)(10,14)(14,13)

我想将数组中的所有根值设置为树中的主根(在所有树中):

(8,3)(8,1)(8,6)(8,4)(8,7)(8,10)(8,14)(8,13)

我应该调查什么算法？

让我们通过列表表示树.

如果叶子的数量是两个,A和B.那么只有一棵树(AB).

如果叶子的数量是三个,A,B和C.那么有两棵树((AB)C)和(A(BC)).

那么如果有N片叶子,那里有多少棵树？

我根据Alex Allain的例子找到了一个二叉树.在向其添加约5000-6000个元素后,它会引发堆栈溢出异常.知道如何防止堆栈溢出？原因是Insert()呼叫本身是递归的.

2013年3月6日更新

这是我如何重构代码以避免堆栈溢出:

void Insert(Key_T key, Value_T val, QuickMapNode<Key_T, Value_T> *leaf)
{
    while (true)
        if(key < leaf->key)
        {
            if(leaf->left) leaf = leaf->left;
            else
            {
                leaf->left = new QuickMapNode<Key_T, Value_T>;
                leaf->left->key = key;
                leaf->left->val = val;
                leaf->left->parent = leaf;
                leaf->left->left = NULL;    // Sets the left child of the child node to null
                leaf->left->right = NULL;   // Sets the right child of the child node to null
                break;
            }  
        }
        else if (key >= leaf->key)
        { …

我正在尝试编写一个函数来获取二叉树的高度.当我打印值maxi的值是我所期望的但是当函数返回值时,值总是为0.有人可以告诉我这里做错了什么吗？

int treeHeight(tree *p)
{
    static int maxi=0;
    static int i=0;
    if(p==NULL)
    {
        return maxi;
    }
    else
    {
        if(p->left!=NULL||p->right!=NULL)
        {
            i++;
        }
        else
        {
            i++;
            if(maxi<i)
            {
                maxi=i;
            }
        }
        treeHeight(p->left);
        treeHeight(p->right);
        i--;
    }
}

我有一个用 Java 编写的二叉树，效果很好。但是我想增强节点中的数据内容。目前，我可以在其上添加值，例如：

for( int i = 1; i <=10; i++ )
    t.insert( new Integer( i ) );

这将添加这样的项目：

public void insert( Comparable item ) {
    current = parent = grand = header;
    nullNode.element = item;
    ...
}

这是树的格式：

private static class RedBlackNode {
    // Constructors
    RedBlackNode( Comparable theElement ) {
        this( theElement, null, null );
    }

    RedBlackNode( Comparable theElement, RedBlackNode lt, RedBlackNode rt ) {
        element  = theElement;
        left     = lt;
        right    = rt;
        color    = RedBlackTree.BLACK;
    }

    Comparable …

我有以下代码来执行二进制树的顺序遍历:

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

inorder :: (a -> b -> b) -> b -> BinaryTree a -> b
inorder f acc tree = go tree acc
  where go Leaf z = z
        go (Node v l r) z = (go r . f v . go l) z

使用上面的inorder函数,我想得到第k个元素,而不必遍历整个列表.

遍历有点像折叠,因为你传递了一个函数和一个起始值.我想我可以通过传递k作为起始值来解决它,并且该函数将递减k直到它达到0并且在该点返回当前节点内的值.

我break遇到的问题是我不太确定如何通过inorder遍历的递归来修改整个函数,但是我觉得必须修改高阶函数会破坏使用更高阶函数的意义.第一名.

k迭代后有没有办法打破？

在Cracking the Coding Interview第6版中,有一个问题(4.4),你想要找出二叉树是否平衡,在这种情况下平衡意味着任何一方比另一方更深一个以上.

我像这样递归地解决了这个问题:

def isBalanced(root):
  return abs(getDepth(root.left) - getDepth(root.right)) > 1

def getDepth(node):
  if node is None:
    return 0
  return 1 + max([getDepth(node.left), getDepth(node.right)])

所以要走过它.它递归检查每个节点的每一侧并将其传递给根,如果根在左右子树之间的差异大于1,则返回False,否则返回True.

在本书的答案部分,作者写了关于这种解决方案的以下内容:

虽然这有效,但效率不高.在每个节点上,我们通过它的整个子树进行递归.这意味着在相同的节点上重复调用getHeight.该算法是O(N log N),因为每个节点在其上方的每个节点被"触摸"一次.

书籍解决方案如下:

int getHeight(TreeNode root) {
  if (root == null) return -1;
  return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

boolean isBalanced(TreeNode root) {
  if (root == null) return true;

  int heightDiff = getHeight(root.left) - getHeight(root.right);
  if (Math.abs(heightDiff) < 1) {
    return false;
  } else {
    return isBalanced(root.left) && isBalanced(root.right);
  }
} …