[자료구조] 트리(Tree)에 대해서 알아보자.

오늘은 트리에 대해서 알아보는 시간을 갖도록 하겠다.

 

Tree

 

(0) 배경지식

 * Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)

 * Root Node : 트리 맨 위에 노드

 * Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄

 * Parent Node : 어떤 노드의 다음 레벨에 연결된 노드

 * Child Node : 어떤 노드의 상위 레벨에 연결된 노드

 * Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드

 * Sibling (Brother Node) : 동일한 Parent Node를 가진 노드

 * Depth : 트리에서 Node가 가질 수 있는 최대 Level

 

 

트리

(1) 정의

 - Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다.

 - 비선형 계층적 자료구조이다.

 

 

(2) 특징

 - 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다.

 - 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조이다.

 - 트리내에 또 다른 트리가 있는 재귀적 자료구조이다.

 - 단순 순환(Loop)을 갖지 않고, 연결된 무방향 그래프 구조이다.

 - 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖는다.

 - 노드가 n개인 트리는 항상 n-1개의 간선(edge)를 갖는다.

 

 

(3) 종류

 1) 이진 트리 (Binary Tree)

  - 각 노드의 차수(자식노드)가 2 이하인 트리

 

 2) 이진 탐색 트리 (Binary Search Tree, BST)

  - 순서화된 이진 트리

  - 노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야 하며 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가져야 함.

 

 3) m원 탐색 트리 (M-way Search Tree)

  - 최대 m개의 서브 트리를 갖는 탐색 트리

  - 이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용함.

 

 4) 균형 트리 (Balanced Tree, B-Tree)

  - m원 탐색 트리에서 높이 균형을 유지하는 트리

  - height-balanced m-way tree라고도 함.

 

 

(4) 이진 탐색 트리 (Binary Search Tree)

 - 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다.

 - 빠른 데이터 탐색을 위해 주로 사용된다.

 

 

 

 

(5) 이진 탐색 트리의 시간 복잡도

 - depth (트리의 높이)를 h로 표기한다면, O(h)

 - n개의 노드를 가진다면, h = 𝑙𝑜𝑔2𝑛에 가까우므로, 시간 복잡도(평균)는 𝑂(𝑙𝑜𝑔𝑛)

 - 아래 그림과 같이 구성되어 있을 경우, 최악의 경우는 링크드 리스트등과 동일한 성능을 보여줌 𝑂(𝑛)

 

References

[자료구조] 트리 (Tree)