WASD BLOG

(2,4) Tree 란? BST(Binary Search Tree)와 비슷하게 In-Order 의 순서로 값이 정렬되는데, 각 노드들의 Entry가 1개~3개인 Multi-Way Tree 의 한 종류이다. 각 Entry에 INF Entry를 더해 총 2개~4개가 되어 (2,4)라고 불린다. 각 Entry는 자식 노드를 하나 가지는데 자신의 값 이하의 노드와 연결된다. Insertion BST처럼 왼쪽, 오른쪽 값들을 비교해가면서 자기 값의 자리를 찾아간다. 찾은 자리에 공간이 남는다면 (Entry가 2개 이하라면) 그 자리에 들어가면 되지만 오버플로우가 발생할 수도 있다. 추가 후에 Entry가 4개가 되어 오버플로우가 발생하면, 왼쪽부터 두 개의 Entry, 오른쪽부터 한 개의 Entry로 쪼개고, 남는 중간 하나의 Entry는 부모 노드로 올려준다. 그 Entry의 왼쪽, 오른쪽이 먼저 쪼갠 두 개의 노드가 된다. 부모 노드로 Entry를 올려주게되면 부모 노드에서도 오버플로우가 발생할 수 있는데, 계속 전파하면된다. 만약 root 노드까지 오버플로우가 발생해 더 이상 올려줄 부모 노드가 없게 되면, 새로운 root노드를 만들어 올려준다. Deletion BST에서처럼 자식 노드가 없다면 그대로 삭제 자식 노드가 하나라면 자식 노드의 부모를 자신의 부모로 바꿔주고 삭제 자식 노드가 여러 개라면 In-Order 순서로 자신 다음 혹은 자신 바로 전 순서의 값과 바꾼 뒤 삭제 위 방식을 그대로 사용한다. 하지만 삭제 시에 노드의 Entry가 0개가 되는 언더플로우가 발생할 수 있다. 언더플로우 발생 시 1. 가까운 형제 노드(깊이가 같은 노드) 의 Entry가 2개 이상인 경우 (Entry를 줘도 언더플로우x)  - 형제 노드의 부모 Entry 값을 자신에게 가져오고, 형제 노드의 Entry는 부모 노드로 올린다. 2. 가까운 형제 노드(깊이가 같은 노드) 의 Entry가 1개인 경우(Entry를 주

AVL Tree의 Insertion, Remove 시 동작 Insertion - 기본적으로 BST의 Insertion 방식을 사용하고, 어떤 노드의 자식 노드들의 height 값의 차가 1보다 커지면 Trinode Restructuring 을 수행한다. 1. Insert된 노드부터 부모 노드를 찾아가면서 균형이 깨진 노드를 찾는다. 2. 찾으면, 현재 경로까지 노드 중 최근 3 가지 노드를 선택한다. ( 밑에서 부터 x, y, z 로 놓는다.) 3. Inorder 순서로 a, b, c 로 놓는다. 총 4가지 경우의 Rotation이 있다. 1) 왼쪽 Single Rotation 트리의 왼쪽에서 b = y -> 트리가 일렬로 있을 때 Y 노드를 잡고 올려주는 모습이다. 그림에는 나오지 않았지만 당연히 Z의 부모 노드는 Y의 부모 노드가 된다. 2) 왼쪽 Double Rotation 트리의 왼쪽에서 b = x -> 트리가 한 번 꺾일 때 X 노드를 잡고 Y 와 Z 사이로 올리는 모습이다. 마찬가지로 Z의 부모 노드가 X의 부모 노드가 된다. 3) 오른쪽 Single Rotation 트리의 오른쪽에서 b = y -> 트리가 일렬로 있을 때 왼쪽일 때에서 In-order의 순서만 바뀌고 거의 유사하다. 4) 오른쪽 Double Rotation 트리의 오른쪽에서 b = x -> 트리가 한 번 꺾일 때 왼쪽일 때에서 In-order의 순서만 바뀌고 거의 유사하다. De letion - Insertion과 마찬가지의 조건에서 Trinode Restructuring을 수행한다. 단, 한 번 수행해도 더 위의 노드가 균형이 깨질 수 있으므로 균형이 깨진 노드를 찾지 못 할 때까지 Restructuring을 수행해야 한다. 1. Delete된 노드부터 부모 노드를 찾아가면서 균형이 깨진 노드를 찾는다. 2. 찾으면, 올라온 반대 방향 으로 3칸 내려간다. ( 밑에서 부터