💡 균형 트리 (Balanced Tree) - 모든 서브트리의 ‘높이 차이가 최대 하나’인 이진트리를 의미합니다. 이러한 특성으로 인해 균형 트리는 검색 연산의 시간 복잡도를 최적화할 수 있습니다. - 대표적인 균형 트리의 종류로는 AVL 트리, 레드-블랙 트리, B-트리 등이 있습니다. - 이러한 균형 트리들은 삽입, 삭제 연산이 발생할 때 트리의 균형을 유지하면서 효율적인 검색을 제공합니다.
2. 이진 탐색 트리(Binary Search Tree)
💡 이진 탐색 트리(Binary Search Tree)
- 노드가 최대 두 개의 자식 노드를 가지며 ‘왼쪽 자식 노드’는 현재 노드보다 ‘작은 값’을 갖고 ‘오른쪽 노드’는 현재 노드보다 ‘큰 값’을 갖는 트리를 의미합니다.
2.1. 이진 탐색 트리(Binary Search Tree) 속성
https://yoongrammer.tistory.com/71
💡 이진 탐색 트리(Binary Search Tree) 속성
1. 각 노드에는 값을 가지고 있습니다.
2. 모든 노드는 유일한 키 값을 갖습니다.
3. 노드의 왼쪽 서브 트리(Left Subtree)에는 루트노드보다 작은 값의 노드만 포함이 됩니다.
4. 노드의 오른쪽 서브 트리(Right Subtree)에는 루트노드보다 큰 값의 노드만 포함이 됩니다.
5. 왼쪽 서브트리(Left Subtree)와 오른쪽 서브트리(Right Subtree) 모두 이진 탐색 트리여야 합니다.
2.2. 이진 탐색 트리(Binary Search Tree)의 주요 특징
💡 이진 탐색 트리(Binary Search Tree)의 주요 특징 1. 검색 연산의 효율성을 가지고 있습니다.
- 트리에서 데이터를 검색할 때는 현재 노드의 값과 찾고자 하는 값을 비교하여 작으면 왼쪽 자식 노드로 이동하고 크면 오른쪽 자식 노드로 이동합니다. 이렇게 반복하면서 검색 대상을 좁혀나가는 것이 가능합니다 - 이진 탐색 트리의 검색 연산은 평균적으로 O(log n)의 시간 복잡도를 가지며, 효율적인 데이터 검색이 가능합니다.
2. 데이터를 정렬된 상태로 유지할 수 있습니다.
- 새로운 데이터를 삽입할 때는 적절한 위치를 찾아서 삽입하며, 삭제 연산을 통해 데이터를 삭제하면 트리의 구조가 유지됩니다. - 하지만 이진 탐색 트리는 데이터의 삽입 순서에 따라 트리의 구조가 달라질 수 있고, 최악의 경우에는 트리가 편향되어 검색 연산의 효율성이 저하될 수 있습니다.
https://adjh54.tistory.com/186
2.3. 이진 탐색 트리 탐색 순서
💡 이진 탐색 트리(Binary Search Tree) 탐색 순서 - 이진 탐색 트리의 탐색 순서는 ‘탐색 대상을 반’으로 줄여나가기 때문에 평균적으로 O(log n)의 시간 복잡도를 가지며, 매우 효율적입니다.
1. 현재 노드의 키 값과 목표 값을 비교합니다.
2. 목표 값이 현재 노드의 키 값보다 작으면 왼쪽 서브트리로 이동합니다.
3. 목표 값이 현재 노드의 키 값보다 크면 오른쪽 서브트리로 이동합니다.
4. 목표 값과 현재 노드의 키 값이 같으면 탐색을 성공적으로 완료합니다.
5. 하위 트리에서 위의 단계를 반복합니다.
💡 이진 탐색 트리(Binary Search Tree) 탐색 순서 예시 설명
- 해당 예시에서는 60이라는 Key 값을 찾으려고 합니다. 이를 위해 루트 노드를 기준으로 60을 탐색합니다.
1. 현재 노드의 키 값과 목표 값을 비교합니다. - 현재 노드의 키값(50) - 목표 값(60)
2. 목표 값이 현재 노드의 키 값보다 작으면 왼쪽 서브트리로 이동합니다. - 목표 값(60) < 현재 노드의 키 값(50) ( * 해당 값은 옳지 않으므로 왼쪽으로 이동하지 않습니다)
3. 목표 값이 현재 노드의 키 값보다 크면 오른쪽 서브트리로 이동합니다. - 목표 값(60) < 현재 노드의 키 값(50) (* 해당 값은 참이므로 오른쪽으로 이동합니다)
4. 목표 값과 현재 노드의 키 값이 같으면 탐색을 성공적으로 완료합니다. - 아직 목표 값과 현재 노드가 일치하지 않으므로 5번 단계로 이동합니다.
5. 하위 트리에서 위의 단계를 반복합니다. -해당 값을 찾지 못하였으므로 2 → 3 → 4 과정을 반복 수행하여 목표값을 찾습니다.
https://yoongrammer.tistory.com/71
3. 균형 이진 탐색 트리(Balanced Binary Search Tree)
💡 균형 이진 탐색 트리(Balanced Binary Search Tree)
- 이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식은 현재 노드보다 작은 값을, 오른쪽 자식은 현재 노드보다 큰 값을 갖습니다. 이러한 이진 탐색 트리의 특성을 유지하면서 불균형한 상태를 피하기 위해 노드 삽입 또는 삭제 시에 트리를 재조정합니다.
- 균형 이진 탐색 트리의 대표적인 종류로 AVL 트리와 레드-블랙 트리가 있습니다.
3) 균형 트리 종류 : 종합
자료구조
설명
검색 시간 복잡도
삽입 시간 복잡도
삭제 시간 복잡도
AVL 트리
노드의 ‘왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1을 넘어가지 않도록 유지’하는 형태의 균형 이진 탐색 트리
O(log n)
O(log n)
O(log n)
레드-블랙 트리
노드가 레드 또는 블랙인 색깔을 가지며, 특정한 규칙을 따르는 균형 이진 탐색 트리
O(log n)
O(log n)
O(log n)
B-트리
노드가 정렬된 데이터를 유지하면서 효율적인 삽입, 삭제 및 검색 작업을 수행하는 자기 균형 탐색 트리
O(log n)
O(log n)
O(log n)
https://adjh54.tistory.com/186
반응형
4) 균형 트리 종류 : AVL 트리
💡 AVL 트리 - AVL의 의미는 발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름입니다. - 균형 이진 탐색의 하나의 종류로 각 노드의 ‘왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1을 넘어가지 않도록 유지’하는 형태의 균형 이진트리를 의미합니다.
- AVL 트리는 삽입 또는 삭제 연산 후에 자동으로 균형을 유지하기 위해 회전 연산을 사용합니다. 회전 연산은 트리의 구조를 변경하여 균형을 복구합니다. - AVL 트리의 장점은 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(log n)으로 매우 효율적이라는 것입니다. 하지만 AVL 트리는 균형을 유지하기 위해 회전 연산이 필요하므로 일반적인 이진 탐색 트리보다는 조금 더 복잡한 구현이 필요합니다. - AVL 트리는 자주 변경되는 데이터 셋에 적합하며, 데이터의 삽입과 삭제가 빈번한 경우에도 균형을 유지하여 항상 빠른 탐색 속도를 제공할 수 있습니다.
1. AVL 트리 기본 구조
💡 기본 구조 설명
- 왼쪽 서브트리 1은 8,5,11 형태로 구성이 되어 있고, 서브트리 2는 5,4 형태로 구성이 되어있습니다. - 오른쪽 서브트리는 18, 17로 하나의 서브트리로 구성되어 있습니다.
🚨 왼쪽은 2개의 서브트리, 오른쪽은 1개의 서버트리로 높이 차이가 1 이나는 AVL 트리를 의미합니다.
1. 왼쪽 자식(A)을 기준으로 오른쪽 서브트리(B)에 불균형이 발생하였습니다. 2. 왼쪽 자식(A)은 왼쪽 회전을 통하여 왼쪽으로 이동하고 B는 오른쪽으로 이동합니다. 3. 좌측 편향 이진트리로 구성이 됩니다. 4. B를 기반으로 C는 ‘오른쪽 회전’을 수행하여 최종 이진트리가 구성이 됩니다.
💡 이중 회전 : 오른쪽 - 왼쪽 회전(Right - Left Rotation) - 불균형이 오른쪽 자식의 왼쪽 서브트리에서 나타나는 경우를 의미합니다.
1. 오른쪽 자식(C)을 기준으로 왼쪽 서브트리(B)에 불균형이 발생하였습니다. 2. 오른쪽 자식(C)은 오른쪽 회전을 통하여 오른쪽으로 이동하고 B는 왼쪽으로 이동합니다. 3. 우측 편향 이진트리로 구성이 됩니다. 4. B를 기반으로 A는 ‘왼쪽 회전’을 수행하여 최종 이진트리가 구성이 됩니다.
💡Step-2 : 노드 값을 찾습니다. 찾고자 하는 값(11)이 현재 노드(7) 보다 크면 오른쪽 자식 노드(18)로 이동합니다.
- 현재 노드의 값과 찾고자 하는 값을 비교합니다.
CASE1: 찾고자 하는 값이 현재 노드의 값보다 작다면, 현재 노드의 왼쪽 자식 노드로 이동합니다. CASE2: 찾고자 하는 값이 현재 노드의 값보다 크다면, 현재 노드의 오른쪽 자식 노드로 이동합니다. CASE3: 찾고자 하는 값이 현재 노드의 값과 같다면, 해당 노드를 찾았습니다
💡Step-3: 노드 값을 찾습니다. - 찾고자 하는 값(11)이 현재 노드(18) 보다 작으면 왼쪽 자식 노드(10)로 이동합니다. - 현재 노드의 값과 찾고자 하는 값을 비교합니다. CASE1: 찾고자 하는 값이 현재 노드의 값보다 작다면, 현재 노드의 왼쪽 자식 노드로 이동합니다. CASE2: 찾고자 하는 값이 현재 노드의 값보다 크다면, 현재 노드의 오른쪽 자식 노드로 이동합니다. CASE3: 찾고자 하는 값이 현재 노드의 값과 같다면, 해당 노드를 찾았습니다
💡 Step-4: 찾고자 하는 값(11)과 현재 노드 값(11)이 같으면 해당 노드를 찾았습니다. - 위의 과정을 현재 노드가 리프 노드가 될 때까지 반복합니다. - 리프 노드까지 도달했는데도 찾고자 하는 값과 일치하는 노드를 찾지 못했다면, 해당 값은 트리에 존재하지 않습니다.
- 정렬된 데이터를 유지하면서 효율적인 삽입, 삭제 및 검색 작업을 수행하는 자체 균형 검색 트리 자료 구조입니다.
- 이는 데이터베이스의 인덱스와 파일 시스템에서 일반적으로 사용됩니다.
[ 더 알아보기 ] 💡 자체 균형 검색 트리(Self-Balancing Binary Search Tree)
- 이진 탐색 트리(Binary Search Tree)를 응용한 것으로 트리의 ‘균형을 유지’하면서 탐색, 삽입, 삭제 연산을 효율적으로 수행할 수 있는 자료 구조입니다. - 이러한 트리는 특정 연산의 시간 복잡도를 최적화하여 탐색과 관련된 작업을 빠르게 수행할 수 있습니다. - 대표적인 자기 균형 검색 트리로는 AVL 트리, 레드-블랙 트리, B-트리 등이 있습니다.
1. B-트리 기본구조
💡 B-트리 기본구조 1. 하나의 노드에는 ‘여러 개의 키’와 자식 노드를 가리키는 ‘자식 포인터’로 구성이 되어 있습니다. 2. B-트리의 루트 노드, 내부 노드 및 리프노드로 구성이 되어 있습니다.
- 루트 노드는 트리의 가장 위에 있는 노드이며 자식 노드를 가리키는 포인터를 포함하고 있습니다. - 내부 노드는 키와 자식 노드를 가지고 있습니다. - 리프 노드는 실제 데이터나 데이터를 가리키는 포인터를 저장합니다.
- B-트리는 균형을 유지하며, 모든 리프 노드가 동일한 레벨에 위치합니다. 이는 트리가 검색 작업에 대해 효율적인 상태를 유지하도록 합니다.
2. 다중 키
- B-트리의 각 노드는 여러 개의 키와 해당 값들을 포함할 수 있습니다. 이는 대량의 데이터를 효율적으로 저장하고 검색할 수 있게 해 줍니다.
3. 분할과 병합
- B-트리의 노드가 가득 차면, 노드는 두 개의 노드로 분할되고, 한 개의 키는 상위 노드로 이동됩니다. 반대로, 노드가 너무 비어 있으면 인접한 노드와 병합될 수 있습니다. 이는 트리가 균형을 유지하도록 합니다.
4. 자식 포인터
- B-트리의 각 노드는 자식 노드를 가리키는 포인터를 포함합니다. 이 포인터들은 검색 작업 중에 트리를 효율적으로 탐색하는 데 도움을 줍니다.
3. B-트리 검색과정
💡 B-트리 검색과정
- B-트리 검색 과정은 대소관계의 비교를 통해 ‘가능성을 제한’함으로써 검색이 감소하게 하는 방법입니다. - 해당 과정은 리프노드에 도달할 때까지 반복하여 수행합니다. - 각각 네모에 들어가 있는 값은 노드의 키 값을 의미합니다 - 노란색 부분은 자식 노드를 가리키는 ‘포인터’를 의미합니다.
💡 해당 예시에서는 ‘19’ 값을 찾는 과정을 예시로 알아봅니다.
💡 STEP1
- 먼저, 검색은 루트 노드부터 시작됩니다.
1. 찾으려는 값은 ‘19’입니다. 2. 찾으려는 값(19)은 7보다 크고 7과 15 사이의 값은 아니고 ‘15 이상의 값’입니다. 그렇다면 오른쪽으로 이동합니다
💡 STEP 2
1. 찾으려는 값은 ‘19’입니다. 2. 찾으려는 값(19)은 17보다 크고 ‘17과 20 사이’의 값입니다. 그렇다면 중간으로 이동합니다.
💡 STEP 3
1. 찾으려는 값은 ‘19’입니다. 2. 리프노드에서 찾으려는 값을 찾았습니다.
💡 최종적으로 대소 관계를 통하여서 ‘가능성을 제한’하여 검색을 감소하여 최적화된 검색 방법입니다.
💡[참고] 좀 더 다양한 자료구조에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.
