내 AVL 트리 구현의 경우, 왼쪽, 오른쪽 및 부모 포인터 및 균형 변수가있는 노드가 있습니다. 새 노드를 삽입하고 필요한 회전을 수행 할 때마다 왼쪽 하위 트리에서 오른쪽 하위 트리를 빼서 잔액을 업데이트합니다. 문제의이 메서드는 높이를 계산하기 위해 반복적으로 호출합니다. 문제AVL 트리의 로그 조건
방법 : AVL 트리 삽입 시간 복잡도가 나는이 방법이 시간 복잡도에 영향을 생각 O(log n) 때문에
private int getHeight(Node nd){
if (nd != null){
if (nd.getLeft() == null && nd.getRight() == null)
return 0;
else if (nd.getLeft() == null)
return getHeight(nd.getRight()) + 1;
else if (nd.getRight() == null)
return getHeight(nd.getLeft()) + 1;
else
return Math.max(getHeight(nd.getLeft()), getHeight(nd.getRight())) + 1;
}
else return -1;
}
내 질문이있다. 그것을 수정하기 위해 무엇을 할 수 있습니까?