알고리즘 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-2-Tree의 삽입

본문내용

0) return true;
else loc = loc.right;
}
}
return false;
}
5. 2-3-Tree의 삽입
2-3-Tree의 삽입은 이진 검색 트리와 마찬가지인 항상 단말 노드에서 이루어진다는 것을 염두하고 과정을 생각해 보자.
0. 먼저 키 값이 삽입 될 단말 노드를 찾는다.
① 이 노드가 2-노드이면 이 노드에 키 값을 적절하게 삽입함으로 삽입이 완료된다.
② 이 노드가 3-노드이면 이 노드에 삽입할 공간이 없으므로 이 노드의 분할 과정이 필요하다.
- 노드의 분할은 기존의 노드에 있던 두 개의 값과 새 값을 정렬하여 그 중에 중간 값을 부모노드로 올리고 나머지 두 개의 값은 기존 노드에 위치하게 된다. 중간 값을 부모노드로 삽입할 때 부모노드 역시 3-노드이면 이 노드 역시 분할되어야 한다. 이 과정을 반복하여 루트가 분할되면 트리의 높이가 하나 증가하게 된다.
항상 단말 노드로 삽입이 된다. 39를 삽입
해당 단말 노드가 2-노드라면 3-노드로 만듦
부모가 2-노드이므로 중간 값에 해당하는 39를 promote하면서 부모 노드를 3-노드로 변경
Promote Middle이 발생하여 그 중간 값이 있던 원 노드가 분리됨

키워드

알고리즘,   트리,   tree,   23,   2-3