Tree

트리는 노드로 이루어진 데이터 구조이다.
노드들 사이에 부모와 자식 관계를 가진 가지가 있다.
한가지 에서 여러개의 노드 0~n개의 노드를 가질 수 있다. 각 노드는 한개 이상의 다른 노드를 가질 수 있다는 점에서 연결리스트와는 차이가 있다.

선형 구조(linked-list)에서도 보면 트리 구조에 속하므로 트리로 볼수 있다.

트리는 부모-자식 관계에서 자식 노드만 가리킬 수 있다.

아래는 트리라고 볼 수 없는 구조이다.

이런 것들은 그래프라고 볼 수 있다.

트리는 하나의 루트 노드로부터 자식노드만 가리킬 수 있으며, 루트에서 멀어지는 방향으로 연결된 노드여야 한다.

트리사용의 예

• DOM 객체
• 유닉스, 윈도우 폴더구조
• 네트워크 라우팅, JSON, AI 머신러닝 등
• n-queen에서도 경우의 수를 트리 구조로 보여주었다.

트리의 구조, 용어

• 노드: 트리를 구성하는 기본 원소
• 루트: 트리 구조 최상단의 위한 트리의 시작노드
• 부모노드, 자식노드, 형제노드 : 상대적인 위치의 노드
• 리프노드: 자식이 없는 단말 노드
• 간선: 노드들을 잇는 선

• 길이: 출발 노드에서 도착노드까지 거치는 간선의 개수
• 경로: 한노드에서 다른 노드까지 이르는 길 사이의 노드들의 순서
• 깊이: 루트경로까지의 길이
• 레벨: 루트노드부터 노드까지 연결된 간선 수의 합
• 차수: 각 노드의 자식 개수
• 크기: 노드의 개수
• 트리의 차수: 트리의 최대 차수 max(deg1,deg2...degN)
• 너비: 가장 많은 노드를 갖고 있는 레벨의 크기
• 포레스트: 서로 독립적인 트리들의 모임

이진 탐색 트리

이진트리

각 노드가 최대 두개의 자식

이진 탐색 트리

부모노드보다 작은 요소를 가진 노드는 왼쪽 자식 노드에 위치한다. 큰 요서는 오른쪽에 자식 노드에 위치한다 >> 이진타색 트리

이진탐색 트리의 시간 복잡도

모두 잘 정렬 되어있는 경우 O(log n)의 시간 복잡도를 가진다.

하지만 이를 보장할 수는 없다.
한쪽으로 치우쳐진 트리가 있다면 최악의 경우 O(n)의 시간 복잡도를 가진다.