개발자 노트

AVL Tree의 노드를 삭제한 이후에도 재배열 과정을 거쳐야 한다. 재배열 과정에서 지켜야할 규칙은 이전 블로그에서 기록한 내용과 동일하다. T1, T2, T3는 루트노드 y 또는 x의 자식트리이다. (y는 왼쪽, x는 오른쪽 트리) y x / \ Right Rotation / \ x T3 – – – – – – – > T1 y / \ < - - - - - - - / \ T1 T2 Left Rotation T2 T3 두 트리에서 지켜야 할 데이터 크기의 순서는 아래와 같다. keys(T1) < key(x) < keys(T2) < key(y) < keys(T3) 삭제의 순서 노드 w를 삭제한다고 할 때, 순서는 아래와 같다. BST의 삭제 방법과 동일하게 노드 w를 삭제한다. w 노드로부터 불균형한 첫번째..

AVL Tree는 스스로 균형을 맞추는 이진탐색트리(BST)이다. 여기서 균형을 맞춘다는 것은 왼쪽/ 오른쪽 자식트리의 깊이 차이가 1을 넘지 않는다는 의미이다. [그림1] AVL Tree [그림 2] AVL Tree가 아님 위 [그림1, 2]는 AVL Tree의 성립 조건을 비교하는 예시이다. [그림 1]의 경우는 모든 노드에서 자식노드들(왼쪽, 오른쪽)의 깊이 차이가 1을 넘지 않는다. 그런데 [그림 2]의 트리는 8과 18을 가진 노드에서 자식노드들의 깊이 차이가 1을 넘기 때문에 AVL Tree 조건을 성립하지 않는다. 왜 AVL Tree를 사용할까?이진탐색트리의 작업들(검색, 삽입, 삭제 등)을 수행할 때 O(logN)의 시간이 소요된다. 하지만 한쪽으로 노드들이 쏠린 트리의 경우 수행시간이 O..