[자료구조] 트리(Tree) / 이진검색트리 (Binary Searching Tree)

yeonhwan619·2023년 9월 4일

목록 보기

4/6

트리

트리(Tree) 자료구조란 연결리스트와 같이 Node라는 단일 자료형을 연결시켜 만드는 자료구조이다. 하지만 트리는 연결리스트와 같이 선형적인 연결형태를 가지고 있지 않다는 중요한 차이점이 존재한다. 연결리스트의 Node가 next 또는 prev 프로퍼티를 통해 연결의 참조를 형성하고 있다면, 트리 자료구조는 left, right 프로퍼티등을 통해서 비선형적인 연결의 참조를 형성하고 있다. 트리 자료구조의 연결의 형태는 비선형적인 형태로 parent - child의 구조를 반복한다. 맨 위의 트리 Node는 root라고 불리며 모든 트리 Node들의 입구 역할을 하며, root의 left, right 프로퍼티에는 child역할을 하게될 다른 트리 Node들이 할당되고, 이 child 트리 Node들은 다시 자신들의 child의 parent역할을 하게 된다. 이러한 방식으로 Node들이 계속해서 연결되면 마치 나무를 뒤집어놓은 것과도 같은 모양을 하게 되는데, 이를 트리 자료구조라고 부른다.

트리 자료구조에서 사용하는 용어들은 다음과 같다.

Root : 트리의 입구역할을 하며 가장 최상위에 존재하는 Node
Leaf : 트리의 최하단에서 어떠한 Child도 가지지 않은 Node
Parent : 자신의 하위에 Child를 가지고 있다면 해당 Node는 하위 Node의 Parent Node이다.
Child : 자신이 상위의 Node에 연결되어 있다면 해당 Node는 상위 Node의 Child Node이다.
Sibiling : 같은 계층간에 존재하며, 서로 직접적으로 연결되어 있지 않은 Node들을 Sibiling Node라고 한다.
Edge : Node와 Node의 연결을 나타낸다.
Sub-tree : 전체 트리자료구조내에 존재하는 작은 부분 tree 구조를 말한다.

트리 자료구조의 특징은 다음과 같은 용어들을 통해 나타낸다.

Size (크기) : 자신을 포함하여 자신의 하위로 모두 연결되어있는 Node들의 총 갯수
Depth (깊이) : Root 에서 시작하여 특정 Node에 도달하기 까지 거쳐야하는 edge의 갯수
Level (단계) : 해당 트리에서 특정 깊이를 공유하는 Sibiling Node들의 집합
Height (높이) : Root 에서 가장 깊이 존재하는 Node까지의 연결 단계
Degree (차수) : 한 Parent 가 가지고 있는 edge의 갯수

트리의 종류

위에서 언급했다시피 트리자료구조란 비선형적인 트리 Node들간의 연결을 의미할 뿐이고, 이를 활용한 다양한 트리자료구조가 존재한다. 부모의 차수가 2개인 sub-tree의 모양이 반복되는 이진트리(Binary Tree)의 형태부터, 차수를 점차 늘려가며 트라이(Trie-3차), n차 트리까지 필요에따라 구현하여 사용가능하다. 여기서는 이진트리를 위주로 살펴보도록 하자.

이진트리의 종류

이진트리에는 이진트리의 기본적인 연결 형태는 유지하되 어떻게 Node들의 연결규칙을 형성하느냐에 따라 분류가 나뉘어진다.

이진트리(Binary Tree) : 가장 기본적인 형태로, parent의 차수가 최대 2를 넘을 수 없다.
정이진트리(Full Binary Tree) : 모든 노드가 0 혹은 2의 차수를 지녀야만 한다.
완전이진트리(Complete Binary Tree) : 마지막 Leaf Node를 제외하고 모든 Node가 Child Node를 순서대로 채운 상태를 지니고 있어야만 한다.
포화이진트리(Perfect Binary Tree): 정이진트리이면서 완전이진트리인 이진트리이다.
편향이진트리(Skewed Binary Tree): 트리 자료구조이지만, 왼쪽 혹은 오른쪽으로만 Node를 연결하여 선형적인 구조를 만들어낸다.
균형이진트리(Balanced Binary Tree): 트리 자료구조에서 모든, 왼쪽 sub-tree들과 오른쪽 sub-tree들의 depth 차이가 1이하로 존재해야만 한다.
이진탐색트리(Binary Search Tree): 이진 트리의 형태이지만, Parent 노드의 왼쪽 sub-tree들은 모두 Parent의 값보다 작아야하고, 오른쪽 sub-tree들은 Parent의 값보다 커야만한다.

