AVL 트리에 추가하기

Question

AVL 트리에 값을 추가 할 때 어떻게 삽입해야하는지 어떻게 알 수 있습니까? 나는 코딩 측면에 대해 이야기하는 것이 아니라 그림 적 표현에 대해 이야기하고 있습니다. 삽입이 처음 사용 가능한 외부 노드에서 수행되었다고 가정하고 있지만, 임의의 외부 노드에 텍스트 파일을 삽입하는 예제와 같이 확신 할 수는 없습니다.

Answer 1

AVL 트리는 자체 균형 조정 이진 검색 트리이며 이진 검색 트리에는 다음과 같은 속성이 있습니다. 모든 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함되며 모든 노드의 오른쪽 하위 트리에는 키는 노드의 키인보다 큽니다. 따라서 삽입 된 속성이 남아있는 것과 같은 방식으로 새 노드를 삽입해야합니다. 루트 노드로 시작하여 새 노드 키와 현재 노드 키를 비교하여 리프쪽으로 작업합니다. 새 노드 키가 더 큰 경우 오른쪽 자식을 방문합니다. 그 다음에 자식 노드가있을 때 새로운 노드를 삽입합니다.