insert 메서드 재정의

AVL 트리에 요소를 삽입하는 것은 트리 균형을 다시 조정해야 할 수 있다는 점을 제외하면 BST에 요소를 삽입하는 것과 동일합니다. 새 요소는 항상 리프 노드로 삽입됩니다. 새 노드를 추가하면 새 리프 노드의 조상 높이가 증가할 수 있습니다. 새 노드를 삽입한 후 새 리프 노드부터 루트까지의 경로를 따라 노드를 확인합니다. 불균형한 노드가 발견되면 아래 코드의 알고리즘을 사용하여 적절한 회전을 수행합니다.

1 BalancePath(E e) {
2 요소 e를 포함하는 노드에서 루트까지의 경로를 가져옵니다.
그림 26.9와 같이 3;
루트 {
로 이어지는 경로의 각 노드 A에 대해 4개 5 A의 높이를 업데이트하세요.
6 parentOfA가 A의 부모를 나타내도록 합니다.
7은 경로의 다음 노드이거나 A가 루트인 경우 null입니다.
8
9 스위치(balanceFactor(A)) {
10가지 경우 -2: BalanceFactor(A.left) == -1 또는 0인 경우
11 LL 회전을 수행합니다. // 그림 26.2 참조
그 외 12개
13 LR 회전을 수행합니다. // 그림 26.4 참조
14 휴식;
15가지 경우 +2: if BalanceFactor(A.right) == +1 또는 0
16 RR 회전을 수행합니다. // 그림 26.3 참조
그 외 17개
18 RL 회전을 수행합니다. // 그림 26.5 참조
19 } // 스위치 끝
20 } // for
끝 21 } // 메서드 끝

알고리즘은 새 리프 노드에서 루트까지의 경로에 있는 각 노드를 고려합니다. 경로의 노드 높이를 업데이트합니다. 노드가 균형을 이루고 있으면 조치가 필요하지 않습니다. 노드의 균형이 맞지 않으면 적절한 회전을 수행하십시오

위 내용은 insert 메서드 재정의의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!