이진트리와 이진검색트리

지난 글 : [알고리즘/Do it 알고리즘] - 트리

 

이진트리란?

각 노드가 왼쪽 자식과 오른쪽 자식 둘을 갖는 트리를 이진트리(binary tree)라 한다. 이때 두 자식 가운데 한 쪽이 없거나 둘 다 없는 노드가 포함되어도 된다. 이진트리의 특징은 왼쪽 자식과 오른쪽 자식을 구분한다는 점이다.

 

완전이진트리란?

루트에서 아래쪽 레벨로 내려가는 노드가 빠짐없이 채워져 있고, 또 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 빠짐없이 채워져 있는 이진트리를 완전이진트리(complete binary tree)라 한다.

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

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

 

이진검색트리 살펴보기

이진검색트리(binary search tree)는 이진트리가 아래 조건을 만족하면 된다.

1. 어떤 노드 N을 기준으로 왼쪽 서브트리 노드의 모든 키값은 노드 N의 키값보다 작다.
2. 오른쪽 서브트리 노드의 키값은 노드 N의 키값보다 크다.

그러므로 같은 키값은 갖는 노드는 없다. 이진검색트리는 아래와 같은 특징 때문에 폭넓게 사용된다.

- 구조가 단순하다.
- 중위 순회를 하면 키값의 오름차순으로 노드를 얻을 수 있다.
- 이진 검색과 비슷한 방식으로 아주 빠르게 검색할 수 있다.
- 노드를 삽입하는 것이 쉽다.

이제 이진검색트리 프로그램을 작성하며 이와 같은 특징을 더 자세히 알아보자.

 

이진검색트리 만들기

노드 클래스 Node<K, V>

이진검색트리의 개별 노드를 나타내는 노드 클래스 Node<K, V>는 아래와 같이 4개의 필드로 구성된다.

- key : 키값(자료형 k는 임의의 자료형)
- data : 데이터(자료형 v는 임의의 자료형)
- left : 왼쪽 포인터(왼쪽 자식 노드를 가리킴, 형은 Node<K, V>)
- right : 오른쪽 포인터(오른쪽 자식 노드를 가리킴, 형은 Node<K, V>)

노드 클래스 Node<K, V>에는 1개의 생성자와 3개의 메서드가 있다.

- 생성자 : 각 필드에 넣어 둘 4개의 값을 전달받아 그대로 설정한다.
- getKey() : 키값 key를 그대로 반환하는 메서드다.
- getValue() : 데이터 data를 그대로 반환하는 메서드다.
- print() : 데이터를 출력하는 메서드다. 출력하는 것은 data, 즉 data에 대해 묵시적으로 toString 메서드를
            호출해 얻어지는 문자열이다.

 

이진검색트리 클래스 BinTree<K, V>

이진검색트리 클래스 BinTree<K, V>는 2개의 필드로 구성된다.

- root : 루트에 대한 참조를 넣어 두는 필드.
- comparator : 키값의 대소 관계를 판단하는 비교자. 이진검색트리를 생성하는 생성자에서 비교자를 명시적으로
               설정하지 않으면 자동으로 null이 되도록 초기자 null을 주어 선언한다.

 

생성자

클래스 BinTree<K, V>에는 2개의 생성자가 있다. 둘 다 비어 있는 이진 검색 트리를 생성한다.

BinTree()

루트에 대한 참조인 root를 null로 하여 노드가 하나도 없는(비어 있는) 이진검색트리를 생성하는 생성자다. 이 생성자로 생성한 이진검색트리에서는 노드 키값의 대소 관계를 판단할 때 자연 순서에 따라 수행한다. 따라서 키를 나타내는 K의 형(type)이 Comparable 인터페이스를 구현하고 있는 Integer 클래스나 String 클래스 등에 알맞다. 또 다른 생성자 BinTree(Comparator<? super K> c)와 달리 비교자를 따로 설정하지 않으므로 비교자용 필드 comparator의 값은 null이 된다.

 

BinTree(Comparator<? super K> c)

인수로 비교자를 전달받는 생성자다. 이 생성자로 생성한 이진검색트리에서는 키값의 대소 관계를 판단할 때 전달받은 비교자에 의해 아래와 같이 수행한다.

1. this()에 의해 인수를 전달받지 않는 생성자 BinTree()를 호출. root가 null인 이진검색트리를 생성.
2. 필드 comparator에 전달받은 c를 설정한다.

 

두 키값을 비교하는 메서드 comp

2개의 키값을 비교하는 메서드다. 검색 • 삽입 • 삭제의 각 메서드에서 호출하는 비공개 메서드(private method)다.

