[자료구조] AVL Tree, 2-3 Tree

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

tree에 대한 Lemma

• 한 서브트리의 모든 값들은 전체를 sorting 해놓은 리스트에서 연속적이다.
• 수학적 귀납법으로 증명 가능
• Base : 루트에서는 무조건 성립한다.
• Step : 특정 노드 X에서 성립한다고 가정하면, 해당 서브트리인 L과 R은 각각 왼쪽과 오른쪽으로 갈린다. 따라서 무조건 성립하게 된다.

AVL Tree

• 균형잡힌 Tree라고 할 수 있다. 전체를 lotation 처리한 결과이다.
• 각 노드의 Lable에 L/R을 추가한다.
• L : Height of Left subtree / R : Height of Right subtree
• 조건 : L-R의 절댓값이 2 미만이어야 한다. 즉, L-R은 -1,0,1 중 하나이어야 한다.
• N개의 노드에 대해 AVL Tree는 O(logN)의 효율을 보인다. 가득 채우면서 내려가기 때문에 Height에 비해 노드 개수가 많다.
• 즉, 전체에서 가장 깊은 레벨의 leaf 노드에 대비해서, 나머지 leaf노드들도 그에 가까운 레벨을 가진다.

AVL Tree와 관련된 몇 가지 정의

• 이해를 용이하게 하기 위한 몇가지 정의
• Down Sequence : L, R로 이루어진 문자열. root부터 일정 위치까지 내려간 움직임의 흔적. (ex. LRLLR)
• Terminated Down Sequence : Down Sequence에서 더 이상 가지 못하는 위치를 빨간색으로 표시한 것. (ex. LRLLRL)
• 해당 Sequence들을 다 적어보면 가장 짧은 Down Sequence와 가장 긴 Down Sequence는 약 2배정도의 차이가 난다.
• root의 레이블 L/R 중에서 큰 것이 K라면, height는 K+1이다.
• 가장 짧은 Down Sequnce 위 레벨의 가지들은 노드로 가득 차있을 것이다. (해당 레벨 위까지의 노드 개수 2^(k/2)개)
• 가장 짧은 leaf 노드가 약 k/2라고 하면 노드 개수는 최소 2^(k/2)개, 최대 2^(k)개이다. (최대는 노드가 끝까지 모두 차있는 경우)
• 따라서 노드개수 N을 기반으로 방정식을 구해보면, 2^(k/2) <= N <= 2^(K). k/2 <= logN <= k 가 된다. 즉, k= O(logN)이다.
• 즉 height는 약 logN이 되고, 해당 tree에서의 search도 O(logN)이 된다.
• 다만 insert와 delete 사용시 AVL Tree는 label L/R에 대한 정의가 깨질 수 있다. 이를 잘 다루어주어야만 한다.

AVL Tree Insert

1. 일반적 insert를 수행한다. 특정 leaf에 해당 노드가 추가되었을 것이다.
2. tree를 거꾸로 올라가면서 label을 변경한다.
3. 조건이 불만족되면 rotation을 수행한다.
4. 조건이 모두 만족될 때까지 2~3의 과정을 반복한다.

• '조건 불만족'이란 L-R이 -1,0,1 이외의 값을 가지는 경우이다.
• 기존의 insert 코드에서 Rotation을 수행하는 코드가 추가적으로 필요할 것이다.
• del도 유사하게 작동한다.

AVL Tree Rotation

• Rotation은 새로운 노드가 추가된 위치에 따라 작동방식이 달라진다.
• 조건불만족(L-R이 2이상, -2이하가 되었다는 것)은 결국 새로운 노드가 추가된 subtree의 높이가 최소 2보다 크다는 것이므로, 새로운 노드가 추가된 위치에 대해 2개 이상의 Down Sequence를 정의할 수 있다.
• 조건 불만족이 발생한 노드 기준 새로운 노드가 추가된 위치가 LL(Left,Left)방향인지, LR(Left,Right)인지, RL(Right,Left)인지, RR(Right,Right)인지에 따라 Rotation 방식이 달라진다. (방향에 따라 2개까지의 Down Sequence만 분류한다.)
• 각 케이스에 따른 방법은 https://www.zerocho.com/category/Algorithm/post/583cacb648a7340018ac73f1 참조

2-3 Tree

• 각 노드당 1~2개의 key값을 가진다.
• 자식은 최대 3개까지 가질 수 있다.
• 1개의 자식은 허용하지 않는다.
• 모든 leaf가 같은 거리에 있다. (root ~ leaf 까지의 거리가 모두 같다.)
• emzei.tistory.com/132 참고

2-3 Tree의 Height

• 'N개의 key가 존재할 때 height가 O(logN)이다.'의 증명 -> Height를 고정값으로 두고 계산한다. 각 노드의 key, 자식개수의 값들이 모두 다를 수 있기 때문에 Height를 고정값으로 두어도 노드개수의 범위는 넓다.
• 높이를 h로 두면, 노드 개수 N = 2^h ~ 3^h 이다. 따라서 h는 대략 logN이라고 할 수 있다.

2-3 Tree의 Insert

1. Leaf까지 쭉 내려간다. (범위에 따라)
2. 해당 Leaf가 1개 혹은 2개의 key값을 가지는지 체크한다. 1개의 key값을 가지면 해당 leaf에 값을 추가한다. 2개의 key값을 가지면 기존에 존재하던 값 a,b와 새로 추가하려는 값 c 중 제일 작은 것과 제일 큰 것으로 새로운 노드를 만든다. 중간이 되는 값은 따로 저장하고, 세 포인터를 부모로 전달한다.
3. 2개의 key값을 가지는 경우는 계속 부모 노드의 상태를 체크하면서 작업을 반복한다. (key값이 1개 일경우 빈자리에 중간값 삽입, key값이 2개일 경우 또 새 노드 추가 및 분배 실행)
4. root까지 올라갔을 때 빈자리가 없으면 새로운 new root를 만들어 처리한다.

AVL vs 2-3

• AVL : 밸런스가 흐트러지면 성분 하나의 위치를 조정(Rotation)해서 밸런스를 맞춘다.
• 2-3 : 밸런스를 맞춰가면서 구성한다.