AVL 트리
균형 이진 트리 중 하나로,
모든 internal 노드의 left height와 right height의 차이가 최대 1인 트리
밸런스 포스
트리의 균형이 얼마나 맞는 지에 대한 척도
Left Height - Right Height로 계산한다
AVL 트리에서 절대 값이 1인 경우 (-1 ~ 1인 경우) 밸런스가 맞춰진 것으로 본다.
밸런스가 맞춰지지 않으면 재정리가 일어난다
재정리
밸런스 포스가 깨지면 수행한다
싱글 로테이션
깨진 방향이 일괄적인 경우 사용한다
균형이 깨진 방향의 반대 방향으로 로테이션한다
더블 로테이션
깨진 방향이 일괄적이지 않은 경우 사용한다
균형이 깨진 방향의 반대 방향으로 로테이션한 뒤 한번 더 로테이션 한다
게임 개발자 지망생, 유니티 공부중!