Tree Structure 노트7 - 2-3 Tree

높이균형트리 2-3 Tree

2-3 Tree는 내부노드의 차수가 2 또는 3인 균형 탐색트리이다. AVL 트리의 단점인 삽입과 삭제 시의 전체 트리를 재구성하는 부분을 최대한 줄이는 것이 핵심.

- 노드 하나에 항목이 2개의 값이 있으며 링크는 3개가 있을 수 있음.

- 노드 안에 항목의 수가 2개 있을 수 있고 각 항목은 크기대로 순서를 갖음.

- 해당 노드가 가리키는 3개의 링크는 왼쪽부터 순서대로 링크 되어 있음.

단점 : 하나의 노드 안에 2개의 데이터가 모두 존재할 때 해당 노드를 분할하는 작업이 만만치 않음.

특징 : 

- 각 노드는 2개 이하의 항목과 3개 이하의 링크를 가짐.

- 노드 안의 각 항목은 item1<item2 크기로 정렬되어 저장.

- 각 링크는 subtree1<item1<subtree2<item2<subtree3와 같은 순서로 링크됨.

- 중간값을 가짐.

분할(Split method) : 

- 하나의 노드 안에 이미 2개의 데이터가 차있을때 새로운 데이터를 추가하면 노드를 쪼개는 작업이 필요함. -> 무조건 분할 하는 것이 아닌 데이터의 크기에 따라서 나눔.

- 현재 노드인 왼쪽 자식 노드를 분할하기 전 상위인 부모노드를 먼저 검사. -> 부모노드가 다 차지 않았으면 자식 노드의 2개 데이터와 추가되는 데이터 중에 중간값인 데이터를 부모 노드로 보냄 -> 남은 2개의 데이터를 각각 노드로 만들어 저장.

 

2-3 Tree와 그 동작

2-3 Tree는 Multiway tree인 B-Tree의 일종으로 삽입의 원리는 단순함.

①어떤 원소가 입력됨. 그 원소가 들어갈 위치 찾음. ②규칙에 맞게 insert 되면 완료. ③들어갈 위치에 공간이 부족해서 더 이상 자리가 없으면 '만만한 노드'를 하나 골라서 parent node로 보냄. 되면 완료. 올라간 노드 위치에 자리가 없으면 다른 노드를 올림. ④최악의 경우 root에서까지 자리가 부족하면 root를 쪼개고 다시 새로운 root를 만듦. 이 경우는 높이 1증가.