이 메서드는 두 키값 key1, key2를 비교해 아래 값을 반환한다.

- key1 > key2면 양수
- key1 < key2면 음수
- key1 == key2면 0

이진검색트리에 비교자 comparator가 설정되어 있는지 그렇지 않은지에 따라 2개의 키값을 비교하는 방법이 다르다.

 

1. 비교자 comparator가 null인 경우

생성자 BinTree()로 이진검색트리를 생성하면 필드 comparator값은 null이 되므로 비교자는 따로 설정되지 않는다. 자연 순서를 갖는 클래스는 Comparator<T> 인터페이스를 구현하며 동시에 compareTo 메서드를 구현한다.

((Comparable<K>)key1).compareTo(Key2)

key1을 Comparable<K> 인터페이스형으로 형 변환(cast)하고 compareTo 메서드를 호출해 Key2와 비교한다.

 

2. 비교자 comparator가 null이 아닌 경우

생성자 BinTree<Comparator<? super K> c)로 이진검색트리를 생성하면 필드 comparator에 비교자가 설정된다.

comparator.compare(Key1, Key2)

생성된 비교자 comparator의 compare 메서드를 호출해 두 키값 key1, key2의 대소 관계를 판단한다.

 

키값으로 검색하는 메서드 search

이진검색트리에서 원하는 값을 찾으려면 루트부터 시작해 현재 선택한 노드의 키값과 비교하며 왼쪽, 오른쪽을 검색하면 된다. 알고리즘은 아래와 같다.

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

search 메서드는 이 알고리즘을 바탕으로 이진검색트리에서 노드를 검색한다.

키값이 key인 노드를 검색해 성공하면 그 노드의 데이터에 대한 참조를 반환한다.

 

노드를 삽입하는 메서드 add

이진검색트리에 노드를 삽입하는 알고리즘을 생각해보자. 노드를 삽입할 때 주의할 점은 노드를 삽입한 후에도 트리가 이진검색트리의 조건을 유지해야 한다는 점이다. 따라서 노드를 삽입할 때는 가장 먼저 삽입할 알맞은 위치를 찾아야 한다. 그리고 삽입할 노드의 키와 값이 같은 노드가 이미 있을 경우 삽입할 수 없다.

 

node를 루트로 하는 서브트리에 대해 키값이 key인 데이터를 삽입하는 알고리즘은 아래와 같다(node가 null이 아닌 경우).

1. 서브트리의 루트를 선택한다. 여기서 선택 노드를 node로 한다.
2. 삽입할 키 key와 노드 node의 키값을 비교한다. 값이 같으면 삽입에 실패한다(종료).
   - key값이 삽입할 값보다 작으면
     왼쪽 자식 노드가 없으면 그곳에 노드를 삽입한다(종료).
     왼쪽 자식 노드가 있으면 선택 노드를 왼쪽 자식 노드로 나아간다.
   - key값이 삽입할 값보다 크면
     오른쪽 자식 노드가 없으면 그곳에 노드를 삽입한다(종료).
     오른쪽 자식 노드가 있으면 선택 노드를 오른쪽 자식 노드로 나아간다.
3. (2.)로 되돌아 간다.

add 메서드는 이 알고리즘을 바탕으로 노드를 삽입한다. 삽입하는 노드의 키값은 key이고 데이터는 data이다.

삽입은 root값에 따라 아래와 같이 수행한다.

 

root가 null인 경우

트리가 비어 있으므로 루트만으로 구성된 트리를 만들어야 한다. new Node<K, V> (key, data, null, null)에 의해 키값이 key, 데이터가 data, 왼쪽 포인터와 오른쪽 포인터가 null인 노드를 생성하고, root가 그것을 참조하도록 한다.

 

root가 null이 아닌 경우

트리가 비어 있지 않으므로 addNode 메서드를 호출해 노드를 삽입한다. addNode 메서드는 node를 루트로 하는 서브트리에 키값이 key이고 데이터가 data인 노드를 삽입한다.

 

노드를 삭제하는 메서드 remove

이진검색트리에서 노드를 삭제하는 알고리즘을 살펴보자. 삭제하는 절차가 복잡하므로 아래와 같이 세 경우로 나눠 학습한다.

1. 자식 노드가 없는 노드를 삭제하는 경우
2. 자식 노드가 하나인 노드를 삭제하는 경우
3. 자식 노드가 둘인 노드를 삭제하는 경우

 

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

