[목차]
- Tree
- Binary Tree
- Binary Search Tree
- B-Tree
- RB-Tree
[면접 질문 list]
- 트리 자료구조에 대해서 설명
- 트리와 그래프의 차이?
- 트리의 순회방식 종류
- 이진트리란?
- BST란?
- BST worst case 해결방법은?
- BST 성능 개선 방법
- RB Tree란?
- RB Tree 작동 원리는?
- RB Tree 삽입/삭제 알고리즘 구현은?
- RB Tree 사용 시 주의해야 할 점
- RB Tree 사용 예시
- RB Tree 장점
- AVL 트리란?
- 검색 자동완성을 어떻게 구현할 수 있는가?
Tree
❓루트가 없는 트리도 있는가?
yes. 루트가 없는 free tree가 존재
❓루트가 있고 없고의 차이는 뭐고, 왜 루트가 있는 트리를 많이 사용하는 것일까?
루트가 있는 트리는 부모-자식 관계가 명확하다.
레벨이나 깊이의 개념이 있다. (계층 구조 존재) ⇒ 파일 시스템 등 많은 데이터들이 계층 구조를 가지고 있기에, 이런 데이터를 표현하기 적합하다.
모든 노드가 루트로부터 유일한 경로를 가진다. ⇒ 탐색이 효율적이다. 또한 부모에서 자식으로 단방향 참조만 필요하므로 메모리 사용이 효율적이다.
❓트리란 무엇인가?
#계층구조 #노드 #간선 #루트 #부모-자식 관계 #리프 #사이클 없음 #연결성
트리란 계층 구조를 가진 비선형 자료구조이다. 트리는 노드를 가지며, 노드는 객체로 표현된다. 각 노드는 간선으로 연결되어 있으며, 0개 이상의 자식 노드를 가질 수 있다.
트리의 중요한 특성은 사이클이 없다는 점이며, 모든 노드는 서로 연결되어 있어야 한다.
이러한 특성들로 인해 트리는 계층적 데이터를 표현하고 처리하는 데 매우 효과적인 자료구조이다.
❓트리와 그래프의 차이점?
- 사이클: 트리는 사이클이 없지만, 그래프는 사이클을 가질 수 있다.
- 연결성: 트리는 항상 모든 노드가 연결되어 있지만, 그래프는 연결되지 않을 수 있다.
- 엣지 수: n개의 노드를 가진 트리의 엣지 수는 n-1 개로 항상 정해져 있다.
- 루트: 그래프에는 루트 개념이 없다
- 부모 자식 관계: 트리는 관계가 명확하고, 그래프는 이런 개념이 없음
모든 트리는 그래프이지만, 모든 그래프가 트리인 것은 아니다.
Binary Tree
이진트리는 각 노드가 최대 두개의 자식 노드를 갖는 트리 구조이며, 보통 왼쪽 자식과 오른쪽 자식으로 구분된다. 이때 자식 노드는 없을 수도 있고, 하나만 있을 수도 있고, 두 개 있을 수도 있다. 같은 루트에 같은 자식 노드를 가지고 있더라도, 그 노드의 위치가 다르면 서로 다른 트리로 구분된다.
주요 특징으로는 서브트리가 존재하며, 모든 노드의 차수가 최대 2이다. 또한 이진트리는 선형자료구조인 1차원 배열로 표현할 수 있다는 특징을 가진다.
Binary Search Tree
- 이진검색트리란?
이진 트리 형태를 가지며, 각 노드를 객체로 하는 자료구조다. key, 부속 데이터, left, right, p 필드를 가진다.
- 이진 검색트리 특징
모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다. 또한 자녀 노드는 최대 두 개까지 가질 수 있다.
- 값을 정렬된 순서로 출력하기 위해 이진 검색 트리를 순회하는 방법
- 중위 트리 순회 (inorder tree walk)
- 전위 트리 순회 (preorder tree walk)
- 후위 트리 순회(postorder tree walk)
- 이진 검색 트리에서 하나의 값을 검색하는 방법
- 최대 원소 또는 최소 원소를 찾는 방법
- 한 원소의 직전원소 또는 직후 원소를 찾는 방법
- 삽입/삭제를 수행하는 방법
B-Tree
- 개념
이진 트리를 확장한 것으로, 하나의 노드는 자식 노드를 2개 이상 가질 수 있다. 또한 이러한 자료구조는 데이터 베이스를 관리하는 데 특히 유용하다.
- 특징
자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장한다.
부모 노드의 key들을 오름차순으로 정렬한다.
정렬된 순서에 따라 자녀 노드들의 Key 값의 범위가 결정된다.
추가는 항상 leaf 노드에 한다.
노드가 넘치면 가운데 Key를 기준으로 좌우 key들은 분할하고 가운데 Key는 승진한다.
- 파라미터
M: 각 노드의 최대 자녀 노드 수
M-1: 각 노드의 최대 key 수
⌈M/2⌉: 각 노드의 최소 자녀 노드 수
⌈M/2⌉ - 1 : 각 노드의 최소 key 수
RB-Tree
- 개념
이진 검색 트리의 최선의 시간 복잡도는 O(logn)이고, 최악의 시간 복잡도는 O(n)인데, 최악의 경우에도 빠른 실행 속도(O(logn))를 보장할 수 있도록 이진 검색 트리를 변형한 것이 RB Tree 이다.
RB Tree는 트기가 ‘균형을 이루도록’ 고안된 검색 트리 구조이다.
- 특징
레드 블랙 트리는 다음과 같은 특성을 만족하는 이진 검색 트리이다.
- 모든 노드는 적색이거나 흑색이다.
- 루트는 흑색이다.
- 모든 리프는 흑색이다.
- 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
- 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.