하나 이상의 데이터에 무방향으로 연결된 자료구조, 나무가 뒤집어진 모양이라 트리라 칭함
깊이 depth : 루트로부터 해당 노드까지의 깊이
❗️root의 깊이 : 0
레벨 level : 같은 깊이의 노드들
❗️같은 레벨노드 ➡️ 형제노드
여러 점들의 연결 관계를 표현한 자료구조
자식노드가 최대 두 개인 트리(이진트리)를 검색이 편리하도록 만든 자료구조
부모의 작은 노드는 왼쪽, 큰 노드는 오른쪽에 위치
➡️ 탐색시,
✔️ 해당 노드의 값이 현재 노드의 값보다 작다면 왼쪽 자식노드 탐색
✔️ 해당 노드의 값이 현재 노드의 값보다 크다면 오른쪽 자식노드 탐색
정 이진트리(full binary tree) : 각 노드가 0개 or 2개의 자식 노드를 가지는 경우
완전 이진트리(complete binary tree) : 마지막 레벨이 모두 채워지지 않았지만, 왼쪽부터 채워져 있는 경우
포화 이진트리(perfect binary tree) : 모든 레벨이 채워져있는 경우