자료구조 Tree, BST

Tree

트리로 부르는 이유는 거꾸로 뒤집어 놓은 나무처럼 생겼다고 해서 불려진 이름이다.

 

트리의 특징.

그래프의 한 종류이다.

트리는 계층 모델이다.

트리의 순회는 Pre-oreder, In-order, Post-order로 이루어진다.

트리의 종류는 이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙 등이 있다.

 

트리(Tree)의 구조

• 루트노드(Root Node) : 트리의 맨 위에 있는 노드로,  트리 당 단 하나의 루트만 있다.
• 부모노드(Parent Node) : 루트 노드를 제외하고, 간선으로 연결된 자식 노드 위의 노드를 부모노드라고 부른다.
• 자식노드(Child Node) : 특정 노드 아래로 연결된 노드를 자식 노드라 부른다.
• 단말노드(Leaf Node) : 자식이 없는 노드로, 말단 혹은 잎 노드라고 부른다.
• 간선(edge) : 노드를 연결하는 선 (link,  branch라고부름)
• 형제(siblings ro Brother Node) : 같은 부모를 가진 노드
• 하위트리(Sub-tree): Sub-tree는 노드의 하위 항목을 나타낸다.
• 노드의 깊이(Depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선 수
• 노드의 레벨(Level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수

 

이진 트리

 

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

노드의 왼쪽 자식은 부모 노드보다 작은 값을 가져야하고, 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가져야한다.

 

 

완전 이진 트리

 

마지막 레벨을 제외한 트리의 모든 높이에 노드가 꽉 차 있는 이진 트리이다. 

마지막 레벨은 전부 차 있지 않아도 되지만, 왼쪽에서 오른 쪽으로 채워져 있어야한다.

가장 오른 쪽의 잎 노드가 제거 되어있어야 한다.

배열을 사용해 효율적인 표현이 가능하다.

 

전 이진 트리

 

모든 노드가 0개 또는 2개의 자식을 갖는 트리

 

포화이진 트리

 

전 이진 트리 이면서 완전 이진 트리인 경우

모든 노드가 두개의 자식 노드를 가진다.

모든 말단 노드가 동일한 깊이, 레벨을 가진다.