[자료구조] 트리 (Tree) - 트리의 정의와 종류 (이진트리 등)

트리 (Tree)란?

트리는 노드로 구성된 자료구조이다.

 

- 트리는 루트노드(root node)를 가진다.

- 루트노드는 0개 이상의 자식노드(child nodes)를 가진다.

- 각 자식노드 또한 0개 이상의 자식노드를 가진다.

 

- 트리는 cycle을 가질 수 없다.

- 노드는 특정한 순서로 있을수도 없을수도 있다.

- 노드는 어떤 데이터 타입도 값으로 가질 수 있다.

- 노드는 부모 노드로 가는 링크를 가지고 있을수도 없을수도 있다.

 

 

Node 예시

class Node:
  def __init__(self, data):
    self.data = data
    self.children = []

 

Tree 예시

class Tree:
  def __init__(self):
    self.root = None

 

---

 

트리의 타입

 

- 이진 트리 (Binary Trees)

이진 트리란 각 노드가 자식노드를 최대 두 개까지 가지는 트리이다.

 

자식노드를 가지지 않는 노드를 리프노드(leaf node)라고 한다.

 

 

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

이진 탐색 트리란 모든 노드가 특정한 순서에 의해 위치하는 이진 트리를 말한다.

 

노드 n을 중심으로 왼쪽의 후손은 n보다 값이 작고, 오른쪽 후손은 n보다 값이 크다.

(왼쪽 < n < 오른쪽)

 

 

- 균형 트리 (Balanced Tree)

균형트리라해서 반드시 왼쪽과 오른쪽의 서브트리가 같은 사이즈여야하는 것은 아니다.

삽입과 탐색에서 O(log n) 시간을 충족할 수 있다면 균형 트리라 할 수 있다.

 

예: 레드블랙트리, AVL 트리

 

 

- 완전 이진 트리 (Complete Binary Trees)

 

트리의 모든 레벨이 가득 차야한다. 마지막 레벨은 가득차지 않아도 괜찮다. 다만 왼쪽에서 오른쪽 순서로는 차있어야한다.

 

 

- 정 이진 트리 (Fully Binary Trees)

각 노드가 0개 혹은 2개의 자식 노드를 가지고 있는 이진 트리를 말한다.

 

 

- 포화 이진 트리 (Perfect Binary Trees)

리프 노드를 제외한 내부 노드(internal node)가 2개의 자식 노드를 가지는 이진 트리를 말한다.

 

Perfect Binary Tree는 2^k - 1개의 노드를 가진다.

 

---

출처

- Cracking the Coding Interview - Chapter 4. Trees and Graphs