이진검색 트리 ( binary search tree )

트리 ( tree ) 는 부모와 자식간의 관계로 이뤄진 구조이다.

여기서 이진 트리 ( binary tree ) 는 이진 ( 2 ) 개의 자식으로 이뤄진 트리 구조이며, 왼쪽의 자식 ( child ) 는 왼쪽 부분 트리 ( left subtree ), 오른쪽 부분 트리 ( right subtree ) 로 부른다.

 

정의 ( definition ) 을 보면 아래와 같다.

순서가능집합 ( ordered set ) 에 속한 구성 ( item ) 으로 구성된 이진 트리이며 아래 조건을 만족해야 한다.

• 각 마디는 하나의 키만 가지고 있다
  • 여기서 키는 노드가 대표하는 값 ( id ) 이다
• 주어진 마디의 왼쪽 부분트리에 있는 키는 그 마디 ( 부모 ) 의 키보다 작거나 같다
• 주어진 마디의 오른쪽 부분트리에 있는 키는 그 마디의 키보다 크거나 같다

트리 구조에 대해 더 설명을 이어가면 트리는 마디의 계층 구조이므로 깊이 ( depth ) 또는 수준 ( level ) 이 존재한다. 그래서 모든 마디의 두 부분트리의 깊이가 1 이상 차이나지 않는 트리를 균형잡힌 트리 ( balanced tree ) 라고 부른다. 

 

트리를 구성하는 노드의 구성은 아래와 같다.

struct nodetype
{
	keytype key;
    nodetype* left;
    nodetype* right;
}

 

트리 구조 내에서 특정 "key" 값을 찾는 과정은 아래와 같다.

function search(tree, key)
{
	var found = false;
    
    var node = tree; // first node is root.
    
    while(!found) {
    	if(node.key == key) {
        	found = true;
        }
        else if(key < p.key) {
        	node = node.left; // move left.
        }
        else {
        	node = node.right; // move right.
        }
    }
    
    return found;
}

 

( next ) 최적 이진검색 트리에서 찾는 과정과 트리를 구성하는 방법을 알아본다.