값을 가지고 있는 트리의 구성 요소
모든 노드는 0개 이상의 자식 노드(child)를 가지고 있으며, 그런 관계를 자식-부모 관계라고 한다
노드의 종류는 아래와 같이 3가지로 분류할 수 있다
- 루트 노드 (Root Node) : 트리 구조에서 최상위에 있는 노드
- 단말 노드 (Terminal Node, Leaf Node) : 하위에 다른 노드가 연결되어 있지 않은 노드
- 비단말 노드 (Internal Node, 내부 노드) : 단말 노드를 제외한 모든 노드
트리를구성하기 위해 노드와 노드를 연결하는 선
각 층별로 숫자를 매겨 트리의 레벨로 사용
루트 노트의 레벨은 0이다
트리의 최고 레벨을 트리의 높이(height)라고 한다
트리는 스택이나 큐와 달리 비선형 자료구조이자, 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다
사이클이 존재할 수 없다 (그래프와 트리의 차이)
루트에서 한 노드로 가는 경로는 유일하다
노드의 개수가 N개면 간선은 N-1개이다
- 전위 순회 (pre-order) Root → Left child → Right child
- 중위 순회 (in-order) Left child → Root → Right child
- 후위 순회 (post-order) Left child → Right child → Root
- 레벨 순회 (level-order) 루트부터 계층 별로 방문하는 방식
이진 트리는 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 지며, 각 서브 트리 또한 이진 트리이다
이진 트리를 배열로 구성할 경우, i번째 노드에 대하여 parent(i) = i / 2, left_child(i) = 2 * i, right_child(i) = 2 * i + 1 의 index를 갖는다
이진 트리는 아래와 같이 분류할 수 있다
- Perfect Binary Tree (포화 이진 트리) 모든 레벨이 꽉 찬 이진 트리
- Complete Binary Tree (완전 이진 트리) 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 채워진 이진 트리
- Full Binary Tree (정 이진 트리) 모든 노드가 0개 또는 2개의 자식 노드를 갖는 이진 트리
이진 트리의 일종으로, 데이터를 저장하는 규칙들을 규정하여 데이터를 효율적으로 탐색할 수 있게 해준다
이진 탐색 트리는 이진탐색과 연결리스트을 합하여 각각의 단점을 보완하고 장점을 모두 얻는다
이진 탐색의 경우, 탐색에 소요되는 시간 복잡도가 O(log n)이라는 장점이 있지만, 데이터의 삽입 및 삭제가 불가능하다는 한계가 존재한다
연결 리스트의 경우, 삽입과 삭제의 시간 복잡도는 O(1)이지만, 탐색은 O(N)이라는 단점이 있다
이렇게 두 가지 장점을 합하여 효율적인 탐색 능력을 가지고, 자료의 삽입 및 삭제가 가능한 자료구조가 탄생한 것이다
- 이진 탐색 트리의 노드에 저장된 키는 유일하다
- 부모의 키가 왼쪽 자식 노드의 키보다 크다
- 부모의 키가 오른쪽 자식 노드의 키보다 작다
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다
*참고: 이진 트리이므로 모든 노드의 자식은 2개 이하이다
이진 탐색 트리의 순회는 중위 순회 방식을 따른다
이를 통해 정렬된 순서로 자료를 탐색할 수 있다
- 자식이 없는 단말 노드인 경우 : 삭제
- 자식이 1개인 노드인 경우 : 지워진 노드의 자식을 올린다
- 자식이 2개인 노드인 경우 : 오른쪽 노드의 가장 작은 값, 또는 왼쪽 자식 노드의 가장 큰 값을 올린다
- 장점 : 탐색 연산의 시간 복잡도가 O(log n) 이다 정확히는 트리의 높이 h에 대하여 O(h)의 시간복잡도를 갖는다 트리에 레벨이 추가될 때 추가가능한 노드의 수가 2배씩 증가하기 때문이다
- 단점 : 편향 트리 (Skewed Tree)가 되어 Worst Case의 시간복잡도가 O(n)이 될 수 있다
해당 단점을 보완하기 위해 트리의 균형을 맞춰주는 Rebalancing(재조정)이 필요하며, 그러한 기법을 이용한 트리에는 Red Black Tree와 AVL Tree가 있다
BST를 기반으로 한 자료구조로, 데이터의 탐색, 삽입, 삭제 연산이 전부 O(log n)이라는 시간 복잡도가 소요되는 장점을 가지고 있다
BST에서 Depth를 최소화한 Complete Binary Tree를 구현하여 시간 복잡도를 줄이는 것이 핵심이다 (노드의 자식이 없을 경우 NIL 값을 저장한 후 단말 노드로 간주한다) 앞선 BST의 단점 중 편향된 트리의 경우에 발생하는 단점을 보완하기 위해 Balanced 상태로 트리를 유지한다. 즉, 루트 노드부터 단말 노드까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다
Red Black Tree는 아래와 같은 규칙들을 만족하는 BST이다
- 모든 노드는 Black 또는 Red의 색을 갖는다
- 루트 노드의 색은 Black이다
- 단말 노드의 색은 Black이다
- 어떤 노드의 색이 Red라면 다른 두 개의 자식의 색은 Black이다
- 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 전부 같은 수의 Black 노드를 포함하고 있다 이때, 해당 Black 노드의 수를 Black Height라고 부른다
배열에 기반하여 구현한 Complete Binary Tree 이며, 이 때 배열의 1번 index에 루트 노드가 들어간다
Max Heap(최대힙)과 Min Heap(최소힙), 2종류가 존재한다
- 최대 힙 : 각 노드의 값이 자식들보다 크거나 같다
- 최소 힙 : 각 노드의 값이 자식들보다 작거나 같다
- 부모 노드는 반드시 자식 노드보다 값이 커야 한다 (최대 힙)
- 형제 또는 사촌 노드 간의 규칙은 없다 (우선순위가 없다)
- 원소를 heap의 가장 마지막 노드에 추가
- 추가한 원소를 부모와 비교하여 조건과 일치한다면 중지
- 부모와 위치를 교환 후 2~3번 반복
Binary heap에서 다음 값(최대 값/최소 값)을 추출하고 다음 값을 루트 노드로 만드는 작업이다
- Heap의 루트 노드 삭제
- 마지막 노드를 루트로 이동
- 루트를 자식 노드와 비교하여 조건과 일치한다면 중지
- 루트와 위치를 교환한 후 3~4번 반복
- 각 힙의 루트에 저장된 값이 가장 큰/작은 값이므로 최대/최소 값을 탐색하는 연산이 O(1)이다
- 데이터의 삽입/삭제는 최악의 경우에도 O(nlog n)이라는 시간 복잡도를 갖는다