# 이진탐색트리 (BinarySearchTree)
written by sohyeon, hyemin 💡
# 1. 이진탐색트리 (BinarySearchTree)
이진트리가 다음 조건을 만족할 때 이진탐색트리라고 한다.
- 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다.
- 오른쪽 서브 트리 노드의 키 값은 노드N의 키 값보다 커야 한다.
- 같은 키 값을 갖는 노드는 없다.
각 노드에 값이 존재할 때, 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져있다.
노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져있다.
좌우 하위트리는 각각이 다시 이진탐색트리이다.
# 이진탐색트리 예시
이진탐색트리를 중위 순회하면
1 -> 4 -> 5 -> 6 -> 7 -> 9 -> 11 -> 12 -> 13 -> 14 -> 15 -> 18
오름차순으로 노드를 얻을 수 있으며, 구조가 단순하다.
이진검색과 비슷한 방식으로 검색이 가능하며 노드의 삽입이 쉽다는 특징이 있다.
# 1-1. 최솟값과 최댓값
이진탐색트리의 특성에 의해
최솟값
왼쪽 자식 노드가 없을 때까지 왼쪽 자식노드를 탐색 했을 때 나오는 키 값이다.최댓값
오른쪽 자식 노드가 없을 때까지 오른쪽 자식노드를 탐색 했을 때 나오는 키 값이다.
# 1-2. Successor와 Predecessor
Successor
임의의 루트노드 x가 존재할 때 x보다 큰 값으로 이루어진 서브트리의 값 중 가장 작은 키 값을 의미한다.Predecessor
임의의 루트노드 x가 존재할 때 x보다 작은 값으로 이루어진 서브트리의 값 중 가장 큰 키 값을 의미한다.
# 2. 이진탐색트리 만들기
# 2-1. 노드 클래스 Node<K,V>
이진탐색트리의 개별 노드를 나타내는 것, 4개의 필드로 구성 된다.
- key : 키 값
- data : 데이터
- left : 왼쪽 자식 노드에 대한 참조(왼쪽 포인터)
- right : 오른쪽 자식 노드에 대한 참조(오른쪽 포인터)
# 예제 코드
class Node<K,V>{
K key;
V data;
Node<K, V> left;
Node<K, V> right;
// 생성자
Node(K key, V data, Node<K,V> left, Node<K,V> right){
this.key = key;
this.data = data;
this.left = left;
this.right = right;
}
// 키 값을 반환
K getKey(){
return key;
}
// 데이터를 반환
V getValue(){
return data;
}
// 데이터를 출력
void print(){
System.out.println(data);
}
}
private Node<K,V> root;
private Comparator<? Super K> comparator = null; // 비교자
# 2-2. 이진탐색트리 클래스 BinTree<K,V>
2개의 필드로 구성된다.
- root : 루트에 대한 참조를 보존, 유지하는 필드
- comparator : 키 값의 대소 관계를 비교하는 비교자
# 예제 코드
// 생성자
public BinTree(){
root = null; // 노드가 하나도 없는 이진탐색트리를 생성
}
//생성자
public BinTree(Comparator<? super K> c){
this();
comparator = c;
}
BinTree()생성자로 생성한 이진탐색트리에서는 노드 키 값의 대소관계를 판단할 때 자연 순서에 따라 수행된다.
따라서 키를 나타내는 K의 형이 Comparable 인터페이스를 구현하고 있는 Integer클래스나 String클래스등에 알맞다.
다른 생성자 BinTree(Comparator<? super K>c)와 달리 비교자를 설정하지 않으므로 필드 comparator의 값은 널이 된다.
BinTree(Comparator<? super K> c)생성자는 인수로 비교자를 전달받는 생성자이다.
이 생성자로 생성한 이진탐색트리는 노드의 대소 관계를 판단할 때 전달받은 비교자에 의해 수행된다.
this()에 의해 인수를 전달받지 않는 생성자 BinTree()를 호출. root가 null인 이진검색트리를 생성한다.
필드 comparator에 전달받은 c를 설정한다.
# 2-3. comp메서드: 두 키 값을 비교
2개의 키 값을 비교하는 메서드이다. 검색, 삽입, 삭제의 각 메서드에서 호출하는 비공개 메서드이다.
# 예제 코드
private int comp(K key1, K key2){
return (comparator == null) ? ((Comparable<K>)key1).compareTo(key2) : comparator.compare(key1, key2);
}
- key1 > key2면 양수
- key1 < key2면 음수
- key1 == key2면 0
이진 검색트리에 비교자 comparator가 설정되어 있는지에 따라 2개의 키값을 비교하는 방법이 다르다.
# 비교자 comparator가 null인 경우
((Comparable<K>)key1).compareTo(key2)
key1을 Comparable
# 비교자 comparator가 null이 아닌 경우
comparator.compare(key1, key2)
설정된 비교자 comparator의 compare메서드를 호출하여 두 키값 key1, key2를 비교
# 2-4. search 메서드: 키 값으로 검색
이진탐색트리에서 원하는 값을 찾으려면
루트부터 시작해 현재 선택한 노드의 키 값과 비교하면서 왼쪽, 오른쪽으로 검색을 진행한다.
- 루트부터 선택하여 검색을 진행한다. 여기서 선택하는 노드를 p라고 한다.
- p가 Null이면 검색에 실패한다.
- 검색하는 값 key와 선택한 노드 p의 키 값을 비교하여
- 값이 같으면 검색에 성공(검색 종류)한다.
- key가 작으면 선택한 노드에 왼쪽 자식 노드를 대입한다(왼쪽으로 검색 진행).
- key가 크면 선택한 노드에 오른쪽 자식 노드를 대입한다(오른쪽으로 검색 진행).
- 2번 과정으로 되돌아간다.
# 예제 코드
public V search(K key){
Node<K,V> p = root;
while(true){
if(p==null)
return null;
int cond = comp(key, p.getKey());
if(cond==0)
return p.getValue(); // 검색 성공
else if(cond<0)
p = p.left;
else
p = p.right;
}
}
키 값이 key인 노드를 검색하고 검색에 성공하면 그 노드의 데이터에 대한 참조를 반환한다.
# 2-5. add 메서드: 노드를 삽입
이진탐색트리의 조건을 유지하도록 노드를 삽입한다.
삽입할 노드의 키와 같은 값을 가지는 노드가 있다면 노드를 삽입해서는 안된다.
- 루트를 선택한다. 여기서 선택하는 노드를 node로 한다.
- 삽입할 키 key와 선택노드 node의 키 값을 비교한다. 값이 같다면 삽입에 실패한다(종료).
- 값이 같지 않은 경우 key값이 삽입할 값보다 작으면,
왼쪽 자식 노드가 없는 경우에는 노드를 삽입(종료)
왼쪽 자식 노드가 있는 경우에는 선택한 노드를 왼쪽 자식 노드로 옮긴다. - key값이 삽입할 값보다 크면,
오른쪽 자식 노드가 없는 경우에는 노드를 삽입(종료)
오른쪽 자식 노드가 있는 경우에는 선택한 노드를 오른쪽 자식 노드로 옮긴다.
- 값이 같지 않은 경우 key값이 삽입할 값보다 작으면,
- 2로 되돌아 간다.
# 예제 코드
private void addNode(Node<K,V> node, K key, V data){
int cond = comp(key, node.getKey());
if(cond == 0)
return;
else if(cond<0){
if(node.left == null)
node.left = new Node<K,V>(key, data, null, null);
else
addNode(node.left, key, data);
} else{
if(node.right == null)
node.right = new Node<K,V>(key, data, null, null);
else
addNode(node.right, key, data);
}
}
public void add(K key, V data){
if(root == null)
root = new Node<K,V>(kdy, data, null, null);
else
addNode(root, key, data);
}
# 2-6. remove 메서드: 노드를 삭제
노드를 삭제할 때는 세가지 서로 다른 상황에 알맞은 처리를 해야한다.
# 1) 자식 노드가 없는 노드를 삭제하는 경우
- 삭제할 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터를 null로 한다.
- 삭제할 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터를 null로 한다.
# 2) 자식 노드가 1개인 경우
- 삭제 대상 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다.
- 삭제 대상 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 한다.
# 3) 자식 노드가 2개인 경우
삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색한다.
(Predecessor, 자식노드가 하나이거나 하나도 존재하지 않는 특징이 있다.)검색한 노드를 삭제 위치로 옮긴다.
옮긴 노드를 삭제한다.
- 옮긴 노드에 자식이 없으면, 자식 노드가 없는 노드의 삭제 순서에 따라 노드를 삭제
- 옮긴 노드에 자식이 있으면, 자식 노드가 1개 있는 노드의 삭제 순서에 따라 노드를 삭제
# 예제 코드
public boolean remov(K key){
Node<K,V> p = root;
Node<K,V> parent = null;
boolean isLeftChild = true;
// 삭제할 키 검색
while(true){
if(p == null)
return false;
int cond = comp(key, p.getKey()); // key와 노드p의 키 값을 비교
if(cond == 0) // 같으면 검색 성공
break;
else{
parent = p;
if(cond < 0){ // key쪽이 작으면 왼쪽 자식으로 내려가고 왼쪽서브트리에서 검색
ifLeftChild = true;
p = p.left;
}
else{ // key쪽이 크면 오른쪽 자식으로 내려가고 오른쪽 서브트리에서 검색
isLeftChild = false;
p = p.right;
}
}
}
/*
자식노드가 없는 경우, 자식노드가 1개인 경우의 과정 수행
삭제 노드에 왼쪽 자식이 없으면 왼쪽 포인터가 null,
오른쪽 자식이 없으면 오른쪽 포인터가 null이 되는 방법 이용
*/
if(p.left == null){ // p에 왼쪽 자식이 없음
if(p == root)
root = p.right;
else if(isLeftChild)
parent.left = p.right;
else
parent.right = p.right;
}
else if(p.right == null){ // p에 오른쪽 자식이 없음
if(p == root)
root = p.left;
else if(isLeftChild)
parent.left = p.left;
else
parent.right = p.left;
}
// 자식 노드가 2개인 노드를 삭제하는 경우 수행
else{
parent = p;
Node<K,V> left = p.left; // 서브 트리 가운데 가장 큰 노드
isLeftChild = true;
while(left.right != null){ // 가장 큰 노드 left를 검색
parent = left;
left = left.right;
isLeftChild = false;
}
p.key = left.key; // left의 키 값을 p로 옮김
p.data = left.data; // left의 데이터를 p로 옮김
if(isLeftChild)
parent.left = left.left; // left를 삭제
else
parent.right = left.left; // left를 삭제
}
return true;
}