AVL Tree Variation(2-3 Tree, 2-3-4 Tree, Red-Black Tree, skip list)

2-3 Tree

Definition

• Each Node has 2 or 3 Children, Not allowed to have a single child
  모든 노드는 2개 혹은 3개의 자식 노드를 가진다. 한개의 자식 노드를 허용하지 않음
• All leaves at the same level 
  모든 leaf는 같은 레벨을 가짐. 즉, 루트에서부터 leaf까지의 거리가 항상 같음
• N개의 key가 있다면, O(log N)이다 
  ex) 만약, 다 자식 노드가 2개씩 있다면, 높이가 3일때 \(2^3 -1\)개
        자식노드가 3개씩 있다면 최대 \(\frac{3^3-1}{3-1}\)

< 특징 >

2 트리일 때는 안됐던 (AVL) 모든 트리의 높이가 똑같이 유지할 수 있도록 할 수 있음

2 트리일 때는 1차이까지는 허용하여 주어야 하는 이유 -> 높이를 똑같이 유지할 방법이 없었음

Insert

x, z가 있는 상태에서 y가 insert된 경우

1. Go down the tree doing search until Leaf
2. See if Leaf has 1 or 2 Keys
   1. Key가 1개인 경우 : Just insert int the leaf
   2. Key가 2개인 경우 : 새로운 노드를 만들면, 리프의 높이가 달라지기 때문에 새로운 노드를 만드는 것은 불가능
      좌우로 노드 두개를 쪼갠 후, 중간 값을 parent로 올려보냄
3. 만약 key가 2개인 경우가 자식에서 발생했다면, 부모노드에 한개의 값이 insert되는 것과 마찬가지. 2의 경우 반복
4. 만약, root 노드까지 올라간다면, 루트를 새로 만듦

2-3-4 Tree

Definition

• Each Node has 1,2 or 3 keys
• each Node has 2,3, or 4 children
• Not allowed to have single child
• all leaves at the same level
• 2-3-4 tree has N keys -> the height is O(log N)

< 특징 >

search 하러 내려갈 때 split을 하면서 내려갈 수 있음 (2-3 tree에서는 불가능함)

즉, split이 2-3 tree처럼 계속 올라가지 않음

*2-3트리에서는 insert를 하면서 올리는 과정을 거침

왼쪽 -> 오른쪽으로 변경 가능

2-3 트리의 경우, 하나의 노드를 채우는 값 2개가 있더라도, 분리할 수 없음 3개가 필요함

 

Insert

1. Split 4 nodes when going down the tree -> reach leaf
2. if leaf is split -> parent can nver be split
3. 그 외에는 2-3 tree와 같음

AVL tree의 improvenment

• 상황에 따라 다양한 버전을 사용할 수 있음

[ 메모리 ] 상관 없음

[ 디스크 ] 하드 디스크에서 사용할 때 굉장히 느림 

 

노드가 커지면 커질 수록 배열처럼 행동함 

만약 링크하는 것이 비싸면 노드를 크게 만드는 경향이 있음

 

Red-Black Tree

2-3-4트리를 RedBlack트리로

A Different Representation of 2-3-4 tree

2-3-4 트리와 같은데, 노드를 하나만 넣을 수 있게 변경함. 

원래 없던 링크를 빨간색으로 표시함

 

• When you go down the tree until you cannot go futher, you see the same number of Black Links
  아래로 내려갈 수 있을 때까지 최대한 내려가면, 같은 수의 블랙 링크가 있다 (원래 있어야하는 링크의 개수, 2-3-4 트리는 리프까지의 거리가 같기 때문)
• Red는 연속으로 나올 수 없음 
• Black링크만 있는 것이 가장 짧고, Red 링크가 가장 많은것이 가장 길 것이다

* 만약 a,b가 한 노드에 있다면, a위에 b를 빨간 링크로 접어 올리면 red-black 트리가 됨

가운데에 있는 것을 부모노드로 하여 접어 올리는 과정 거치면 red-black 트리가 됨

LR Rotation

split을 하기 전과 한 후로 트리를 그릴 수 있는데, split을 하기 전, 후의 과정은 AVL트리의 LL, LR과 같은 로테이션으로 볼 수 있음

Red-Black Tree는 2-3-4 트리의 시뮬레이션

 

Operations on R-B Tree

Normal BST insert using Red Edge

red edge로 insert를 하는 BST 트리

만약, red edge가 연속되면 rotate함

rotation propagate upwards (insert하면서 위로 올라가면서 rotate)→ AVL트리와 2-3트리와 같아짐

ratation when searching down (search 하면서 아래로 내려가면서 rotate) → 2-3-4트리와 같아짐

 

Terminate Down Sequence

맨 끝까지 가는데에 필요한 black링크의 개수는 같다

shortest and longest about 2 times different

ex) black이 10개면 red는 최대 11개

가장 짧은 것은 black만 있는 것, 가장 긴것은 red가 제일 많은 것

height difference of left and right subtrees

최대 2배 다를 수 있음 

 

Skip List

binary skip list

올라갈수록 더 많이 건너는 skip list가 존재함

위에 skip list와 아래의 list 사이에 양방향 링크를 두어 위치를 찾을 수 있도록 한다

• 위에 있는 skip list는 사이에 한개 혹은 2개를 허용함 (2-3 트리와 동일함)

search

skip 리스트에서 찾은 후, 사이에 있는 값이라면 아래로 내려가서 그 사이에서 실제 값을 찾음

insert

skip 리스트에서 범위를 찾은 후, 아래로 내려가서 insert할 위치를 찾음

만약 insert한 후,

1. skip 리스트에서 표현되는 범위 내에 숫자가 1개에서 2개라면 skip 리스트를 그대로 유지
2. 2개 이상이라면, 중간 값을 skip리스트로 복사하여 올려줌

ex) 4와 6을 Insert한다면

4를 insert 했을 때 3과 7 사이에 4, 5 두개이므로 그대로 두면 됨

6을 insert하면 3과 7 사이에 4,5,6 세개가 생기므로 skip 리스트에 5를 추가함

또한, 위의 skip 리스트에  -와 + 사이에 3, 5, 7 세개의 숫자가 생기므로 위에 스킵 리스트를 하나 더 만들어, 5를 추가한다