수동으로 BST 트리 균형 조정

Question

트리 요청을 수동으로 요청 (bst> avl)하고 정말 쉽다는 것을 궁금해합니다. 그래서 올바르게 수행했는지 확신 할 수 없습니다.

  a 
    /\ 
     b e3 
    /\ 
    e1 e2

초기 상태이다 'A' 'B'(좌측) 및 "E3"(우측)의 부모이고, B는 (좌측) "E1 '및'E2 '의 부모 (인 권리). 우회전을 적용

이

우리에게 제공합니다 오른쪽에 왼쪽과 'A'아동에 'A'아이 'E1'대신에

  b 
    /\ 
    e1 a 
     /\ 
     e2 e3

'B'를 'A'는 'E2'를 얻는다 왼쪽에 'b'가 있습니다.

그래서 질문 : E1 자체가 다른 요소, 난 아직도이 회전을 할 수가 포함 된 하위 트리 또는 노드

1. 경우?
2. 2. e2 및 e3이 없으면이 회전을 계속 수행 할 수 있습니까?

실시 예 11; 12 16

  16 
    /
    13 
/
10 

intial 상태 : (13) (왼쪽) (10) (16) (오른쪽)

의 부모이다 : (16) (13) 및 (13)의 부모 I 그것에서 할 수있는 제 의 부모이다

나는 그것이 단순하다는 것을 알고있다. 그러나 이론은 분명히 모든 사람들에게 잘 맞지 않는다는 가정하에 이러한 것들을 다루지는 않는다. 도움을 주셔서 감사합니다.

Answer 1

예, 모든 것이 있습니다. order 속성에 대해 생각해보십시오. 왼쪽 자손 < 노드와 오른쪽 자손 노드 <입니다. 회전이 이것을 어떻게 보존하는지 주목하십시오; 회전 전에 a와 b를 e1, e2 및 e3과 비교하고 회전 후에 순서와 자손 관계를 확인하십시오. 나는 그것을 버리기 전에 어떻게 숙고하도록 할 것입니다.