트리
특징
- 비선형 구조
- 단방향 그래프
활용
- 파일 시스템(컴퓨터 디렉토리 구조)
- 모든 폴더는
/(루트 폴더)에서 시작하여, 가지를 뻗어나온다.
- 모든 폴더는
- 월드컵 토너먼트 대진표
- 가계도(족보), 조직도
구조
- 각 데이터를 노드(Node)라고 함
- 맨 위에 있는 노드를 루트(Root)라고 함
- 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계이다.
- 위에 있는 노드를 부모 노드(Parent Node), 아래에 있는 노드를 자식 노드(Child Parent)라고 한다.
- 자식이 없는 노드를 리프 노드(Leaf Node)라고 함 (트리 구조의 끝 지점)
출처: 파이썬 알고리즘 인터뷰, https://namu.wiki/jump/k84rEL9gLARSrcoJojPvtBnQERJkWOhPLU9uXrEqH8Qv69PXoNvaQPrgmMMZeQG1
저작자: 책만 출판사
이 이미지는 크리에이티브 커먼즈 저작자표시-비영리 2.0 대한민국 라이선스로 배포됩니다.
- 깊이: 루트에서 특정 노드까지의 거리(루트는 깊이가 0이므로 0부터 count한다.)
- 레벨: 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현하고 이들을 형제 노드(Sibling Node)라고 한다.
- 깊이는 0부터 시작하지만, 레벨은 1부터 시작한다.
- 높이: 리프 노드를 기준으로 루트까지의 높이
- 부모 노드는 자식 노드의
가장 높은 height + 1을 높이로 갖는다. - 그림의 H, I, E, F, G는 높이가 0이다.
- D는 높이가 1, E는 높이가 0이고, 이 둘의 부모인 B는 높이가 2이다.(D의 height+1)
- 부모 노드는 자식 노드의
- 서브 트리: 전체 트리 내에서 트리 구조를 갖춘 작은 트리
이진 트리
-
자식 노드가 최대 2개인 트리
-
완전 이진 트리(Complete binary tree): 마지막 레벨을 제외한 모든 노드는 가득 차 있으며, 마지막 레벨은 전부 차 있지 않아도 되지만 왼쪽부터 채워져 있는 트리
-
정 이진 트리(Full binary tree): 자식 노드가 아예 없거나, 두 개인 트리. 자식을 하나만 가진 노드가 없어야 한다.
-
포화 이진 트리(Perfect binary tree): 완벽한 피라미드 형태의 이진 트리, 빈 공간 없이 모든 노드가 자식을 2개씩 갖고 있는 트리
-
균형 이진 트리(Balanced Binary Tree): 높이 균형이 맞춰진 이진 트리
-
비균형 이진 트리(Unbalanced Binary Tree): 밸런스가 맞지 않은 트리
-
편향 이진 트리(Skewed Binary Tree): 한 쪽으로 지나치게 치우친 트리
이진 탐색 트리(Binary Search Tree, BST)
이진 탐색 트리는 이진 트리가 효율적인 탐색을 위해 발전된 구조이다!
- 왼쪽 자식의 값이 부모보다 작고, 오른쪽 자식의 값이 부모보다 크다.
- 중위 순회를 통해서 트리의 값을 오름차순으로 얻을 수 있다.
트리 순회
= 트리의 모든 노드를 한 번씩 방문하는 것
순회 시에는 항상 왼쪽에서 오른쪽으로 순회한다!
"root를 언제 순회하는가"에 따라 이름을 붙였다.
root를 가장 먼저 순회하면 전위 순회, 마지막에 순회하면 후위 순회, 중간에 순회하면 중위 순회
- 전위 순회: root -> L -> R
- 중위 순회: L -> root -> R
- 후위 순회: L -> R -> root
균형 이진 탐색 트리
이진 탐색 트리에 새로운 노드가 삽입될 때, 부모 노드보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 추가된다.
BST는 높이가 커질수록 검색에 불리해지는데, 최악의 경우에는 편향 이진 트리가 된다.
BST의 효율을 높이기 위해서는 BST의 높이가 계속 커지는 것을 막아야한다. 즉 Unbalanced Binary Tree를 Balanced Binary Tree로 바꿔주는 작업을 해야 한다.
이때 나오게 된 것이 균형 이진 탐색 트리(Balanced Binary Search Tree)이고, 균형 이진 탐색 트리는 노드가 삽입/삭제될 때, 스스로 구조를 변경하여 높이를 최소한으로 유지하는 트리이다.
이런 균형 이진 탐색 트리에는 여러가지가 있는데 대표적으로 AVL 트리, B 트리가 있다.
AVL 트리
문제점
- 균형 유지로 인해 일정 수준의 검색 성능을 보장하는 대신
자료의 개수가 증가하여 트리의 높이가 계속해서 높아진다는 문제점이 있다. - 자료의 추가나 삭제가 빈번하게 발생하면 균형유지에 소모되는 시간이 많아져 힘들어진다.
=> 이 문제를 해결한 트리가 다원탐색트리(Multiway Search Tree), 그중에서도 B-Tree이다.