이런 경우 삭제하는 노드(A)를 가리키는 부모 노드의 왼쪽 포인터를 null로 업데이트하면 된다. 이렇게 하면 노드 A는 어디에서도 가리키지 않기에 이진검색트리에서 삭제된다. 이 과정을 간단히 정리하면 아래와 같다.

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

 

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

오른쪽 자식 노드(B) 1개만 갖는 root의 오른쪽 노드인 A를 삭제하는 경우다. 이런 경우 노드 A의 위치로 오른쪽 자식 노드 B를 가져와 삭제를 수행한다. 이것이 가능한 이유는 '자식 노드(B)(A의 오른쪽 자식)를 루트로 하는 서브트리의 모든 키값은 부모 노드인 root보다 크다'라는 조건을 만족하기 때문이다. 구체적으로 삭제 노드의 부모 노드인 root의 오른쪽 포인터가 삭제 대상 노드인 A의 자식 노드 B를 가리키도록 업데이트하면 된다. 그럼 A는 어디에서도 가리키는 않기에 이진검색트리에서 삭제된다.

 

왼쪽 자식 노드(B) 1개만 갖고 있는 경우도 마찬가지다. 삭제할 노드 A의 부모 노드인 root의 왼쪽 포인터가 삭제 대상 노드의 자식 노드인 B를 가리키도록 업데이트하면 삭제가 완료된다. 이 과정을 간단히 정리하면 아래와 같다.

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

 

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

이 경우는 위 두 과정보다 더 복잡하다. root의 왼쪽 자식 노드인 A를 삭제하는 경우이다. 노드 A의 왼쪽 서브트리에서 키값이 가장 큰 노드 B를 노드 A가 있는 곳으로 옮겨 삭제를 수행한다. 이 과정을 간단히 정리하면 아래와 같다.

1. 삭제할 노드의 왼쪽 서브트리에서 키값이 가장 큰 노드를 검색한다.
2. 검색한 노드의 데이터를 삭제 대상 노드로 복사한다.
3. 검색한 노드를 삭제한다.
  - 노드에 자식이 없으면
    '자식 노드가 없는 노드의 삭제 순서'에 따라 노드를 삭제한다.
  - 노드에 자식이 1개만 있으면
    '자식 노드가 1개 있는 노드의 삭제 순서'에 따라 노드를 삭제한다.

 

삭제 알고리즘을 3가지 경우로 구분해 학습했다. remove 메서드도 이 3가지 경우를 묶어 구현했다.

remove 메서드는 키값이 key인 노드를 삭제한다.

 

1. 삭제할 키를 검색한다. 검색에 성공하면 p는 찾은 노드를 가리키고, parent는 찾은 노드의 부모 노드를 가리킨다.

 

2. 자식이 없는 노드를 삭제하는 과정과 자식이 1개만 있는 노드를 삭제하는 과정을 수행하는 부분이다. 삭제할 노드에 왼쪽 자식이 없으면 왼쪽 포인터가 null, 오른쪽 자식이 없으면 오른쪽 포인터가 null인 것을 이용해 두 가지 과정을 같은 절차로 수행한다.

 

3. 자식이 2개 있는 노드를 삭제하는 과정을 수행하는 부분이다.

 

모든 노드를 출력하는 메서드 print

모든 노드의 키값을 오름차순으로 출력하는 메서드다. 오름차순으로 출력하기 위해 중위 순회 방법으로 트리를 검색한다.

print 메서드는 root를 매개변수로 printSubTree 메서드를 호출한다. printSubTree 메서드는 node를 루트로 하는 서브트리의 모든 노드를 키값의 오름차순으로 출력하기 위한 재귀 메서드다. 출력하는 내용은 노드의 데이터다. 전달받은 node가 null참조인지 아닌지를 확인하고 만약 null 참조라면 아무것도 하지 않고 원래 호출한 곳으로 되돌아간다. printSubTree 메서드가 루트인 노드 A에 대한 참조를 매개변수 node로 전달 받는다. node가 null 참조가 아니면 printSubTree 메서드의 동작은 아래와 같다.

1. 노드 B를 가리키는 왼쪽 포인터를 매개변수로 해 printSubTree 메서드를 재귀적으로 호출(재귀).
2. 자기 자신인 노드 A의 데이터를 출력
3. 노드 C를 가리키는 오른쪽 포인터를 매개변수로 해 printSubTree 메서드를 재귀적으로 호출(재귀).

이때 1, 3은 재귀 호출이므로 그 동작을 한마디로 설명할 수 없다.

 

이진검색트리를 사용하는 프로그램 만들기

아래는 이진검색트리 클래스 BinTree<K, V>를 사용하는 프로그램이다.

출력 결과

 

참고 서적 :