CS/자료구조

[자료구조] 비선형 자료구조 1탄 : 트리

개발중인 감자 2023. 8. 6. 22:35

 

1. 비선형 자료구조란? (Non-Linear)

자료 뒤에 하나의 자료만 올 수 있던 선형 자료구조와 달리, 여러 개의 자료가 올 수 있는 자료구조이다. 계층적인 구조도 비선형 자료구조이다. 1:n 혹은 n:n 관계을 나타낸다. 트리, 그래프가 해당 구조에 해당된다. 

 

2. 트리의 개념 

 

트리는 계층적인 자료를 표현하는데 적합한 자료구조이다. 또한 한 개 이상의 노드로 이루어진 유한집합이다.

트리의 구성요소에 해당하는 A 부터 I 까지 노드 (node) 라고 한다. 

 

📌 트리의 용어들 

루트 노드 : A (계층적인 구조에서 가장 높은 곳에 있는 노드)
서브 트리 : 루트 제외한 나머지 노드들 
간선 : 노드간의 연결선 
부모 노드 : A는 C의 부모 노드
자식 노드 : C는 A의 자식 노드
형제 노드 : D, E는 형제 노드
단말 노드 : 자식 노드가 없는 노드 (혹은 리프 노드), 차수가 0이다. 
비단말 노드 : 단말 노드가 아닌 노드
레벨 : 트리의 각층에 번호를 매기는 것. 보통 루트 노드가 1
높이 : 트리가 가지고 있는 최대 레벨 (위 트리에서는 4)
차수 : 어떤 노드가 가지고 있는 자식 노드의 개수, B는 자식이 D, E이므로 차수가 2이다.
크기 : 자신을 포함한 노드의 개수, B는 D, E 포함해 크기가 3이다. 
트리의 차수 : 트리가 가지고 있는 차수 중 가장 큰 값. 위는 C의 차수가 3이 가장 크므로 트리의 차수 또한 3이다. 

 

3. 이진 트리 (Binary Tree)

 

공집합이거나, 루트와 왼쪽 서브트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진 트리여야한다. 즉 이진트리의 모든 노드는 차수가 2이하여야한다. 노드를 하나도 갖지 않아도 된다. 

 

 

📌 이진 트리의 특징 

n개의 노드를 가진 이진트리는 n-1개의 간선을 가진다. 
높이가 h인 이진트리의 경우, 최소 h개 부터 최대 (2의 h승 -1)개의 노드를 가진다.
포화 이진 트리란 리프노드를 제외한 트리의 각 레벨에 노드가 꽉 차있는 이진트리이다. 높이가 n이라면 (2의 n승-1) 개의 노드를 가진다. 
완전 이진 트리는 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져있는 이진트리이다. 즉 포화 이진트리는 완전 이진 트리이지만, 완전 이진 트리 모두가 포화 이진 트리는 아니다.

 

 

📌 이진 트리의 표현법 

 

📝 배열 표현법 

 

 

노드 i의 부모 노드 인덱스 : i / 2
노드 i의 왼쪽 자식 노드 인덱스 : i * 2
노드 i의 오른쪽 자식 노드 인덱스 : i * 2 + 1

 

📝 링크 표현법

 

 

트리에서 노드가 하나의 구조체로 표현되고, 각 노드의 포인터를 이용하여 노드와 노드를 연결하는 방법이다. java로 노드라는 새로운 자료형을 정의하면 아래와 같은 구조가 나올 것이다. 

class Node {
	Object data;
	Node left, right;
	Node(Object data) {
            this.data = data;
            left = null;
            right = null;
	}
}

 

 

📌 이진 트리의 순회

 

 

전위 순회 : 루트 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리
중위 순회 : 왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리
후위 순회 : 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트 노드
레벨 순회 : 너비 우선 순회라고 함. 레벨 순서대로 순회. 위 3가지는 보통 스택이고, 이 것은 큐로 구현한다. 

 

 

