알고리즘 2-3 Tree(2-3 트리)

소개글

알고리즘 2-3 Tree(2-3 트리)

목차

1. 2-3-Tree 란?
2. AVL-Tree와의 차이
3. 2-3-Tree의 형태
4. 2-3-Tree의 검색과 코드
5. 2-3-Tree의 삽입

본문내용

1. 2-3-Tree 란?
AVL-Tree와 마찬가지로 효율적인 검색을 위한 균형 트리의 구조를 지닌다. 이의 성립을 위해서는 세가지 조건을 만족하여야 한다.
(1) 모든 중간 노드들의 자식 수가 2또는 3이 되어야 한다. 자식이 둘이면 2-노드 그리고 자식이 3이면 3-노드라고 한다.
(2) 모든 단말노드가 같은 레벨에 있어야 한다.
(3) 자식 수가 둘이라면 노드에 있는 값은 왼쪽 부분트리에 있는 노드들의 값보다 크고, 중간 부분트리에 있는 노드들의 값보다는 작아야 한다. 자식 수가 셋인 경우에는 노드에 있는 작은 값은 왼쪽 부분트리에 있는 노드의 값보다는 크고, 중간 부분트리에 있는 노드들의 값보다는 작아야 한다. 또한 노드에 있는 큰 값은 중간 부분트리에 있는 노드들의 값보다는 크고, 오른쪽 부분트리에 있는 노드들의 값보다는 작아야 한다.

2. AVL-Tree와의 차이
AVL-Tree는 높이 부분에 있어서 거의 최소의 높이를 유지시켜 준다는 장점을 지니고 있지만 복잡도의 면에서 생각해 보면 삽입과 삭제는 어렵게 다가올 수도 있다. 이러한 AVL-Tree에 비해 2-3-Tree는 간단하게 이의 구현이 가능하다. 물론 각 연산의 시간 복잡도는 O(logn)을 유지한다.
AVL-Tree가 균형 트리(Balaced Tree)를 지향하였다면, 2-3-Tree는 완벽 균형 트리(Perfect Binary Tree)를 지향한다.

참고 자료

없음