[자료구조] Tree 와 Binary Search Tree(BST)

Tree란?

 

정의

비선형적 자료구조

부모노드와 자식노드의 관계가 형성되는 자료구조

 

특징

하나의 root노드가 있고 노드들은 여러개의 자식노드를 가진다

그래프 형태로 계층적 구조를 표현한다

 

 

용어정리

• root : 시작 노드. 최대 하나의 root노드를 가짐
• edge : 부모 노드와 자식 노드를 잇는 선
• sibling : 같은 부모를 갖는 자식 노드들
• leaf : 자식이 없는 노드
• height : 해당 노드에서 부터 가장 깊은 노드까지 경로의 길이(트리 노드들간의 경로 중 가장 큰 값)
• depth : root 노드부터 특정 노드까지의 경로 길이(ex) root - depth 0, root -> 첫번째 자식 노드 - depth 1)

 

BST (Binary Search Tree)

 

정의

아래와 같은 특징을 갖는 이진 트리

 

특징

1. 각 노드에는 값이 있다.
2. 각 노드는 최대 두 개의 자식 노드를 갖는다.
3. 노드의 왼쪽 자식 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 구성되어 있다.
4. 노드의 오른쪽 자식 트리에는 그 노드의 값보다 같거나 큰 값들을 지닌 노드들로 구성되어 있다.