[자료구조] Tree & Binary Search Tree

1. 트리(Tree) 

: 트리(Tree)는 계층적인 자료를 표현하는데 이용되는 자료구조이며,컴퓨터의 directory 를 예시로 들 수 있다. 

실제 나무를 거꾸로 한 것과 같은 모양을 하고 있어 "Tree" 라고 부른다. 

아래사진은 내방식으로 정리한 그림이다. 

 

 

루트노드 (root node) : 부모가 없는 최상위 노드 

단말노드 (leaf node) :자식이 없는 노드

크기 (size) : 트리에 포함된 모든 노드의 개수

깊이 (depth) : 루트 노드로부터의 거리 

높이 (height) : 깊이(depth) 중 최댓값, 즉 루트 노드로부터 가장 멀리있는 노드.

차수 (degree) : 각 노드의 간선 개수 

 

2. 이진트리(Binary Tree)

트리를 구성하는 노드의 branch는 0개, 1개, 2개, 3개 등 여러개가 될 수 있지만, 이진트리는 모든 노드가 최대 2개의 서브트리를 가지고있는 트리다. 서브트리 또한 모두 이진트리이다. 즉 branch가 최대 2개인 노드로만 구성되는 트리라는 뜻이다. 

 

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

 

 

이진탐색트리(BST)

이진 탐색 트리는 위의 이진트리에 조건이 더해진 것이다. 

 

이진탐색트리는 모든 노드가 왼쪽 자식 노드 < 부모노드 < 오른쪽 자식 노드의 순서대로 값이 크다. 

 

또한, 부모노드를 중심으로 작은 값은 왼쪽 자식 노드에 큰 값은 오른쪽 자식 노드에 존재해야 하므로, 이진 탐색 트리의 모든 노드이 데이터 값은 중복되는 값이 존재하면 안되낟. 즉, 데이터 값은 유일해야한다.