[Algorithm] 자료구조 - 트리 (Tree), 이진 트리(Binary tree)

 

트리 (Tree)

---

계층형 자료 구조

트리의 최상위 원소를 루트(root)라고 하고,

나머지 모든 원소는 부모 원소가 있고 0개 이상의 자식 원소를 가진다

자식 노드가 없는 노드는 리프 노드(leaf node)라고 한다

 

 

이진 트리 (Binary tree)

가장 기본적인 트리의 유형

---

각 노드에 왼쪽, 오른쪽 자식이라는 최대 2개의 자식이 있는 트리

이진 탐색 트리 (BST, Binary Search Tree)는 다음 방법으로 노드를 정렬한다

1. 왼쪽 하위 트리의 키(key)가 부모 노드의 키보다 작거나 같다

2. 왼쪽 하위 트리의 키가 부모 노드의 키보다 크다

 

 

이진 탐색 트리의 API와 시간 복잡도

API (Application Programming Interface)

---

- Insert(k) : 트리에 새 원소 k를 삽입

- Delete(k) : 트리에서 원소 k를 삭제

- Search(k) : 트리에서 값이 k인 원소를 검색 (없을 수도 있음)

- FindMax() : 트리에서 가장 큰 값을 찾는다

- FindMin() : 트리에서 가장 작은 값을 찾는다

> 모든 연산은 트리가 균형을 이룰 때는 평균적인 시간 복잡도 O(logn),

  트리가 균형을 이루지 않았을 때는 최악의 시간 복잡도 O(n)

 

 

* 항상 균형을 유지하는 이진 탐색 트리

  : AVL 트리, 레드-블랙 트리(RB-트리) 등

 

* 정렬된 딕셔너리(Dictionary)는 RB-트리를 사용해 구현한다

 

 

 

💡 자료 구조 : codesyun.tistory.com/106

[Algorithm] 자료 구조(Data Structure) 란?