[자료구조]Tree 공부: 이진트리 & BST & N항 트리

 오늘은 트리에 대해 공부하겠습니다.

 

 본격적으로 트리에 대해 알아보기 전에, 선형 자료구조에는 배열, 연결 리스트, 스택, 큐 등이 있는데요! 선형 자료구조는 최대 두 가지 방향(순방향과 역방향)으로만 자료를 순회할 수 있습니다. 

 때문에 문제를 해결하기에 매우 제한적이며 복잡한 문제에는 적용할 수 없는데요.

 

 그래서 우리는 비선형 자료구조를 사용하여 좀 더 복잡한 문제를 해결할 수 있습니다. 그 중 하나가 바로 트리입니다. 

 

1. 트리 Tree 란?

 

 트리는 노드와 노드 사이를 부모-자식 관계로 연결하여 계층을 구성하는 자료구조입니다. 

 

 트리의 중심이 되는 노드를 루트 노드(root node)라고 부르고, 트리 내의 연산은 이 root 노드를 통해 접근합니다.

 

 트리 자료 구조의 연산에는 크게 검색, 삽입, 삭제가 있습니다.  

 

출처: https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=4717010&logNo=60209552604

 

 이제 트리에는 어떤 종류들이 있는지, 연산 과정은 어떻게 되는지 살펴보겠습니다. 

 

 

2. 이진 트리 (Binary Tree)

 

 이진 트리는 하나의 노드가 두 개의 자식 노드를 가질 수 있는 트리를 말합니다. 가장 널리 사용되는 트리 중 하나입니다.

 

출처: https://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Binary_tree.svg/220px-Binary_tree.svg.png

//이진 트리의 자료구조
struct node{
	data_type data;
    	node* left_child;
    	node* right_child;
};

 

 이진 트리의 검색, 삽입, 삭제 연산은 재귀 호출을 통해 구현할 수 있습니다. 

 

 

 

 

2. 이진 검색 트리 BST(Binary Search Tree)

 

 이진 검색 트리는 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 크다는 특징이 있습니다. 즉, 왼쪽 자식 노드 <= 부모 노드 <= 오른쪽 자식 노드 라고 표현할 수 있습니다. 

 

 이진 트리에서 하나의 노드를 찾기 위해 드는 시간 복잡도가 O(N)이라면 

 

 이진 검색 트리는 검색 범위가 절반으로 줄어 시간 복잡도가 O(log N)이 됩니다. 

 

출처: https://t1.daumcdn.net/cfile/tistory/2321CB4951A467AC0B

 

 자료 구조는 이진 트리와 동일합니다. 

 

 삽입, 삭제 연산을 할 때 이진 검색 트리의 구조에 맞게 수정하는 것이 중요합니다. 

 

 

 

3. N 항 트리(N-ary tree)

 

 N 항 트리는 각 노드가 N개의 자식을 가질 수 있습니다. 

 

 컴퓨터의 파일 시스템 구조처럼 다수의 파일과 폴더를 관리해야 할 때 많이 쓰이는 자료구조입니다. 

 

출처: https://media.vlpt.us/images/leyuri/post/9f95fbb8-58f6-4515-b0c5-88c76c9d3dd1/%EB%A6%AC%EB%88%85%EC%8A%A4%EB%A6%AC%EB%88%85%EC%8A%A4(Linux)_%ED%8C%8C%EC%9D%BC%EC%8B%9C%EC%8A%A4%ED%85%9C.png

//n항 트리의 자료구조
struct node{
	data_type data;
    	vector<node*> children;
}