avl tree 정리

Binary Search Tree의 속성을 가짐 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 삽입, 삭제, 검색 시 시간복잡도는 O(logN), N은 노드의 개수 Node는 key, left node pointer, right node pointer, height 로 구성 Balance Factor 균형을 파악할 때 활용 BF(k) = k의 왼쪽 서브트리의 높이 - k의 오른쪽 서브트리의 높이 (-1, 0, 1 중 하나) Rotation RR, Right Rotation : 회전의 기준이 되는 노드가 오른쪽으로 감. LR, Left Rotation : 회전의 기준이 되는 노드가 왼쪽으로 감. Case LL(Left Left) Case : 중심 노드를 기준으로 왼쪽에 노드가 깊이 있는 경우 -> RR을..