Delete operation in Array Binary Tree

Question

I know you guys are going to complain about having this question being asked again and again. Sorry, but I have not found my answer in Google/Stackoverflow/Forums... etc

I am creating an Array Binary Tree (it's not a search one) in Java.

1) My node has the attributes: parent, left and right. Which are the number of the indexes of the parent, left child and right child. My professor told me to do it like this, I don't know why because you can find the indexes of the parent and children with a formula, and I would like someone to tell me how adding the indexes of parent/left/right whould help me in the complexity of the operations.

2) And I just can't find what should be the complexity of the delete operation when you have a pointer to the node in the array. I'm thinking in moving all the nodes to the left when deleting a node. I think it's O(n) and I don't know how to improve it. I've read that some people are implementing this operation with O(log n). But they don't say how. (I would appreciate any snippet code in Java).

*Keep in mind I am working with an ArrayList from Java.

Some Code:

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) Having parent/left/right indexes stored in a node would just waste memory as you can anyways achieve it using formula.

2)If you already have a pointer to node that you want to delete then the complexity would be O(1) for deletion and you can simply mark that node with special symbol for denoting it as deleted instead of shifting all the nodes to the left. In this way you can reuse the node while insertion (Also you are not creating a BST then any insertion can be done in the deleted node).

Answer 2

Well on 1) having a formula for the indexes only works if you have a fixed layout. However if you don't have a balanced tree this is wast of space in your array. On 2) solving the delete on O (log n) requires a balanced tree (If not a BST - I'm not sure). You can find an explanation how to do this easily using Google ;).