数组二进制树中的删除操作

Question

我知道你们会抱怨这个问题被一遍又一遍地问。抱歉，我在Google/Stackoverflow/Forums中没有找到我的答案...等等

我正在用Java创建一个数组二叉树(不是搜索树)。

1） 我的节点具有以下属性：父节点、左节点和右节点。它们是父级、左子级和右子级的索引数。我的教授告诉我这样做，我不知道为什么，因为你可以用公式找到父母和孩子的索引，我希望有人告诉我，添加父母/左/右的索引如何帮助我降低操作的复杂性。

2）而且当您有指向数组中节点的指针时，我只是找不到删除操作的复杂性。我正在考虑在删除节点时将所有节点向左移动。我认为它是O（n），我不知道如何改进它。我读到有些人正在使用 O（log n） 实现此操作。但他们没有说如何。（我将不胜感激Java中的任何代码片段）。

*请记住，我使用的是Java的ArrayList。

一些代码:

public class ArrayBinaryTree<E> implements BinaryTree<E> {
    private class BTPos<T> implements Position<T> {
        private T element;
        private int parent;
        private int left;
        private int right;
        private int index;

        /** Main constructor */
        public BTPos(T element, int index, int parent, int left, int right) {
            setIndex(index);
            setElement(element);
            setParent(parent);
            setLeft(left);
            setRight(right);
        }

        /** Returns the index */
        public int getIndex() {
            return index;
        }

        /** Sets the index */
        public void setIndex(int i) {
            index = i;
        }

        /** Returns the element stored at this position */
        public T getElement() {
            return element;
        }

        /** Sets the element stored at this position */
        public void setElement(T o) {
            element = o;
        }

        /** Returns the parent */
        public int getParent() {
            return parent;
        }

        /** Sets the index */
        public void setParent(int i) {
            parent = i;
        }

        /** Returns the left */
        public int getLeft() {
            return left;
        }

        /** Sets the left */
        public void setLeft(int i) {
            left = i;
        }

        /** Returns the right */
        public int getRight() {
            return right;
        }

        /** Sets the right */
        public void setRight(int i) {
            right = i;
        }
    }
    private List<BTPos<E>> tree;
    private int size;
    private final int MAX_SIZE;

    /** Creates an empty binary tree. */
    public ArrayBinaryTree() {
        this.MAX_SIZE = 100;
        this.tree = new ArrayList<BTPos<E>>(this.MAX_SIZE);
        this.size = 0;
    }
}

Answer 1

1）将父/左/右索引存储在节点中只会浪费内存，因为无论如何都可以使用公式来实现它。

2）如果您已经有一个指向要删除的节点的指针，那么删除的复杂度将是O（1），您可以简单地用特殊符号标记该节点以表示已删除，而不是将所有节点向左移动。通过这种方式，您可以在插入时重用该节点（此外，您没有创建BST，那么可以在已删除的节点中进行任何插入）。

Answer 2

嗯，1)如果你有一个固定的布局，有一个索引的公式才起作用。然而，如果你没有一个平衡的树，这是对数组空间的浪费。On 2)解决O (log n)上的删除需要一个平衡树(如果不是BST——我不确定)。你可以使用谷歌找到如何轻松做到这一点的解释；).