알고리즘) 2장

 

 

 

rb, 2-3-4 

그니깐 대충 같아질수도있고(모두 2노드이면) 

모두 4노드이면 높이 차이 2배 난다는건가 

 

 

 

Only 1 rotation per insertion!"

• **C=b(회전)**의 경우, 한 번 균형을 맞추면 트리의 전체적인 Black height가 유지되기 때문에 더 이상 위로 올라가며 수정할 필요가 없습니다. (딱 한 번의 회전으로 상황 종료)
• 반면 **C=r(색상 변경)**의 경우, 할아버지가 Red가 되면서 그 위쪽 부모와 또 Double Red가 생길 수 있어 루트까지 계속 확인해야 합니다.

 

 

 

과정중에 22삽입할때 15,13에서 더블레드인데

그러면 이것도 avl처럼 5,13,15 재구성인가,

13,15,20이 아니라