2-3 트리

2-3 트리는 노드 하나에 2개의 값이 있을수 있으며 링크는 3개가 있을수 있다.

2-3 트리는 다음과 같은 특징을 가지고 있다.

1. 각 노드는 2개 이하의 아이템과 3개 이하의 링크로 구성된다.
2. 노드 안의항목은 Item1 < Item2 크기로 정렬된다.
3. 각 링크는 SubTree1 < Item1 < SubTree2 < Item3 < SubTree3 와 같은 순서로 링크된다.

AVL 트리가 총 6개의 노드를 나타낼때 높이는 2이지만 2-3트리를 이용하여 나타낼때는 높이가 1이 된다.
따라서 AVL트리와 2-3트리의 시간복잡도를 나타내자면 각각 O( log2(N) ), O( log3(N) )이 되어 2-3트리가 성능이 더 높음을 알수 있다.

하지만 2-3트리가 여러 가지 트리 중 성능이 최고라고 할수만은 없다.
왜냐면 AVL트리가 회전 작업으로 인해 불필요한 오버헤드가 발생했던것과 같이 2-3트리 역시 노드 안에 2개의 아이템이 존재한다면 해당 노드를 분할하는 작업이 더 큰 오버헤드를 발생시킬수도 있기 때문이다.

그로인해 분할 작업을 더 간단하게 만든 2-3-4트리를 사용하기도 한다.
2-3-4트리는 노드 안에 저장되는 아이템이 3개까지 허용되며 자식 노드에 연결되는 링크 역시 4개까지 허용된다.
2-3-4트리는 B트리 구조와 비슷하다.