❗️ 계속해서 업데이트 될 예정...
잘못된 부분이 있다면 알려주세요 🙏
트리
트리
가계도나 회사의 조직도처럼 위아래 개념을 컴퓨터로 표현한 자료구조이며, 루트 값과 부모-자식 관계의 서브트리로 구성된다.
- 차수(Degree) : 자식 노드의 개수
- 크기(Size) : 자신을 포함한 모든 자식 노드 개수
- 높이(Height) : 현재 위치에서 리프까지의 거리
- 깊이(Depth) : 루트에서 현재 노드까지의 거리
트리와 그래프의 차이
트리는 순환 구조를 갖지 않는 그래프. 즉, 그래프의 일종임.
또한 트리는 부모 노드가 자식 노드를 가리키는 단방향 구조.
오직, 하나의 부모 노드만 가질 수 있음. 물론, 루트 또한 하나여야 함.
이진 트리(Binary Tree)
모든 노드의 차수가 2 이하일때 이진 트리라고 부름.
- 정 이진 트리(Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
- 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있음.
- 포화 이진 트리(Perfect Binary Tree) : 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.
이진 탐색 트리(BST)
정렬된 트리로, 노드의 왼쪽 트리는 그 노드의 값보다 작은 값들로 되어있고, 오른쪽 트리는 그 노드의 값과 같거나 큰 값들로 되어있다.
그래서 탐색 시간 복잡도는 O(logn)이다.
자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)
왼쪽 사진과 같이 이진 트리이지만 균형이 많이 깨지면 연결 리스트와 다르지 않다. 그래서 모두 탐색해야하므로 효율적이지 못하다. 이런 트리의 균형을 맞춰 줄 필요가 있어 고안해낸 것이 자가 균형 이진 탐색 트리다.
삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리.
트리 순회
그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정.
그래프 순회와 마찬가지로 DFS 또는 BFS로 탐색함.
DFS는 노드의 방문 순서에 따라 3가지 방식으로 구분됨.
- 전위(Pre-Order)순회(NLP)
현재(N) 노드 -> 왼쪽 -> 오른쪽 - 중위(In-Order)순회(LNR)
왼쪽(L) 노드 -> 현재 -> 오른쪽 - 후위(Post-Order)순회(LRN)
왼쪽(L) 노드 -> 오른쪽 -> 왼쪽
