데이터 구조 과정에 AVL 트리를 작성해야하고 트리를 회전하는 위치와 방법을 알 수 있도록 하위 트리의 균형 요소를 계산해야합니다. .왼쪽 및 오른쪽 서브 브랜치 깊이를 계산하는 데 도움이 필요합니다.
감사합니다, 에릭
편집 : 나는 이진 트리에서 노드의 수를 계산하는 알고
.
private int countTotalNodes(AVLNode<T> start){
AVLNode<T> current = start;
if(current.getLeft() != null){
return countTotalNodes(current.getLeft());
}
if(current.getRight() != null){
return countTotalNodes(current.getRight());
}
return 1;
}
AVL 트리에 대한 일반적인 구현은 노드 자체의 노드 높이를 저장하고 삽입, 잘라 내기 및 링크 작업에서 업데이트되는 것으로 생각합니다.
/**
* Recursively updates heights starting with given node.
* If height of given node is already correct we know
* that we can stop.
*/
private void updateHeights(AvlNode<T> node){
if(node == null) return;
int heightLeft = node.left != null ? node.left.height : -1;
int heightRight = node.right != null ? node.right.height : -1;
int height = heightLeft > heightRight ? heightLeft + 1 : heightRight + 1;
if(node.height != height){
node.height = height;
updateHeights(node.parent);
}
}
항상 이야기하는 최고 변경된 노드의 부모에라고 : 위로 높은 노드의 높이가 여전히 이런 일에 올 경우 그 작업 후 우리는 다음 확인해야합니다. 아 좋은 옛날 - AVL 트리를 구현하는 것은 재미있는 작은 프로젝트입니다. 행운을 빌어 요.
트리의 깊이를 계산 한 다음 왼쪽 및 오른쪽 하위 트리에 적용하는 방법을 작성하십시오.
트리 데이터 구조의 장점은 자연스럽게 자기 유사하고 재귀 적입니다.
그 정도는 알지만 문제는 그 방법을 쓰고 있습니다 : D – erversteeg
일반적인 방법은 트리 노드의 데이터 구조에 균형 요소 필드를 추가하는 것입니다. 균형 요소에 대한 변경 사항은 삽입 및 삭제에서 발생하며 변경 사항은 균형을 유지하기 위해 회전이 진행됨에 따라 전파됩니다. 의사 코드 인 here과 함께 이것에 대한 좋은 설명이 있습니다.
균형을 각 노드에서 약간의 부기로 유지하는 대신 각 삽입 또는 삭제에서 균형을 계산하면 이러한 작업이 훨씬 더 비쌉니다.
노드 수를 계산할 때은 잘못되었습니다 (매우 퇴화 된 나무 제외). 왼쪽 또는 오른쪽 하위 트리 중 하나만 계산합니다.하지만 둘 다 결코 계산되지 않습니다. 먼저 수정하십시오.
그런 다음 유사한 알고리즘을 사용하여 깊이를 구성하는 방법에 대해 생각해보십시오.
그러나 다른 답변에서 말했듯이, 균형 잡힌 트리를 갖는 모든 혜택보다 더 많은 것 이것의 성능 저하로, 당신의 나무를 균형이를 사용하지 않는 . 대신 노드에 깊이를 저장하고 언제 적응해야하는지 생각하십시오.
나무를 탐색하는 방법을 알고 있습니까? 그것을위한 재귀 함수가 있습니까? 각 반복은 글로벌 '깊이'값에 대한 가시성을 갖고 있습니까? – Randy