问维护二叉树中的列表顺序
EN

Stack Overflow用户

提问于 2011-02-16 23:17:00

回答 3查看 894关注 0票数 3

给定一个数字序列，我希望将这些数字插入到平衡二叉树中，这样当我在树上执行顺序遍历时，它会返回该序列。

如何构造与此需求相对应的插入方法？

请记住，树必须是平衡的，所以没有一个完全平凡的解决方案。我试着用AVL树的一个修改版本来做这件事，但我不确定这是否能成功。

我也希望能够实现一个删除操作。Delete应删除列表中第i个位置的项。

编辑:澄清：

我希望有: Insert(i，e)，它在序列中的第i个元素之前插入一个元素e。Delete(i)，它删除序列的第i个元素。

如果我插入(0，5)，插入(0，4)，插入(0，7)，那么我存储的序列现在是7，4，5，二叉树上的顺序遍历应该得到7，4，5。

如果我删除了(1)，那么在二叉树上的顺序遍历应该会得到7，5。如你所见，在这种情况下，删除了i=1的第i个序列元素后，序列顺序保持不变(因为我已经从0开始对我的序列进行了索引)。

algorithm

binary-tree

在线客服搭建方案

搭建集AI机器人、在线客服、智能外呼等多功能服务的客服系统，支持快速接入及自搭建客服系统，从而让顾客快速得到解答

回答 3

Stack Overflow用户

回答已采纳

发布于 2011-02-18 12:08:16

这可以使用AVL树来完成。

通过添加到树的最右侧节点，将项目添加到AVL树。

由于旋转的性质，AVL平衡不会影响顺序遍历属性。

在每个节点上存储树的大小，并在插入/删除/平衡期间为每个受影响的节点维护这些值，可以在O(log )时间内完成。在每个节点上存储树的大小允许在序列中按排名搜索项目，因为树中项目的排名是由节点的左子节点的大小+ 1知道的。

从AVL树中删除可以通过将删除的节点替换为该节点的右子树的最左边的节点来完成。

然后，插入和删除操作在O(log )时间内完成，因为树始终是平衡的，并且节点上的大小更新是沿着从插入/删除节点到根的路径进行的。

由于除了二叉树之外不存在后备数据结构，因此可以执行受益于树的其他操作，例如在O(log )时间内找到序列中m，n范围的元素的和。

票数 1

Stack Overflow用户

发布于 2011-02-16 23:22:03

在树中保留一个链表。多亏了树，你已经有了指向节点的指针/引用。当您插入到树中时，还要在链表的末尾插入。从树中删除时，请从链接列表中删除。因为您有引用，所以它们都是O(1)操作，如果您愿意，可以按插入顺序迭代。

编辑:为了澄清Bart的顾虑，这里有一个Java实现

class LinkedTreeNode<E> {
   E data;
   LinkedTreeNode<E> parent;
   LinkedTreeNode<E> left;
   LinkedTreeNode<E> right;
   LinkedTreeNode<E> insertNext;
   LinkedTreeNode<E> insertPrev;
}

class LinkedTree<E> {
    LinkedTreeNode<E> root;
    LinkedTreeNode<E> insertHead;
    LinkedTreeNode<E> insertTail;

    // skip some stuff
    void add(E e) {
        LinkedTreeNode<E> node = new LinkedTreeNode<E>(e);

        // perform the tree insert using whatever method you like

        // update the list
        node.insertNext = insertTail;
        node.insertPrev = insertTail.insertPrev.insertPrev;
        node.insertPrev.insertNext = node;
        insertTail.insertPrev = node;
    }

    E remove(E e) {
        LinkedTreeNode<E> rem = // whatever method to remove the node
        rem.insertNext.insertPrev = rem.insertPrev;
        rem.insertPrev.insertNext = rem.insertNext;
        return rem.data;
    }
}

票数 1

Stack Overflow用户

发布于 2011-02-17 01:10:35

如果你可以随机访问序列的内容(例如，你有一个数组)，那么你可以直接构建树，这样预排序遍历就可以提供你想要的序列。它实际上可以在没有随机访问的情况下完成，但效率较低，因为可能需要线性扫描来找到序列的中点。

这里的关键观察是，序列中的第一个值位于树的根中，然后序列的其余部分可以分为两部分。前半部分将进入以左子节点为根的子树，后半部分将进入以右子节点为根的子树。因为您在每个步骤中将剩余的列表一分为二，所以生成的树将具有log_2 n个级别，并且将是平衡的。

下面是一些C++代码。请注意，" end“指的是当前数组段末尾之后的元素的索引。

struct Node {
    Node(int v) : value(v), l(0), r(0) {}

    int value;
    Node* l;
    Node* r;
};

Node* vector_to_tree(int begin, int end, int array[]) {
    if (begin == end)
        return NULL;

    Node* root = new Node(array[begin++]);
    int mid = (begin + end) / 2;
    root->l = vector_to_tree(begin, mid, array);
    root->r = vector_to_tree(mid,   end, array);

    return root;
}

void preorder_traverse(Node* root) {
    if (!root)
        return;

    std::cout << root->value << std::endl;
    traverse(root->l);
    traverse(root->r);
}