我知道你们可能会抱怨这个问题反复被问到。抱歉，但是我在Google/Stackoverflow/Forums等等网站上没有找到答案。
我正在用Java创建一个数组二叉树（不是搜索二叉树）。
1) 我的节点具有属性：parent（父节点）、left（左子节点）和right（右子节点）的索引号码。我的教授告诉我要这么做，但我不知道为什么，因为你可以通过公式找到父节点和子节点的索引，我希望有人能告诉我如何通过添加parent/left/right的索引来提高操作的复杂度。
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;
}
}
2i + 1，2i + 2，(i - 1)/2？ - Alex