Tree

트리

🌲 정점끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프

원소의 구성을 정말 나무처럼 표현한 예시로 영화 해리포터 속에서 나왔던 시리우스 블랙의 가계도가 생각났다. 자료구조의 트리는 나무가 거꾸로 있는 형태이므로 가문의 선조가 가장 위에 있도록 원본 이미지를 회전했다.

⬆️위와 같은 가계도 모양을 생각하면 노드는 가문의 각 구성원이며 왜 상위 노드를 부모 노드, 하위 노드가 자식 노드라고 불리는지 쉽게 이해할 수 있다. 이 예시로 트리 용어들을 일상적으로 비유해 본다면 루트 노드는 가문의 선조, 차수는 각 구성원에서 뻗어나간 가지 수로 몇 명의 자식이 있는지, 깊이는 현재 구성원이 선조로부터 몇 세대 내려왔는지, 높이는 마지막 후손의 깊이이다.

이진 트리

🌲 자식 수가 최대 2개인 트리

이진트리 탐색

• 전위 탐색: 부모 - 좌 - 우
• 중위 탐색: 좌 - 부모 - 우
• 후위 탐색: 좌 - 우 - 부모

이진탐색트리

• 왼쪽 방향에 있는 노드들은 전부 부모 보다 값이 작아야 함
• 우측 방향에 있는 노드들은 전부 부모 보다 값이 커야만 한다
• 삽입
• 삭제

균형잡힌 이진 탐색 트리

삽입, 삭제가 일어나는 순간 루트 노드와 주위에 있는 노드를 회전 등의 작업을 통해 적절하게 조절 → 트리의 높이를 최소화

• 트리 높이를 항상 logN으로 유지할 수 있다
• 삽입, 삭제, 탐색 시간 O(logN)

완전 이진 트리

• 모든 값이 왼쪽에서 순서대로 차 있다
• 모든 노드에 대해 부모 노드가 자신의 자식보다 같거나 큰 or 작은 경우 👉 Heap