Tree, Binary Tree, BST, AVL Tree

Tree

트리는 비선형 구조로서, 원소들 간에 1:n 관계를 가지고 계층 관계를 가지는 자료구조이다.

상위 원소에서 하위 원소로 내려가면서 확장되는 나무 모양을 하고있다.

용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자식 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

특징

• 트리는 방향성이 있는 비순환 그래프(DAG, Directed Acylic Graph)의 한 종류로서, 사이클이 없다.
• 노드가 N개인 트리는 항상 N - 1개의 간선을 가진다.
• 정점의 개수가 N개인 트리는 항상 N - 1개의 간선을 가진다.

Binary Tree(이진 트리)

모든 노드의 최대 차수가 2인 트리로서, 각 노드는 자식 노드를 최대한 2개까지만 가질 수 있다.

 

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

정렬된 이진 트리로서, 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 크다.

원소를 삽입, 삭제, 검색하는데 효율적인 자료구조이다.

이진 탐색 트리는 균형이 잡혀있지 않을 경우, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다. 이는 탐색하는데 시간이 소요될 수 있으므로 삽입/삭제마다 트리의 구조를 재조정하는 알고리즘을 거칠 수 있는데, 이렇게 스스로 균형을 잡는 이진 탐색 트리를 AVL 트리라고 한다.