이진검색트리(Binary Searching Tree)

위에서 설명한 트리의 자료구조와 이진검색의 알고리즘을 합하여 데이터를 보다 탐색에 용이하도록 구성한 것이 이진검색트리이다. 이진검색트리는 이진검색을 활용하기 때문에 트리 자료구조의 parent-child간의 연결간에 규칙이 발생한다.

parent의 child는 2개를 초과할 수 없다.

left-child의 value는 반드시 parent의 value 보다 작아야한다.

right-child의 value는 반드시 parent의 value 보다 커야한다.

이렇게 트리 Node들을 연결하게 되면, 이진검색알고리즘을 통해서 데이터를 빠르게 탐색하여 사용할 수 있다.

이진검색트리 구현

이진검색트리(BST) 를 직접 구현해보도록 하자. BST를 구현하기 위해서는 먼저 기존에 리스트형태에 사용했던 Node가 아니라 트리 자료구조에 적합하도록 Node를 작성한다. 이후, BST를 담아줄 수 있도록 클래스를 선언해 이를 구현한다.

class TreeNode{
	constructor(value, left=null, right=null) {
    	this.value = value;
      	this.left = left;
      	this.right = right;
    }
}


class BST {
	constructor(root = null;) {
    	this.root = root;
    }
}

const Node1 = new TreeNode(5);
const BST = new BST(Node1);

// 위의 그림과 같이 트리Node들을 선언해준 후,
// BST를 생성해 Root만을 할당해주었다.

이진검색트리 메소드

BST를 구현하였으니, BST에서 활용할 수 있는 메소드를 작성해보도록하자. BST의 규칙에 맞게 트리 Node들의 연결을 구성하는 것도 메소드를 통해서 할 것이다. BST의 메소드들은 다음과 같다.

insert / add : 이진검색트리에 Node를 추가해주는 메소드이다. insert는 재귀적으로, add는 반복문을 통해서 구현한다.
search / find : 이진검색트리에서 해당 Node를 찾는 메소드이다. search는 재귀적으로, find는 반복문을 통해서 구현한다.

insert(value, root?)

value를 전달받아 새로운 트리 Node를 생성하고, 이를 BST의 규칙을 따라서 트리에 삽입해주는 메소드이다.

1. value : 트리 Node 생성에 사용될 값이다.
2. root? : root 값을 전달받는다. 기본값은 this.root이다. 재귀적으로 트리를 탐색하기 위해 사용된다.
return : 새롭게 추가된 Node를 반환한다.

insert(value, root=this.root) {
	if(!root) return new TreeNode(value);
   // 만약 root가 없으면 새로운 Node를 생성하고 끝마친다.
	
  // 1) 값이 작을경우, 왼쪽 sub-tree를 탐색한다.
  	if(value < root.value) {
      // 왼쪽 sub-tree의 끝을 발견하면,
      // 해당 자리가 새로운 Node가 삽입될 자리이다.
      if(!root.left) {
      	root.left = new TreeNode(value);
      } else {
        // 발견할 때까지 재귀적으로 탐색을 계속한다.
    	return insert(value, root.left);
      }
    
    // 2) 값이 클 경우, 오른쪽 sub-tree를 탐색한다.
    } else if(value > root.value) {
      // 오른쪽 sub-tree의 끝을 발견하면,
      // 해당 자리가 새로운 Node가 삽입될 자리이다.
      if(!root.right) {
      	root.right = new TreeNode(value);
      } else { 
        // 발견할 때까지 재귀적으로 탐색을 계속한다.
     	return insert(value, root.right);
      }
    } else {
      	// 해당 값이 존재하면 값을 추가하지 않고 반환한다.
    	return root;
    }
}



BST.insert(3);
BST.insert(7);

//     5
//    / \
//   3   7

add(value)

insert와 동일하지만 반복적(iterative)인 방법으로 새롭게 구현한다.

