트리
🌲 정점끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프
⬆️위와 같은 가계도 모양을 생각하면 노드는 가문의 각 구성원이며 왜 상위 노드를 부모 노드, 하위 노드가 자식 노드라고 불리는지 쉽게 이해할 수 있다. 이 예시로 트리 용어들을 일상적으로 비유해 본다면 루트 노드는 가문의 선조, 차수는 각 구성원에서 뻗어나간 가지 수로 몇 명의 자식이 있는지, 깊이는 현재 구성원이 선조로부터 몇 세대 내려왔는지, 높이는 마지막 후손의 깊이이다.
이진 트리
🌲 자식 수가 최대 2개인 트리
이진트리 탐색
- 전위 탐색: 부모 - 좌 - 우
- 중위 탐색: 좌 - 부모 - 우
- 후위 탐색: 좌 - 우 - 부모
이진탐색트리
- 왼쪽 방향에 있는 노드들은 전부 부모 보다 값이 작아야 함
- 우측 방향에 있는 노드들은 전부 부모 보다 값이 커야만 한다
- 삽입
- 삭제
균형잡힌 이진 탐색 트리
삽입, 삭제가 일어나는 순간 루트 노드와 주위에 있는 노드를 회전 등의 작업을 통해 적절하게 조절 → 트리의 높이를 최소화
- 트리 높이를 항상 logN으로 유지할 수 있다
- 삽입, 삭제, 탐색 시간 O(logN)
완전 이진 트리
- 모든 값이 왼쪽에서 순서대로 차 있다
- 모든 노드에 대해 부모 노드가 자신의 자식보다 같거나 큰 or 작은 경우 👉 Heap