자가 균형 이진 탐색 트리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
- 2.1. 기타 자가 균형 이진 탐색 트리
3. 특징
- 3.1. 시간 복잡도
4. 구현
5. 응용
참조

1. 개요

자가 균형 이진 탐색 트리는 이진 탐색 트리의 일종으로, 삽입 및 삭제 시 트리 회전 등의 연산을 통해 트리의 균형을 자동으로 유지하는 자료 구조이다. AVL 트리, 레드-블랙 트리 등이 있으며, 대부분의 연산에서 O(log n)의 시간 복잡도를 보장한다. 1962년 AVL 트리가 최초로 발명되었으며, 레드-블랙 트리는 AVL 트리보다 회전 연산 횟수가 적어 삽입/삭제 성능이 더 우수하다. 자가 균형 이진 탐색 트리는 정렬된 목록 구성, 연관 배열 구현, 이진 트리 정렬 등에 사용되며, 계산 기하학 알고리즘, 데이터베이스 쿼리 최적화 등에도 활용된다.

더 읽어볼만한 페이지

이진 트리 - 스플레이 트리
스플레이 트리는 스플레이 연산을 통해 자가 균형을 유지하며 최근 접근 노드의 빠른 접근을 가능하게 하는 이진 탐색 트리로, 분할 상환 분석 시 평균적으로 O(log n)의 시간 복잡도를 가진다.
이진 트리 - 스레드 이진 트리
스레드 이진 트리는 이진 트리의 NULL 포인터를 활용해 중위 순회 순서상 이전 또는 다음 노드를 가리키도록 하여 효율적인 순회를 가능하게 하고, 스레드 방식에 따라 단일 스레드와 이중 스레드로 나뉜다.
트리 구조 - 덴드로그램
덴드로그램은 데이터 분석에서 데이터 포인트 간 계층적 관계를 시각적으로 표현하는 나무 형태의 다이어그램으로, 군집 분석에서 클러스터 간 유사성을 나타내기 위해 활용되며 다양한 분야에 응용된다.
트리 구조 - 프림 알고리즘
프림 알고리즘은 그래프의 최소 비용 신장 트리를 찾는 탐욕 알고리즘으로, 최소 가중치를 가진 간선을 선택하여 트리를 확장하며, 시간 복잡도는 사용되는 자료 구조에 따라 달라진다.
소련의 발명품 - 스푸트니크 1호
스푸트니크 1호는 1957년 소련이 발사한 세계 최초의 인공위성으로, 미국 사회에 큰 충격을 주어 우주 경쟁을 촉발하고 과학 기술 발전에 영향을 미쳤으며, 1958년 대기권에 재진입하여 소멸되었다.
소련의 발명품 - 스크린도어
스크린도어는 철도 승강장에서 승객의 안전을 위해 설치되는 설비로, 열차 사고 예방, 무인 운전 가능, 쾌적한 승강장 유지를 위해 다양한 종류로 설치되며, 설치 및 유지 보수 비용, 열차 지연 등의 문제점도 존재한다.

자가 균형 이진 탐색 트리

2. 역사

이진 탐색 트리의 연산 시간은 대부분 트리의 높이에 비례하기 때문에, 높이를 작게 유지하는 것이 중요하다. 일반적인 이진 탐색 트리는 키가 정렬된 순서로 삽입될 경우 트리의 높이가 커져서 연결 리스트와 유사해지는 문제점이 있다. 이러한 경우 모든 연산에 높은 비용이 소요된다.^[1]

자가 균형 이진 탐색 트리는 트리 회전과 같은 트리 변환을 통해 높이를 $O(\log n)$ 으로 유지하여 이 문제를 해결한다. 이러한 변환에는 약간의 오버헤드가 발생하지만, 연산 속도를 향상시켜 장기적으로 이점을 제공한다.

''n''개의 노드를 가진 이진 트리의 최소 높이는 $\lfloor \log_2 n\rfloor$ 이다. 자가 균형 BST는 이 최소 높이를 항상 유지하지는 않지만, 높이를 이 하한의 상수배 이내로 유지한다.

