[자료구조] 트리, 이진 트리, 이진 탐색 트리
트리 (Tree), 이진트리 (Binary Tree), 이진 탐색 트리 (Binary Search Tree)
트리
특징
- 비선형 자료구조
- 값을 가진 노드와 간선으로 이루어짐.
- 최상위 노드인 루트 노드가 있음.
- 모든 노드는 0개 이상의 자식 노드를 갖고 있음.
- 부모-자식 관계로 부름.
- 트리에는 사이클이 존재할 수 없음. (사이클이 있는 것은 그래프)
- 루트에서 한 노드로 가는 경로는 유일함.
이진트리
자식 노드를 최대 2개까지 가질 수 있는 트리 구조.
용어
- 루트 노드 : 부모 노드가 없는 최상단 노드. 트리에서 오직 하나만 존재.
- 간선 : 부모 노드와 자식 노드를 연결하는 선
- 말단 노드 (잎 노드) : 자식 노드가 없는 마지막 노드. 말단 노드는 여러 개 존재할 수 있음.
- 깊이 : 루트 노드부터 어느 한 노드까지의 거리. 위 → 아래
- 높이 : 가장 깊은 노드부터 어느 한 노드까지의 거리. 아래 → 위
종류
- Skewed Binary Tree
- Full Binary Tree
정 이진트리는 모든 노드들이 자식 노드를 0개 또는 2개 가지고 있는 트리를 말한다. 반대로 말하면 자식 노드를 1개만 가지고 있는 노드가 없는 트리 구조라고 할 수 있다.
- Complete Binary Tree
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 모든 노드는 왼쪽부터 채워져 있는 트리 구조.
- Perfect Binary Tree
마지막 레벨을 제외한 모든 노드가 두 개의 자식을 가지는 트리 구조.
순회
- 전위 순회 (pre-order)
각 루트를 순차적으로 먼저 방문하는 방식
(루트 → 왼쪽 자식 → 오른쪽 자식)
1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14
- 중위 순회 (in-order)
왼쪽 하위 트리부터 방문 후 루트를 방문하는 방식
(왼쪽 자식 → 루트 → 오른쪽 자식)
8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 → 14 → 7
- 후위 순회
왼쪽 하위 트리부터 하위를 모두 방문 후 루트를 방문
(왼쪽 자식 → 오른쪽 자식 → 루트)
8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1
- 레벨 순회
루트부터 계층 별로 방문
1 → 2 → 3 → 4 → 5 → 6 → …
이진 탐색 트리(Binary Search Tree)
목적
이진 탐색 + 연결 리스트
이진 탐색 : 탐색에 소요되는 시간 복잡도 O(logN) 삽입, 삭제 불가능
연결 리스트 : 삽입, 삭제 시간 복잡도 O(1) 탐색하는 시간 복잡도 O(N)
특징
- 각 노드는 최대 2개의 자식을 가짐.
- 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼.
- 중복된 노드가 없어야 함. 이진 탐색 트리는 검색이 목적인 자료구조이다. 노드에 개수를 갖도록 처리하는 것이 더 빠르다.
- 중복이 많은 경우 검색 속도가 저하되기 때문이다.
- 중복이 없어야 하는 이유
동작 원리
추가
추가하려는 값을 노드와 비교하여 작으면 왼쪽 노드에 크면 오른쪽 노드에 추가한다.
이미 그 자리에 값이 있으면 같은 원리로 빈자리가 있을 때까지 반복한다.
검색
마찬가지로 찾는 값이 노드보다 작으면 왼쪽, 크면 오른쪽 노드를 검색하여 값을 찾을 때까지 반복한다.
