[자료구조] 이진탐색트리(binary search tree) - 2-3 Tree

2-3Tree: 이진탐색트리의 한 종류 (perfectly balanced) 

                노드의 종류가 2 node와 3 node로 두 개 있다.

시간복잡도: 2 node -> O(log2n), 3 node -> O(log3n)

 

2-3 tree의 조건 1: -1 <= BF <= 1

BF: 왼쪽 subtree의 height(높이) - 오른쪽 subtree의 height

->왼쪽과 오른쪽 subtree의 균형을 맞추어 주기 위한 목적

->왼쪽과 오른쪽의 height의 차이 즉, BF의 절대값이 클수록 노드 탐색 시간이 길어지기 때문이다

 

2-3 tree의 조건2: 2-node는 1개의 key, 2개의 child를 가진다. 

                             3-node는 2개의 key, 3개의 child를 가진다.

 

 

struct node 
{
	int key1;
    int	key2; //2-node의 key2는 NULL 값을 갖는다. 
    struct node *left_child;
    struct node *middle_child; //2-node의 middle_child는 NULL 값을 갖는다. 
    struct node *right_child;
};