이원 탐색 트리

혁콩·2022년 10월 31일

자료구조 알고리즘

1. Intro

이진트리의 종류 중 하나인 이원 탐색 트리(Binary Search Tree)에 대해 알아보고자 한다.

2. Contents

Binary Search Tree : BST

이원탐색트리는 이진트리이며 공백이 아닐 시 다음과 같은 성질을 갖는다.

모든 원소는 상이한 키를 가짐(중복X)

왼쪽 서브트리 원소들의 키 < 루트의 키

오른쪽 서브트리 원소들의 키 > 루트의 키

이진트리와의 차이는 BST는 값을 정렬함으로써 임의의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적이라는 것이다.

아래에선 BST의 탐색, 삽입, 삭제 알고리즘을 알아보겠다.

3. BST 구조 및 연산

3.1. 기본구조 :

필드로 왼쪽, 오른쪽 자식과 키값을 갖는 TreeNode와 rootNode를 갖는 BST로 구성

class TreeNode {
	String key;
	TreeNode Lchild;
	TreeNode Rchild;
}

class BinarySearchTree {
	private TreeNode rootNode;
}

3.2. 탐색 :

루트노드부터 시작하며, 트리가 공백이면 실패, 작으면 왼쪽 크면 오른쪽으로 탐색한다.

	public TreeNode BSTsearch(String k) {
		TreeNode p = rootNode;
		while (true) {
			if (p == null) { // 공백 이진트리로 탐색 실패
				return null;
			} else if (k.compareTo(p.key) == 0) { // 탐색 성공
				return p;
			} else if (k.compareTo(p.key) < 0) { // 오른쪽 서브트리 탐색
				p = p.Lchild;
			} else { // 왼쪽 서브트리 탐색
				p = p.Rchild;
			}
		}
	}

3.3. 삽입 :

삽입의 경우 다음과 같은 순서로 진행된다.

1) K를 key 값으로 가진 원소가 있는지 확인
2) 탐색을 실패하면 반복문이 종료된 위치에 원소를 삽입

삽입을 위해선 삽입을 원하는 자리의 부모노드가 필요하기 때문에 탐색 시 부모노드를 함께 찾아준다.

	public void BSTinsert(String k) {
		TreeNode p = rootNode, q = p;

		while (p != null) {
			if (k.compareTo(p.key) == 0) {
				break;
			}
			q = p; // 부모노드 q를 같이 찾아줌
			if (k.compareTo(p.key) < 0) {
				p = p.Lchild;
			} else {
				p = p.Rchild;
			}
		}

		TreeNode newNode = new TreeNode(); // 삽입할 노드 생성
		newNode.key = k;
		newNode.Lchild = null;
		newNode.Rchild = null;

		if (q == null) { // 트리가 비었다면
			rootNode = newNode; // 새로 만든 노드가 루트노드가 됨
		} else if (k.compareTo(q.key) < 0) { // 삽입하려는 값이 부모보다 작다면
			q.Lchild = newNode; // 왼쪽 서브트리로 삽입
		} else {
			q.Rchild = newNode; // 크다면 오른쪽 서브트리로 삽입
		}
	}

3.4. 삭제 :

삭제 연산은 다음과 같은 순서로 진행된다.

1) 키값이 주어졌을 때 키값을 가진 원소 탐색
2) 원소를 찾으면 삭제 연산 수행

또한 삭제 연산은 세가지 경우로 나눠 연산을 수행한다.

자식이 없는 노드의 삭제(리프노드)

자식이 하나인 노드의 삭제

자식이 둘인 노드의 삭제

이 때 자식이 둘인 노드를 삭제할 경우 트리의 값을 재구성해줘야 하는데, 왼쪽 서브트리의 최대값으로 현재 키값을 대체하도록 한다.

매개변수로 삭제하고자 하는 노드 node의 Lchild를 받아 가장 큰 값을 탐색한다.

	private TreeNode maxNode(TreeNode root) {
		// 왼쪽 서브트리에서의 최대 원소 값
		// 만약 왼쪽 서브트리가 오른쪽 자식노드가 있다면 순환 호출
		if(root.Rchild == null) {
			return root;
		}
		return maxNode(root.Rchild);
	}

이제 삭제를 해보자 !

	private TreeNode delete(TreeNode root, String k) {
		TreeNode p = root, q=p;
		while (p != null) { 
			if (p.key.compareTo(k) == 0) {
				break;
			}
			q = p; // 부모노드 탐색
			if (k.compareTo(p.key) < 0) {
				p = p.Lchild;
			} else {
				p = p.Rchild;
			}
		}
		
		if(p == null) { // 트리가 비었다면
			return null;
		}
		// 1. 자식이 없는 리프 노드일 때
		else if(p.Lchild == null && p.Rchild == null) {
			if(q.Lchild == p) { // 현재 노드가 부모의 왼쪽 자식이라면
				q.Lchild = null; // 왼쪽 연결을 끊어줌
			} else {
				q.Rchild = null; // 아니라면 오른쪽 연결을 끊어줌
			}
		}
		// 2. 자식이 하나인 노드일 때 ->
		// 자식을 삭제되는 노드 자리에 넣기
		else if(p.Lchild == null || p.Rchild == null) {
			if(p.Lchild != null) { // 왼쪽 자식이 있을 때
				if(q.Lchild == p) { // 현재 노드가 부모의 왼쪽 자식이라면
					q.Lchild = p.Lchild; // 현재 자리에 왼쪽 자식을 넣어줌
				} else {
					q.Rchild = p.Lchild; 
				}
			} else { // 오른쪽 자식이 있을 때
				if(q.Lchild == p) { // 현재 노드가 부모의 오른쪽 자식이라면
					q.Lchild = p.Rchild; // 현재 자리에 오른쪽 자식을 넣어줌
				} else {
					q.Rchild = p.Rchild;
				}
			}
		// 3. 자식이 둘인 노드일 때 ->
		// maxNode를 사용하여 삭제되는 노드 자리 왼쪽 서브트리에서 가장 큰 값 넣기
		} 
		else {
        	// 왼쪽 서브트리가 리프노드일때 (maxNode의 잘못된 호출을 막기위함)
			if(p.Lchild.Lchild == null && p.Lchild.Rchild == null) {
				p.key = p.Lchild.key; 
				p.Lchild = null;
			} else {
				q = maxNode(p.Lchild); // 왼쪽 서브트리에서 가장 큰 값을 찾아
				p.key = q.key; // 현재 노드의 키값을 바꿔준 후
				delete(p.Lchild, p.key); // 순환호출한다.
			}
		} 
		return p;
	}

	public void BSTdelete(String k) {
		// delete 호출
		delete(rootNode, k);
	}