2-3 트리

2-3 트리는 노드 하나에 2개의 값이 있을수 있으며 링크는 3개가 있을수 있다. 2-3 트리는 다음과 같은 특징을 가지고 있다. 각 노드는 2개 이하의 아이템과 3개 이하의 링크로 구성된다. 노드 안의항목은 Item1 < Item2 크기로 정렬된다. 각 링크는 SubTree1 < Item1 < SubTree2 < Item3 < SubTree3 와 같은 순서로 링크된다. AVL 트리가 총 6개의 노드를 나타낼때 높이는 2이지만 2-3트리를 이용하여 나타낼때는 높이가 1이 된다. 따라서 AVL트리와 2-3트리의 시간복잡도를 나타내자면 각각 O( log2(N) ), O( log3(N) )이 되어 2-3트리가 성능이 더 높음을 알수 있다. 하지만 2-3트리가 여러 가지 트리 중 성능이 최고라고 할수만은 없다...