연산	Big-O 시간
참조	O(log n)
삽입	O(log n)
삭제	O(log n)
모든 요소에 대한 반복	O(n)

2. 1. 기타 자가 균형 이진 탐색 트리

AVL 트리, 레드-블랙 트리, 스플레이 트리, 스케이프고트 트리, 트리프, AA 트리, 가중 균형 트리, 탱고 트리, 2-3 트리, B-트리는 자가 균형 이진 탐색 트리를 구현한 자료 구조들이다.

자가 균형 이진 탐색 트리
이름	발표 년도
AVL 트리	1962년
레드-블랙 트리	1972년
스플레이 트리	1985년
스케이프고트 트리	1989년
트리프	1989년
AA 트리	1993년

B-트리, 2-3 트리, 2-3-4 트리는 이진 트리는 아니지만, 균형 탐색 트리의 일종이다. 스키핑 리스트는 트리 구조는 아니지만, 같은 용도로 사용할 수 있다. 트리프와 스키핑 리스트는 확률적 알고리즘이다.

3. 특징

트리 회전은 자가 균형 이진 트리에서 균형을 유지하기 위한 일반적인 연산이다.

이진 탐색 트리 (BST)에서 대부분의 연산은 트리의 높이에 비례하는 시간이 걸리므로, 높이를 작게 유지하는 것이 중요하다. 높이 ''h''인 이진 트리는 최대

2^{h+1}-1

개의 노드를 가질 수 있다. 따라서 ''n''개의 노드를 가진 트리의 높이 ''h''는 다음과 같은 관계를 가진다.

:

h\ge\lceil\log_2(n+1)-1\rceil\ge \lfloor\log_2 n\rfloor

.

즉, ''n''개 노드를 가진 이진 트리의 최소 높이는

\lfloor \log_2 n\rfloor

(로그의 내림)이다.^[1]

하지만 가장 단순한 BST 삽입 알고리즘은 정렬된 키 순서로 삽입되는 경우처럼, 트리의 높이가 ''n''이 될 수 있다. 예를 들어, ''n'' = 1,000,000일 때 최소 높이는

\lfloor \log_2(1,000,000) \rfloor = 19

이지만, 최악의 경우에는 1,000,000이 될 수 있다.

데이터를 미리 알고 있다면, 무작위 순서로 값을 추가하여 무작위 이진 탐색 트리를 만들 수 있다. 그러나 온라인 알고리즘과 같이 이러한 무작위화가 불가능한 경우도 많다.

자가 균형 이진 트리는 삽입 시 트리 회전과 같은 트리 변환을 수행하여 높이를

log

₂(''n'')^영어에 비례하게 유지한다. 이러한 오버헤드는 있지만, 조회 비용보다 크지 않으며 모든 연산의 빠른 실행을 보장한다.

AVL 트리는 최적 높이의 1.44배 이내로 유지하면서 추가 저장 공간은 2비트만 필요하다.^[1] 따라서 대부분의 자가 균형 BST 알고리즘은 높이를 최소 높이의 상수 계수 이내로 유지한다.

3. 1. 시간 복잡도

이진 탐색 트리 연산 시간은 대부분 트리의 높이에 비례하므로, 높이를 작게 유지하는 것이 중요하다. 일반적인 이진 탐색 트리는 키가 정렬된 순서로 삽입되는 경우 트리가 연결 리스트처럼 되어 성능이 저하될 수 있다. 자가 균형 이진 트리는 트리 회전과 같은 연산을 통해 높이를

O(\log n)

에 비례하게 유지하여 이 문제를 해결한다.

''n''개의 노드를 가진 자가 균형 이진 탐색 트리에서 참조, 삽입, 삭제 연산은 최악의 경우

O(\log n)

시간이 걸리고, 모든 요소를 정렬된 순서로 반복하는 데는

O(n)