1. value : 트리 Node 생성에 사용될 값이다.
return : return : 새롭게 추가된 Node를 반환한다.

add(value) {
	const newNode = new TreeNode(value);
    // 만약 root가 없으면 새로운 Node를 생성하고 끝마친다.
  	if(!this.root) = return newNode;
  	// 반복법을 사용하기 때문에, pointer를 생성한다.
  	let curNode = this.root;	
  
 	while(true) {
      // 1) 값이 작을경우, 왼쪽 sub-tree를 탐색한다.
    	if(value < curNode.value) {
            // 왼쪽 sub-tree의 끝을 발견하면,
      		// 해당 자리가 새로운 Node가 삽입될 자리이다.
        	if(!curNode.left) {
            	return curNode.left = newNode;
            } else {
              	// 발견할 때까지 포인터를 변경하며 탐색을 계속한다.
            	curNode = curNode.left;
            }
          // 2) 값이 클 경우, 오른쪽 sub-tree를 탐색한다.
        } else if(value > curNode.value) {
             // 오른쪽 sub-tree의 끝을 발견하면,
      		// 해당 자리가 새로운 Node가 삽입될 자리이다.
        	if(!curNode.right) {
            	return curNode.right = newNode;
            } else {
              	// 발견할 때까지 포인터를 변경하며 탐색을 계속한다.
            	curNode = curNode.right;
            }
        } else {
            // 해당 값이 존재하면 값을 추가하지 않고 반환한다.
        	return curNode;
        }
    }
}

BST.insert(1);
BST.insert(4);
BST.insert(6);
BST.insert(10);

//     	  5
//   	 / \
//   	3   7
//	   /\  /\
//    1 4 6 10

search(value, root?)

value를 전달받아 해당 값을 가지는 Node를 재귀적으로 찾아 반환한다.

1. value : 트리 탐색에 사용될 값이다.
2. root? : root 값을 전달받는다. 기본값은 this.root이다. 재귀적으로 트리를 탐색하기 위해 사용된다.
return : 찾아낸 Node를 반환한다.

search(value, root=this.root) {
  // 탐색하면서 root값이 존재하지 않게 됐을 때는 null을 반환한다.
	if(!root) return null;
  	
  // 1) 값이 현재 root의 값보다 작으면 왼쪽 sub-tree 탐색
  	if(value < root.value) {
    	search(value, root.left);
  // 2) 값이 현재 root의 값보다 크면 오른쪽 sub-tree 탐색
    } else if(value > root.value) {
    	search(value, root.right);
  // 3) 위의 세 가지 경우에 속하지 않으면 발견한 것이므로 반환한다.
    } else {
    	return root;
    }
}

BST.search(3);
// TreeNode { value: 3, left: TreeNode(1), right: TreeNode(4) }
BST.search(10);
// TreeNode { value: 10, left: null, right: null }

find(value)

value를 전달받아 해당 값을 가지는 Node를 반복적으로 찾아 반환한다.

1. value : 트리 탐색에 사용될 값이다.
return : 찾아낸 Node를 반환한다.

find(value) {
    // 초기 트리가 비어있을 경우 null을 반환한다.
  	if(!this.root) return null;
  	
 	// pointer 생성
  	let curNode = this.root;
  
  	while(true) {
      	// 값을 찾았으면 해당 Node를 반환한다.
    	if(value === curNode.value) return curNode;
      	
      	// 1) 해당 값이 작을 경우
    	if(value < curNode.value) {
          	// 탐색을 계속할 Node가 있으면 pointer를 교체한다.
      		if(curNode.left) {
      			curNode = curNode.left;
      		} else {
              	// 아닐경우 null을 반환한다.
      			return null;
      		}
    	}
        // 1) 해당 값이 클 경우	
    	if(value > curNode.value) {
          	// 탐색을 계속할 Node가 있으면 pointer를 교체한다.
      		if(curNode.right) {
      			curNode = curNode.right;
      		} else {
               // 아닐경우 null을 반환한다.
      			return null;
      		}
    	}
    }
}

BST.search(7);
// TreeNode { value: 7, left: TreeNode(6), right: TreeNode(10) }
BST.search(6);
// TreeNode { value: 6, left: null, right: null }