📌 이진 트리의 종류 : 이진 탐색 트리 (BST)

 

이미지 출처 : 나무위키

이진 트리의 탐색을 위한 자료구조이다. 왼쪽 자식 노드는 부모 노드보다 작은 값이, 오른쪽 자식 노드는 부모 노드보다 큰 값이 구성된다. 자식 노드들도 동일한 규칙으로 구성되어 있다. 그래서 어떠한 값을 찾을 때에는 현재 노드 값보다 큰지 작은지만 판별하여 찾으면 빠르게 찾을 수 있다. 

탐색 뿐만 아니라 삽입/삭제에서도 똑같은 방법으로 하면 된다. 그래서 이상적인 경우에는 시간복잡도는 탐색/삽입/삭제 모두 O(㏒N)이다. 다만, 트리가 지나치게 기울어져 있는 경우 최악의 경우에는 O(N)의 시간복잡도가 걸린다. 이 경우에는 선형 탐색과 다를바가 없으므로, 트리의 높이를 균형적으로 만드는 기법들이 개발되었다. 

 

 

📌 이진 트리의 종류 : AVL 트리 

 

이진 탐색 트리에서 균형이 안 맞을 경우를 보완하여 나온 균형 트리이다. 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색트리이다. 항상 균형 트리임이 보장되기 때문에 높이는 항상 ㏒N 이다. 그래서 탐색/삽입/삭제은 평균 및 최악 O(㏒N) 시간복잡도가 걸린다.

균형 인수라고 (오른쪽 서브 트리의 높이 - 왼쪽 서브 트리의 높이) 의 절댓값이 1 이하면 AVL 트리를 만족한다. 위 트리 또한 모든 노드의 균형 인수가 1 이하를 만족하여 AVL 트리이다. 

 

 

📌 이진 트리의 종류 : 레드-블랙 트리 (RB 트리)

 

 

AVL 트리 처럼 이진 탐색 트리의 약점을 보완하기 위해 나온 균형 이진 탐색 트리로, 이상적인 상황이나 최악의 상황에서의 탐색/삽입/삭제가 모두 O(㏒N)이다. 밑에는 레드-블랙 트리가 가지는 조건들이다. 구현이 복잡하지만 최악에서도 일정한 시간복잡도를 가지기 때문에 C++ 에서의 set, Map이, JAVA에서 TreeMap, TreeSet이 이 트리를 바탕으로 구현되었다. 

모든 노드는 레드 아니면 블랙이다.
루트 노드는 블랙이다.
모든 NIL 리프 노드는 블랙이다.
레드 노드의 자식 노드는 언제나 블랙이다.
그러므로 블랙 노드만이 레드 노드의 부모가 될 수 있다.
알기 쉽게 말해서 블랙 노드는 연속으로 나올 수 있지만, 레드 노드는 그렇지 못하다.
임의의 한 노드에서 NIL 리프 노드까지 도달하는 모든 경로에는 NIL 리프 노드를 제외하고 항상 같은 수의 블랙 노드가 있다.

 

 

💡 AVL 트리와 레드-블랙트리 (RB 트리) 

 

  • AVL 트리는 더욱 엄격한 균형을 이루고 있기 때문에 RB 트리보다 더 빠른 탐색이 가능하다. 
  • RB 트리는 상대적으로 느슨한 균형으로 인해 회전이 거의 이루어지지 않기 때문에, AVL트리보다 빠르게 삽입 및 제거 작업을 수행한다. 일반적으로 컴퓨터는 탐색보다는 삽입, 삭제가 더 빈번하게 일어나기 때문에 RB 트리가 더 많이 쓰인다. 
  • RB 트리는 맵, C++의 멀티캐스트, Java treeMap 등 대부분의 언어 라이브러리에서 사용되며, AVL트리는 더 빠른 검색이 필요한 데이터베이스에서 사용된다.

 

출처 : agugu95님 블로그