시간이 걸린다. 이는 키를 비교하는 방식의 자료 구조 중에서 점근적으로 최적의 성능이다.

연산	시간 복잡도
참조	O(log n)
삽입	O(log n)
삭제	O(log n)
모든 요소에 대한 반복	O(n)

4. 구현

자가 균형 이진 탐색 트리를 구현하는 자료 구조는 다음과 같다.

2-3 트리
AA 트리
AVL 트리
B-트리
레드-블랙 트리
스케이프고트 트리
탱고 트리
트리프
가중 균형 트리

자가 균형 이진 탐색 트리
이름	영어 이름	발표 년도
AVL 트리	AVL tree	1962년
레드-블랙 트리	red-black tree	1972년
스플레이 트리	splay tree	1985년
스케이프고트 트리	scapegoat tree	1989년
트리프	treap	1989년
AA 트리	AA tree	1993년

또한, 2진 트리가 아닌 균형 탐색 트리로는 B 트리, 2-3 트리, 2-3-4 트리 등이 있다. 트리 구조는 아니지만, 같은 용도로 사용할 수 있는 것으로는 스키핑 리스트가 있다. 트리프와 스키핑 리스트는 확률적 알고리즘이다.

5. 응용

자가 균형 이진 탐색 트리는 우선순위 큐와 같이 정렬된 목록을 구성하고 유지하는 데 사용될 수 있다.^[2] 또한 연관 배열에도 사용할 수 있는데, 키-값 쌍은 키를 기반으로 하는 정렬 순서로 삽입된다. 이러한 기능에서 자가 균형 BST는 해시 테이블에 비해 장단점을 갖는다. 자가 균형 BST의 장점은 해시 테이블이 제공하지 않는 ''키 순서대로'' 항목을 빠르게 열거할 수 있다는 것이다. 단점은 동일한 키를 가진 여러 항목이 있을 경우 검색 알고리즘이 더 복잡해진다는 것이다. 자가 균형 BST는 대부분의 해시 테이블보다 최악의 경우 검색 성능이 더 우수하지만( $O(\log n)$ 대 $O(n)$ ), 평균적인 경우 성능은 더 나쁘다( $O(\log n)$ 대 $O(1)$ ).

자가 균형 BST는 변경 가능한 정렬된 목록이 필요한 모든 알고리즘을 구현하여 최적의 최악의 경우 점근적 성능을 달성하는 데 사용할 수 있다. 예를 들어, 이진 트리 정렬이 자가 균형 BST로 구현되면 매우 간단하면서도 점근적으로 최적인 $O(n \log n)$ 정렬 알고리즘을 얻을 수 있다. 마찬가지로, 계산 기하학의 많은 알고리즘은 자가 균형 BST의 변형을 활용하여 선분 교차 문제 및 점 위치 문제와 같은 문제를 효율적으로 해결한다. (그러나 평균적인 경우 성능의 경우, 자가 균형 BST는 다른 솔루션보다 효율성이 떨어질 수 있다. 특히 이진 트리 정렬은 트리 균형 조정 오버헤드와 캐시 액세스 패턴 때문에 병합 정렬, 퀵 정렬, 또는 힙 정렬보다 느릴 가능성이 있다.)

자가 균형 BST는 유연한 데이터 구조로, 추가 정보를 효율적으로 기록하거나 새로운 작업을 수행하도록 확장하기 쉽다. 예를 들어, 특정 속성을 가진 각 서브트리의 노드 수를 기록하여 $O(\log n)$ 시간에 해당 속성을 가진 특정 키 범위의 노드 수를 계산할 수 있다. 이러한 확장은 예를 들어 데이터베이스 쿼리 또는 기타 목록 처리 알고리즘을 최적화하는 데 사용할 수 있다.^[2]

참조

_[1] 서적 The Art of Computer Programming Addison-Wesley 1998
_[2] 문서 Cuckoo hashing provides worst-case lookup performance of $O(1)$ .
_[3] 서적 The Art of Computer Programming Addison-Wesley 1998

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com