2
나는이 질문을 반복해서 반복하는 것에 대해 불평 할 것이라고 알고 있습니다. 죄송합니다,하지만 Google/Stackoverflow/포럼에서 내 대답을 찾지 못했습니다 ... 등배열 바이너리 트리에서 작업 삭제
나는 자바에서 배열 이진 트리 (검색되지 않습니다)를 만들고 있습니다.
1) 내 노드에는 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;
}
}
나는 1) 대답을 이해하지 못한다. 부모/자식/색인 값을 저장할 필요가 없다는 뜻입니까? – Alex
이것은 배열에 노드를 저장하는 방법에 따라 다릅니다. 귀하는이 정보를 공유하지 않았습니다. –
자, 내가 한 일은 배열의 각 요소가 BTPos 개체에 대한 포인터라는 것입니다. – Alex