Tree?
트리는 계층자료를 표현하기 좋은 계층형 자료구조이다.
꼭 나무를 거꾸로 돌려놓은 모습과 같아서 트리 라고 지었다고 한다.
트리를 공부하기전에 트리의 용어를 먼저 알고 있어야한다.
✔️ 하단의 그림과 함께 보세요
루트 노드(root node) : 부모가 없는 최상위 노드. 트리는 하나의 루트 노드만을 가진다. (A)
단말 노드(leaf node) : 자식이 없는 노드이다. (E),(K),(L),(G),(H),(I),(J)
차수 (degree) : 노드의 자식노드갯수 예를들면 A의 차수는 3 B의 차수는 2
깊이 (depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 E는 2, K는 3
높이 (height) : 4
Tree 종류
트리의 종류는 다양하다. 그 중 대표적인
이진트리, 완전트리, 포화트리, 이진탐색트리에대해서 알아보도록 하려고 한다.
🌱 이진트리
각 노드의 두개의 자식으로만 이루어진 트리를 이진트리라고 한다.
🌱 완전이진트리
🌱 포화이진트리
노드가 꽉 차있는 것
(2^k)-1을 한다면 총 노드의 갯수가 나온다.
k는 트리의 높이이다.
🌱 이진탐색트리 ⭐️
이진탐색트리는 원하는 값을 찾을 때 효율적인 방식으로 빠르게 찾을 수 있다.
규칙을 먼저 익히자.
1. Parent Node > left Children Node
2. Parent Node < right Children Node
예를들어 내가 찾고자하는 숫자는 5일 때 루트에서부터 시작을 했을 때
3은 왼쪽노드 8은 오른쪽노드 왼쪽노드부터 탐색을 시작한다.
현재 parent Node가 3이면 왼쪽노드는 3보다 작을 것이니 탐색 X
오른쪽노드는 3이상이니까 5를 바로 찾을 수 있다.
이렇게 탐색하지 않아도될 곳은 탐색하지 않아도 되니 시간복잡도를 높일 수 있다고 볼 수 있다.
