트리

트리는 노드로 이루어진 자료구조를 말한다.
트리 자료구조는 정말 트리처럼 꼭대기의 별부터 밑으로 점점 커지는 모양이다. 조직도 같이 계층형 구조로 이루어져 있다.

개념

• 트리는 반드시 하나의 root 노드를 가진다.(시작점)

• root 노드는 0개 이상의 자식 노드를 가지고 있다.(root 노드만 있어도 된다는 이야기)

• 자식 노드 또한 0개 이상의 자식 노드를 가질 수 있다.(반복)

• 트리는 노드와 노드들을 연결하는 간선(edge)로 구성된다.

• 트리는 사이클(cycle)이 없는 비선형 구조다.(계층적 구조)

• 노드는 특정 순서로 나열 될 수도 아닐 수도 있다.

용어

• 루트 노드(root node) : 부모가 없는 노드.

• 단말 도느(leaf node) : 자식이 없는 노드.

• 내부노드(internal node) : 단말 노드가 아닌 노드.

• 간선(edge) : 노드를 연결 하는 선(link, branch)

• 형제(sibling) : 같은 부모를 가진 노드.(형제 끼린 레벨이 같음)

• 노드 크기(size) : 자신을 포함한 모든 자손 노드 개수.

• 노드 깊이(depth) : 루트부터 특정 노드 까지 거쳐야하는 간선의 수.

• 노드 레벨(level) : 특정 깊이를 가진 노드의 집합.

• 노드 차수(degree) : 하위 트리 갯수. (A차수 : 2, E차수 :1)

• 트리 차수(degree of tree) : 트리의 최대 차수.

• 트리 높이(hegiht) : 루트 노드에서 가장 아래 있는 노드의 깊이.

특징

• 계층형 모델이다.

• 방향성이 있는 비순환 그래프.

• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.(-1은 루트임)

• 노드에서 노드로 가는 경로는 유일하다.

• 루트 노드는 반드시 한 개, 모든 자식 노드도 하나의 부모 노드만 가짐.

트리 종류

이진 트리(Binary tree)

각 노드가 최대 2개의 자식을 가지고 있는 트리. = 노드 차수가 2이하.

이진 트리 순회

• 중위 순회(in-order traversal) : 왼쪽 가지 -> 현재 노드 ->오른쪽 가지
  
• 전위 순회(pre-order traversal) : 현재노드 -> 왼쪽 가지 -> 오른쪽 가지
  
• 후위 순회(post-order traversal) : 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드
  

개인적인 생각 - 순회의 특징은 항상 왼쪽 ->오른쪽 순서이며 현재 노드의 탐색 위치에 따라 달라진다.

이진 탐색 트리

이진 트리 구조 기반으로 자료의 검색,삭제,삽입에 효율적이게 한 트리 자료구조.

• 왼쪽 자식 노드는 항상 부모보다 작고 오른쪽 자식 노드는 항상 부모보다 크다.
• 모든 노드는 중복된 값을 가지지 않는다.

예시 [28, 21, 15, 14, 32, 25, 18, 11, 30, 19]를 이진 탐색 트리로.
위와 같은 형태로 만들면 효율적인 탐색을 할 수 있다. 원하는 값을 찾을 때 현재 노드 기준으로 작으면 왼쪽 크면 오른쪽으로 가면 되기 때문이다.

완전 이진 트리(Complete)

• 마지막 레벨을 제외하고 모든 노드가 꽉차있는 트리.

• 마지막 레벨은 꽉 차 있지 않아도 되지만 왼쪽이 채워져 있어야 한다.

• 마지막 레벨의 노드의 총 갯수는 (1 ~ 2h-1)개다.

전 이진 트리(Full)

• 모든 노드가 0개 또는 2개의 자식 노드를 가짐.

포화 이진 트리(Perfect)

• 전 이진 트리이면서 완전 이진 트리인 경우.(그냥 꽉 찼다는 얘기)

• 모든 단말 노드는 같은 레벨에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다.

• 단말 노드를 제외하고 2개의 자식 노드를 가진다.

• 노드의 갯수가 정확이 (2^K - 1)여야 한다. K는 트리 높이.

한 줄평 : 트리는 리스트나 배열로 구현 할 수 있다.

참고 -
http://www.ktword.co.kr/test/view/view.php?no=4726
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%AC-Tree#%ED%8E%B8%ED%96%A5-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-skewed-binary-tree