회전 구현

불균형 트리는 적절한 회전 작업을 수행하여 균형을 이룹니다. 섹션, 재조정 트리에서는 노드에서 회전을 수행하는 방법을 보여줍니다. 아래 코드는 아래 그림과 같이 LL 회전에 대한 알고리즘을 제공합니다.

1잔액LL(TreeNode A, TreeNode parentOfA) {
2 B를 A의 왼쪽 자식으로 둡니다.
3
4 if (A가 루트)
5 B가 새로운 루트가 되도록 하세요
그 외 6개 {
7 if (A는 parentOfA의 왼쪽 자식입니다)
8 B를 parentOfA의 왼쪽 자식으로 둡니다.
그 외 9개
10 B가 parentOfA의 올바른 자녀가 되도록 하세요.
11 }
12
13 B.right를 A.left에 할당하여 T2를 A의 왼쪽 하위 트리로 만듭니다.
14 A를 B.right에 할당하여 A를 B의 올바른 자식으로 만듭니다.
15 노드 A와 노드 B의 높이를 업데이트합니다.
16 } // 메서드 끝

노드 A 및 B의 높이는 변경될 수 있지만 트리에 있는 다른 노드의 높이는 변경되지 않습니다. 비슷한 방식으로 RR, LR, RL 회전을 구현할 수 있습니다.

위 내용은 회전 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!