자료구조 - 이진트리와 이진검색트리

이진트리(binary tree)

노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리(binary tree)라고 한다. 이때 각 노드의 자식은 2명 이하만 유지해야 한다.

이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다. 

 

이진트리

 

완전이진트리(complete binary tree)

루트부터 노드가 채워져 있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리라고 한다.

 

1. 마지막 레벨을 제외한 레벨은 노드를 가득 채운다.
2. 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 채우되 반드시 끝까지 채울 필요는 없다.

 

높이가 k인 완전이진트리가 가질 수 있는 노드의 최댓값은 2^k+1 - 1개이다. 따라서 n개의 노드를 저장할 수 있는 완전이진트리의 높이는 log n이다.

완전 이진트리

 

이진 검색트리(binary search tree)

1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.
2. 오른쪽 서브트리 노드의 키 값은 노드 N의 키 값보다 커야한다.
3. 같은 키 값을 갖는 노드는 없다.

 

이진 검색트리는 중위 순회를 하면 키 값의 오름차순으로 노드를 얻을 수 있다는 점과 구조가 단순하다는점, 이진 검색과 비슷한 방식으로 검색이 가능하다는 점, 노드의 삽입이 쉽다는 점 등의 특징이 있어 폭넓게 사용된다.

 

이진 검색 트리

 

이진검색트리의 개별 노드는 다음과 같이 4개의 필드로 구성된다.

- key: 키 값
- data: 데이터
- left: 왼쪽 자식 노드에 대한 참조(왼쪽 포인터라고 부른다.)
- right: 오른쪽 자식 노드에 대한 참조(오른쪽 포인터라고 부른다.)

키값을 검색하는 과정

1. 루트부터 선택해서 검색을 진행한다. 여기서 선택하는 노드를 p라고 한다.
2. p가 널이면 검색에 실패한다.
3. 검색하는 값 key와 선택한 노드 p와의 키값을 비교하여
    - 값이 같으면 검색에 성공(검색종료)
    - key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입한다.(왼쪽으로 검색 진행)
    - key가 크면 선택한 노드에 오른쪽 자식 노드를 대입한다.(오른쪽으로 검색 진행)
4. 2번 과정으로 되돌아간다.

 

노드를 삽입하는 과정

노드를 삽입할 때 주의해야 할 점은 노드를 삽입한 다음에 트리의 형태가 이진 검색트리의 조건을 유지해야 한다. 따라서 노드를 삽입할 때는 알맞은 위치에 삽입해야 하며, 노드의 키와 값은 값을 가지는 노드가 이미 있다면 삽입해서는 안된다.

1. 루트를 선택한다. 여기서 선택하느 노드를 node로 한다.
2. 삽입할 키 key와 선택 노드 node의키 값을 비교한다. 값이 같다면 삽입에 실패한다.(종료)
    - 값이 같지 않은 경우 key값이 삽입할 값 보다 작으면
       왼쪽 자식 노드가 없는 경우에는 노드를 삽입한다.(종료)
       왼쪽 자식 노드가 있는 경우에는 선택한 노드를 왼쪽 자식 노드로 옮긴다.
    - key 값이 삽일한 값보다 크면
       오른쪽 자식 노드가 없는 경우에느 노드를 삽입한다.(종료)
       오른쪽 자식 노드가 있는 경우에는 선택한 노드를 오른쪽 자식 노드로 옮긴다.
3. 2로 되돌아간다.

 

노드를 삭제하는 과정

노드를 삭제하는 과정은 삽입하는 과정보다 복잡하다. 노드를 삭제할 때는 3가지 서로 다른 상황에 놓이기 때문이다. 따라서 각각의 상황에 알맞는 처리를 해야한다.

 

1. 자식 노드가 없는 노드를 삭제하는 경우

- 삭제할 노드가 부모 노드의 왼쪽 자식이면 부모 노드의 왼쪽 포인터를 null로 한다.
- 삭제할 노드가 부모 노드의 오른쪽 자식이면 부모 노드의 오른쪽 포인터를 null로 한다.

 

2. 자식 노드가 1개인 노드를 삭제하는 경우

- 삭제 대상 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다.
- 삭제 대상 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다.

 

3. 자식 노드가 2개인 노드를 삭제하는 경우

자식 노드가 2개인 노드를 삭제하는 과정은 앞의 두 과정보다 복잡하다.

1. 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색한다.
2. 검색한 노드를 삭제 위치로 옮긴다(검색한 노드의 데이터를 삭제 대상 노드 위치로 복사한다.).
3. 옮긴 노드를 삭제한다. 이때
    - 옮긴 노드에 자식이 없으면 자식 노드가 없는 노드의 삭제 순서(1 번 경우)에 따라 노드를 삭제한다.
    - 옮긴 노드에 자식이 1개만 있으면 자식 노드가 1개인 노드를 삭제하는 순서(2번 경우)에 따라 삭제한다.