[자료구조] 13강 - 멀티웨이 탐색 트리(2)

✅ 1. 2-3 트리

[ 트리 분류 ]

• B트리: 멀티웨이 탐색트리로 이진 탐색 트리와 규칙을 동일하지만, 다른점은 2개의 노드 제한이 아닌 여러 노드를 가질 수 있으며, 해당 m원 멀티웨이 트리로부터 균형을 더한 트리임. 이진 탐색 트리의 AVL, BB, Splay 균형 트리와 비슷함.

(1) 2-3 트리(2-3 tree)

• 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리를 의미한다.
• 쉽게말해, 모든 노드가 2노드 또는 3노드로만 이루어진 균형 탐색 트리이며, 해당 구조는 모든 노드가 2개 또는 3개의 자식 노드를 가지는 트리임.
• 2-노드 혹은 3-노드라는 제약이 내부 노드에만 해당함. 즉, 잎 노드의 경우 자식 노드가 없으므로 어차피 해당이 안됨.
• 모든 잎 노드는 같은 레벨에 있어야 한다는 제약만 존재함.
• ** 핵심은 2-3 트리는 차수 3 B-트리와 완전히 동일한 개념이며, 노드가 가질 수 있는 키 개수를 1~2개(즉 2-노드/3-노드)로 제한해둔 형태임. **

(2) 2-3 트리 - 조건

• 결국 B트리의 규칙을 모두 따르면서 B트리는 노드의 제한을 두지 않는 반면 2-3 트리는 노드의 개수를 2개 또는 3개로 제한을 둔 트리로 보면 됨.

(3) 2-3 트리 - 탐색

[ 노드 구조 ]

• 2개의 key 와 3개의 point 로 이루어진 노드임. ( 노드의 구조는 3차 B tree 로 볼 수 있음. )

[ 탐색 로직 ]

• 찾고자 하는 데이터를 함수 입력 데이터로 전달 후 switch 문의 조건에는 compare(x, t) 를 진행함.
• 해당 compare(x, t) 함수는 찾고자하는 데이터와 해당 포인터의 lkey 와 rkey 를 비교한 뒤 어떤 포인터로 갈지 1~4 정수 리턴.
• 이후, 1~4 중 하나가 리턴이 되면 해당 case 를 수행하게 됨.
• case 는 t 에 현재 자식 노드 중 어떤 포인터로 갈지 정해서 리턴을 해줌. 재귀적 호출 방식으로 찿아가는 원리임.
• 위와 같은 로직을 통해 원하는 데이터를 2-3 트리에서 찾을 수 있음.

(4) 2-3 트리 - 삽입

• 트리 구조에선 삽입과 삭제 연산에 대해서 오버헤드가 클 수 밖에 없음.
• 즉, 트리의 형태를 온전히 유지를 시켜줘야 하는 논리적 제약 조건을 가지고 있는 경우가 대부분임.
• 삽입과 삭제가 일어날 때 트리의 구조가 많이 바뀔 수 있는데, 최소한의 변경만으로 트리 구조가 유지되는 트리가 효율이 좋음.

[ 2-3 트리 - 삽입 알고리즘 ]

(5) 2-3 트리 - 삭제

• 2-3 트리의 삭제에서 잎 노드가 아닌 노드의 키를 삭제하면 그곳을 다른 키로 대체해야 함
• 일반적으로 삭제한 키의 왼쪽 서브트리에서 가장 큰 키 값이나 오른쪽 서브 트리에서 가장 작은 키 값을 선택하여 대체함.
• ** 핵심은 B tree 와 삭제 연산과 삽입 연산이 동일하다는 의미임. **

---

✅ 2. 2-3-4 트리

(1) 2-3-4 트리 - 정의

• 2-3 트리를 확장한 개념으로 단순히 4개의 자식을 가진 4-노드를 허용하는 탐색 트리임.

(2) 2-3-4 트리 - 조건

• 단순히 lkey 는 mkey 보다 작아야 한다. ( 이진 탐색 트리 규칙과 동일함 )
• 나머지 규칙도 마찬가지임.

---

✅ 3. 레드 블랙 트리

(1) Red-Black Tree - 정의

• Red-Black Tree 는 2-3-4 트리를 효율적인 기억 장소 사용을 위하여 이진화한 이진트리 형태이다.
• 이진 탐색 트리(BST)의 한종류이며, 스스로 균형(blancing) 잡는 트리이며, BST의 worst case의 단점을 개선한다.
• ** 쉽게말해, 2-3-4 트리의 균형 보장에 대한 장점과 이진 트리 구조의 2개의 자식 노드를 가지는 단순성 및 효율적인 메모리 관리 두 가지를 활용해서 만들어진 트리가 Red-Black Tree 이다. ( 이진 탐색 트리 편향 트리를 방지 할 수 있음. )**
• 즉, 2-3-4 멀티웨이 구조는 버리고 균형을 유지하는 논리적인 규칙만 가져와서 이를 이진 탐색 트리 구조에 적용한 것임.
• 2-3-4 트리의 노드의 빈 공간이 생기는데 이걸 이진 탐색 트리 구조로 변경함으로써 빈 공간이 없어지게 됨.
• ** Red-Black Tree 탐색 방법은 보통의 이진 탐색 트리의 탐색 알고리즘과 동일함. **

(2) Red-Black Tree - 속성

[ Red-Black Tree 속성 ] 1. 모든 노드는 red 혹은 black  2. 루트 노드는 항상 black 3. 모든 nil(leaf) 노드는 black 4. red의 자녀들은 모두 black ( 즉, red 가 연속적으로 존재할 수 없다는 의미임. ) [ nil 노드란? ] - 존재하지 않음을 의미하는 노드임 - 자녀가 없을 때 자녀를 nil 노드로 표기 - 값이 있는 노드와 동등하게 취급이 됨. - 즉, Red-Black Tree 에서 모든 leaf 노드는 nil 노드가 됨.