[자료구조]Java - Binary Search Tree(이진 탐색트리) 개념 + 구현

Binary Search Tree란?

Binary(이진) Search(탐색) Tree(트리)가 합쳐진 것으로, 

즉, 이분화된 탐색을 위한(혹은 특화된) 트리 자료구조라는 뜻이다.

 

그렇다면 트리가 무엇일까?

 

위와 같은 구조를 Tree 구조라고 하는데, 거꾸로 보면 나무같이 생겨서 그렇게 부른다고 한다.

여기서 몇 가지 알아야 할 것이 있는데, 그 부분은 아래와 같다. 

 

부모 노드(parent node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 높은 노드를 의미 (ex. F의 부모노드 : B)

자식 노드(child node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 낮은 노드를 의미 (ex. C의 자식노드 : G, H)

루트 노드 (root node) : 일명 뿌리 노드라고 하며 루트 노드는 하나의 트리에선 하나밖에 존재하지 않고, 부모노드가 없다. 위 이미지에선 녹색이 뿌리노드다.

단말 노드(leaf node) : 리프 노드라고도 불리며 자식 노드가 없는 노드를 의미한다. 위 이미지에서 주황색 노드가 단말노드다.

내부 노드(internal node) : 단말 노드가 아닌 노드

형제 노드(sibling node) : 부모가 같은 노드를 말한다. (ex. D, E, F는 모두 부모노드가 B이므로 D, E, F는 형제노드다.)

깊이(depth) : 특정 노드에 도달하기 위해 거쳐가야 하는 '간선의 개수'를 의미 (ex. F의 깊이 : A→B→F 이므로 깊이는 2가 됨)

레벨(level) : 특정 깊이에 있는 노드들의 집합을 말하며, 구현하는 사람에 따라 0 또는 1부터 시작한다. (ex. D, E, F, G, H)

차수(degree) : 특정 노드가 하위(자식) 노드와 연결 된 개수 (ex. B의 차수 = 3 {D, E, F} )

 

 

그러면 Binary(이진)은 무슨 뜻일까? 쉽게 말해 이분화 된다는 것이다.

 

앞서 본 트리 구조에서 특정한 형태로 제한을 하게 되는데, 모든 노드의 최대 차수를 2로 제한한 것이다. 조금 쉽게 말하자면 각 노드는 자식노드를 최대 2개까지밖에 못갖는다는 것이다. 이를 '이진 트리(Binary Tree)'라고 한다.

위의 이미지에서는 B노드가 차수가 3이므로 이진트리가 아니다. 즉, 이진트리의 경우 다음과 같은 형태를 띈다.

그럼 이제 마지막으로 탐색에 특화 된 트리는 무엇을 의미할까?

 

일단, 한 번 고민을 해보자. 만약 위 이진트리의 각 노드가 갖고있는 값이 규칙 없이 중구난방이면 특정 값을 찾기 위해서는 최악의 경우 저 각각의 노드를 모두 순회(탐색)해야 한다.

 

이를 방지하고자 위 이진트리에서 우리는 조건을 하나 더 붙이게 된다.

 

"부모 노드를 기준으로 왼쪽 자식 노드들은 부모 노드보다 값이 작으며, 오른쪽 자식 노드들은 부모 노드보다 값이 크다"

 

조금 더 줄여 말하자면 나를 부모 노드라고 할 때 자신보다 작은 값은 왼쪽 자식노드, 자신보다 큰 값은 오른쪽 노드에 배정한다는 것이다.

 

이해를 돕기 위해 이미지로 보자면 아래와 같다.

위와 같이 부모 노드 기준으로 대소 관계에 따라 왼쪽엔 작은 값이, 오른쪽엔 큰 값이 들어가도록 구성하면 된다.

 

이렇게 구성사면 우리가 특정 값을 탐색하려 할 때 다음과 같은 장점이 있다.

현재 탐색 노드와 찾으려는 값의 대소 관계를 비교해서 작다면 왼쪽 노드로 탐색하러 가면 되고, 반대로 크면 오른쪽 노드로, 같다면 그 값을 찾게 된 것이다.

 

이렇게 구성하면 우리가 원하는 이진 탐색 트리가 되는 것이다.

 

 

그렇다면 개념은 대충 알게되었으니, 구현으로 넘어가보도록 하겠다.

---

이진탐색트리 구현

---

Node 구현

 

기본적으로 Tree는 Node를 기반으로 구성된다. 물론 배열로도 구현은 가능하지만, 이후 있을 Tree 자료구조들에선 '회전'이라는 개념이 등장하기 때문에 오히려 노드로 구현하는게 좀 더 용이하다.

 

앞선 설명에서도 보셨듯 일단 Tree에 필요한 노드(Node)는 다음과 같이 구성된다.

 

static class Node {
        int data;
        Node left;
        Node right;

        Node(int data) {
           this.data = data;
        }
    }

    public Node root;

---

순환적인 탐색 연산(재귀적인 방법) 구현

 

이진 탐색 트리에서 특정한 키값을 가진 노드를 찾기 위해서는 먼저 주어진 탐색키 값과 루트 노드의 키값을 비교한다.

비교한 결과에 따라 3가지로 나누어진다.

 

1. 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
2. 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 작으면, 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다.
3. 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 크면, 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.

 

1. 탐색키 값 == 루트 노드의 키 값 : 탐색 완료
2. 탐색키 값 < 루트 노드의 키 값 : 루트 노드의 왼쪽 자식 노드를 기준으로 재탐색
3. 탐색키 값 > 루트 노드의 키 값 : 루트 노드의 오른쪽 자식 노드를 기준으로 재탐색

 

 

 

코드구현

// 순환적인 탐색
public static Node circularSearch(Node node, int key) {
    if(node == null) {
        return null;
    }

    if(key == node.data) {
        return node;
    } else if(key < node.data) {
        return circularSearch(node.left, key);
    } else {
        return circularSearch(node.right, key);
    }
}

 

---

반복적인 탐색 연산(while을 사용한 반복문) 구현

 

while문을 이용해 반복적인 기법으로 탐색 연산을 구현한 것이다.

 

매개변수 node가 null이 아니면 반복을 계속한다.

 

반복 루프 안에서는 현재 node의 data값이 key값과 같은지 검사한다.

• 같으면 탐색 성공으로 현재 노드를 반환하고 끝
• key가 현재 노드값보다 작으면 node 변수를 node의 왼쪽 자식 노드를 가리키도록 변경
• key값이 현재 노드의 값보다 크면 node 변수를 node의 오른쪽 자식을 가리키도록 변경

node가 단말 노드까지 내려가서 null 값이 될 때까지 반복

 

만약 반복이 종료되었는데도 아직 함수가 리턴되지 않았다면 탐색이 실패한 것으로 null 반환

 

 

 

 

코드구현

// 반복적인 탐색 
public static Node repetitiveSearch(Node node, int key) {
	while(node != null) {
		if(key == node.data) {
			return node;
		} else if(key < node.data) {
			node = node.left;
		} else {
			node = node.right;
		}
	}

	return null; // 탐색 실패했을 경우 
}

 

---

이진 탐색 트리에서의 삽입 연산

 

원소를 삽입하기 위해서는 먼저 탐색을 수행해야 한다.

이진 탐색 트리에서는 같은 키값을 갖는 노드가 없어야 하고, 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치가 되기 때문이다.

 

예를 들어, 9를 삽입하는 경우 루트(18)에서 부터 9를 탐색한다.

 

트리안에 9가 있다면 탐색 성공 > 중복 > 삽입 불가

 

트리안에 9가 없다면 탐색 실패 > 탐색 실패한 위치(그림에서는 12)가 9가 삽입될 자리

 

따라서 위 그림에서 9는 12의 하위 왼쪽 노드로 추가된다. 

 

새로운 노드는 항상 단말 노드에 추가된다.

단말 노드를 발견할 때까지 루트에서 key를 검색한다.

단말 노드가 발견되면 새로운 노드가 단말 노드의 하위 노드로 추가된다.

 

여기서 단말 노드란? 다른 노드가 연결되어있지 않은 노드(위 그림에서는 3, 12, 27 이 해당됨)를 말한다.

 

 

 

 

코드구현

// 노드 삽입 
public Node insertNode(Node node, int key) {
	if(node == null) { 
		return new Node(key); // 노드가 빈 경우, 새로운 노드 삽입후 반환 
	}

	// 그렇지 않으면 순환적으로 트리를 내려감 
	if(key < node.data) {
		node.left = insertNode(node.left, key);
	} else if(key > node.data) {
		node.right = insertNode(node.right, key);
	}

	// 삽입 완료 후, 루트 노드 반환하며 끝 
	return node;
}

 

---

이진 탐색 트리에서의 삭제 연산

 

이진 탐색 트리에서 가장 복잡한 연산이다.

 

삭제하기 위해서 먼저 노드를 탐색해야 한다.

탐색 후에는 3가지 경우를 고려해야 한다.

 

1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 하나의 서브 트리만(왼쪽 or 오른쪽) 가지고 있는 경우 
3. 삭제하려는 노드가 두 개의 서브 트리를 가지고 있는 경우 

1. 삭제하려는 노드가 단말 노드일 경우 

단말 노드 아래에는 더 이상의 노드가 없으므로 단말 노드만 지우면 된다.

 

단말 노드의 부모 노드를 찾아서 부모 노드의 링크 필드를 null로 만들어 연결을 끊는다.

 

 

2. 삭제하려는 노드가 하나의 서브 트리만 가지고 있는 경우

자기 노드는 삭제하고, 서브 트리는 자기 노드의 부모 노드에 붙여주면 된다.

 

 

3. 삭제하려는 노드가 두 개의 서브 트리를 가지고 있는 경우

어떤 노드를 삭제 노드 위치로 가져올 것이냐가 중요하다.

삭제되는 노드와 가장 값이 비슷한 노드를 후계자로 선택해야 이진 탐색 트리가 그대로 유지된다.

 

그렇다면 가장 값이 가까운 노드란?

왼쪽 서브 트리에서 가장 큰 값이나 오른쪽 서브트리에서 가장 작은 값이 삭제되는 노드와 가장 가깝다.

 

 

• 왼쪽 서브 트리의 가장 큰 값 -  왼쪽 서브트리에서 가장 오른쪽에 있는 노드
• 오른쪽 서브트리에서 가장 작은 값 - 오른쪽 서브트리의 가장 왼쪽에 있는 노드

이 두 노드는 이진 탐색 트리를 중위 순회하였을 경우, 각각 선행 노드와 후속 노드에 해당한다.

 

예를 들어 삭제 노드가 18일 경우, 후계자가 될 수 있는 노드는 12와 22가 된다.

18 자리로 두 노드를 옮겨도 아무런 문제가 일어나지 않음

 

이 두 후계자 중에서 어떤 노드를 선택해야 할까?

상관없다. 지금은 오른쪽 서브 트리에서 가장 작은 값을 후계자로 정해보자.

 

 

삭제되는 노드의 오른쪽 서브 트리에서 가장 작은 값을 갖는 노드는

오른쪽 서브트리에서 왼쪽 자식 노드를 타고 null을 만날 때까지 계속 타고 내려가면 찾을 수 있다.

 

 

최종적으로 22가 후계자가 되고, 22가 18의 자리로 이동된다.

 

 

 

 

코드구현

// 노드 삭제 
public Node deleteNode(Node root, int key) {
	if(root == null) {
		return root;
	}

	if(key < root.data) { // 키가 루트보다 작다면, 왼쪽 서브 트리에 있는 것 
		root.left = deleteNode(root.left, key);
	} else if(key > root.data) { // 키가 루트보다 크다면, 오른쪽 서브 트리에 있는 것 
		root.right = deleteNode(root.right, key);
	} else { // 키가 루트와 같다면 이 노드가 바로 삭제할 노드
		if(root.left == null) { // 1번, 2번의 경우 - 1. 단말 노드인 경우 / 2. 하나의 서브트리만 있는 경우 
			return root.right; // 널 값이면 널 반환 / 오른쪽 있으면 오른쪽 반환해서 이전의 if, else if에서의 왼쪽이든 오른쪽 노드에 붙여주는 것
		} else if(root.right == null) {
			return root.left; // left가 널인 경우와 동일 
		}

		// 3번의 경우 - 3. 두개의 서브 트리가 있는 경우 (left, right 둘 다 null 아님  
		Node temp = minValueNode(root.right); // 오른쪽 서브 트리에서 가장 작은 값(가장 왼쪽 노드)가 후계 노드 

		root.data = temp.data; // 후계 노드 값 복사(삭제할 노드의 값을 후계 노드 값으로 변경  
		root.right = deleteNode(root.right, temp.data); // 후계 노드 삭제 - 오른쪽 노드에게 가장 작은 값을 가졌던 맨 왼쪽 단말노드를 다시 deleteNode를 호출해 삭제하라고 함  
	}

	return root;
}

// 후계 노드 찾기 - 오른쪽 서브트리에서 가장 작은 값을 가지는 노드 반환 
public Node minValueNode(Node node) { 
	Node currentNode = node;

	while(currentNode.left != null) {
		currentNode = currentNode.left; // 맨 왼쪽 단말 노드를 찾으러 내려감 
	}
	return currentNode;
}

// 후계 노드 찾기 - 왼쪽 서브트리에서 가장 큰 값을 가지는 노드 반환
public Node maxValueNode(Node node) { 
	Node currentNode = node;

	while(currentNode.right != null) {
		currentNode = currentNode.right; // 맨 오른쪽 단말 노드를 찾으러 내려감 
	}
	return currentNode;
}

 

다음으로 이진트리를 탐색하는 방법에 대해 알아보겠다.

---

이진트리 탐색방법

 

이진 트리(Binary Tree)를 탐색하는 방법에는 크게 다음의 4가지가 있다.

• 전위순회(Preorder Traversal) : VLR
• 중위순회(Inorder Traversal) : LVR
• 후위순회(Postorder Traversal) : LRV
• 레벨순회(Levelorder Traversal) 또는 BFS(Breadth-First Search; 너비 우선 탐색)

여기서 V는 루트를 방문, L은 왼쪽 서브 트리 방문, R은 오른쪽 서브트리를 방문 하는 작업이다.

 

레벨순회(;BFS)를 제외한 나머지 순회방식은 DFS(Depth-First Search; 깊이 우선 탐색)으로 분류할 수 있다.

 

---

전위순회(preorder traversal)

전위순회는 루트 노드를 먼저 탐색하고, 자식 노드를 탐색하는 방식이다.

 

public void preOrder(Node node) {
	if(node != null) {
		System.out.print(node.data + " ");
		if(node.left != null) preOrder(node.left);
		if(node.right != null) preOrder(node.right);
	}
}

 

---

중위순회(inorder traversal)

 

중위순회는 왼쪽 자식 노드를 탐색하고, 루트 노드를 탐색하고, 오른쪽 자식 노드를 탐색하는 방식이다.

 

//중위 순회 Inorder : Left -> Root -> Right
public void inOrder(Node node) {
	if(node != null) {
		if(node.left != null) inOrder(node.left);
		System.out.print(node.data + " ");
		if(node.right != null) inOrder(node.right);
	}
}

 

 

---

후위순회(postorder traversal)

후위순회는 왼쪽 자식 노드를 탐색하고, 오른쪽 자식 노드를 탐색하고, 루트 노드를 탐색하는 방식이다.

 

//후위순회 Postorder : Left -> Right -> Root
public void postOrder(Node node) {
	if(node != null) {
		if(node.left != null) postOrder(node.left);
		if(node.right != null) postOrder(node.right);
		System.out.print(node.data + " ");
	}
}

 

 

 

 

 

 

 

📗참고사이트

자바 [JAVA] - Binary Search Tree (이진 탐색 트리) 구현하기

 

[Java] 트리 Tree 3 - 이진 탐색 트리

 

[Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현

 

이진 트리 순회: 전위, 중위, 후위, 레벨