Binary Search Tree - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:19:25Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:19 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Data Structures#Binary Search Tree\|Data Structures]]		상위 문서: [[Data Structures#Binary Search Tree\|Data Structures]]

Pinkgo: /* Balanced Binary Search Trees */

2025-09-24T21:11:08Z

Balanced Binary Search Trees

← 이전 판		2025년 9월 24일 (수) 21:11 판
136번째 줄:		136번째 줄:

	Perfectly Balanced 트리는 이론적으로는 이상적이지만, 실제로는 유지하기 어렵다. 그 이유는 어떠한 Perfectly Balanced 트리에 새로운 키를 삽입하고 잘 할 때에는 이를 유지하기 위해 모든 노드의 위치를 재조정해야 하기 때문이다. 이 과정에 드는 비용은 <math>\Theta(log(n))</math>으로 배보다 배꼽이 더 큰 격이다.		Perfectly Balanced 트리는 이론적으로는 이상적이지만, 실제로는 유지하기 어렵다. 그 이유는 어떠한 Perfectly Balanced 트리에 새로운 키를 삽입하고 잘 할 때에는 이를 유지하기 위해 모든 노드의 위치를 재조정해야 하기 때문이다. 이 과정에 드는 비용은 <math>\Theta(log(n))</math>으로 배보다 배꼽이 더 큰 격이다.

	~~<syntaxhighlight lang="c">~~

	~~</syntaxhighlight>~~
	~~<syntaxhighlight lang="c">~~

	~~</syntaxhighlight>~~

	==각주==		==각주==

Pinkgo: /* Tree Insertion/Deletion */

2025-09-12T16:13:50Z

Tree Insertion/Deletion

@@ 126번째 줄: / 126번째 줄: @@
 ## 삭제 노드의 값을 successor(또는 predecessor)의 값으로 교체한다.
 ## 그 다음 successor(또는 predecessor) 노드를 삭제한다.<ref>이 노드는 자식이 최대 1개뿐이므로 삭제가 쉽다.</ref>
 <syntaxhighlight lang="c">

Pinkgo: /* Predecessor/Successor */

2025-09-12T15:27:34Z

Predecessor/Successor

← 이전 판		2025년 9월 12일 (금) 15:27 판
68번째 줄:		68번째 줄:
	===Predecessor/Successor===		===Predecessor/Successor===
	<gallery widths="300" heights="300">		<gallery widths="300" heights="300">
	파일:Figure 3. Predecessor-Successor ~~Case 1~~.jpg\|Figure 3. Predecessor-Successor		파일:Figure 3. Predecessor-Successor EXAMPLE.jpg\|Figure 3. Predecessor-Successor Case 1
	파일:Figure 4. Predecessor-Successor Case 2.jpg\|Figure 4. Predecessor-Successor Case 2.jpg		파일:Figure 4. Predecessor-Successor Case 2.jpg\|Figure 4. Predecessor-Successor Case 2.jpg
	</gallery>		</gallery>

Pinkgo: /* Predecessor/Successor */

2025-09-12T15:25:13Z

Predecessor/Successor

← 이전 판		2025년 9월 12일 (금) 15:25 판
68번째 줄:		68번째 줄:
	===Predecessor/Successor===		===Predecessor/Successor===
	<gallery widths="300" heights="300">		<gallery widths="300" heights="300">
	파일:Figure 3. Predecessor-Successor Case 1.jpg\|Figure 3. Predecessor-Successor ~~Case 1~~		파일:Figure 3. Predecessor-Successor Case 1.jpg\|Figure 3. Predecessor-Successor
	파일:Figure 4. Predecessor-Successor Case 2.jpg\|Figure 4. Predecessor-Successor Case 2.jpg		파일:Figure 4. Predecessor-Successor Case 2.jpg\|Figure 4. Predecessor-Successor Case 2.jpg
	</gallery>		</gallery>

Pinkgo: /* Predecessor/Successor */

2025-09-12T15:24:43Z

Predecessor/Successor

← 이전 판		2025년 9월 12일 (금) 15:24 판
67번째 줄:		67번째 줄:

	===Predecessor/Successor===		===Predecessor/Successor===
	<gallery widths="~~300px~~" heights="~~300px~~">		<gallery widths="300" heights="300">
	Figure 3. Predecessor-Successor Case 1.jpg\|Figure 3. Predecessor-Successor Case 1		파일:Figure 3. Predecessor-Successor Case 1.jpg\|Figure 3. Predecessor-Successor Case 1
	Figure 4. Predecessor-Successor Case 2.jpg\|Figure 4. Predecessor-Successor Case 2.jpg		파일:Figure 4. Predecessor-Successor Case 2.jpg\|Figure 4. Predecessor-Successor Case 2.jpg
	</gallery>		</gallery>
	어떤 sorted list 자료구조의 predecessor와 successor의 정의는 아래와 같다:		어떤 sorted list 자료구조의 predecessor와 successor의 정의는 아래와 같다:

Pinkgo: /* Predecessor/Successor */

2025-09-12T15:19:38Z

Predecessor/Successor

← 이전 판		2025년 9월 12일 (금) 15:19 판
73번째 줄:		73번째 줄:
	어떤 sorted list 자료구조의 predecessor와 successor의 정의는 아래와 같다:		어떤 sorted list 자료구조의 predecessor와 successor의 정의는 아래와 같다:
	* Predecessor: 어떤 노드 X의 바로 앞 원소.		* Predecessor: 어떤 노드 X의 바로 앞 원소.
	* Successor: 어떤 노드 X의 바로 뒤 원소.		* Successor: 어떤 노드 X의 바로 뒤 원소.
	이를 이진 탐색 트리에 확장시키면, 어떤 노드 X가 두 자식을 가진다고 할 때 아래와 같이 정의된다:		이를 이진 탐색 트리에 확장시키면, 어떤 노드 X가 두 자식을 가진다고 할 때 아래와 같이 정의된다:
	* Predecessor: X의 왼쪽 서브트리의 최대값		* Predecessor: X의 왼쪽 서브트리의 최대값

2025년 9월 12일 (금) 15:13에 Pinkgo님의 편집

2025-09-12T15:13:14Z

@@ 95번째 줄: / 95번째 줄: @@
+}
 </syntaxhighlight>
 이러한 메커니즘은 figure 4와 같은 이진 탐색 트리를 A,B,C,D,E,F,G,H의 순서로 순회한다. 이때 시간 복잡도는 각 노드 방문에 O(1) 시간이 소요되고 총 n개의 노드를 방문하므로 O(n)의 시간복잡도가 소요된다.
 <syntaxhighlight lang="c">
 </syntaxhighlight>
 <syntaxhighlight lang="c">

Pinkgo: /* In-Order Traversal */

2025-09-12T05:12:13Z

In-Order Traversal

← 이전 판		2025년 9월 12일 (금) 05:12 판
80번째 줄:		80번째 줄:

	===In-Order Traversal===		===In-Order Traversal===
	[[파일:Figure 5. In-Order Traversal.jpg\|섬네일\|~~398x398픽셀~~\|Figure 5. In-Order Traversal]]		[[파일:Figure 5. In-Order Traversal.jpg\|섬네일\|298x298px\|Figure 5. In-Order Traversal]]
	In-Order Traversal은 이진 탐색 트리를 오름차순으로 순회하는 탐색법이다. 이는 아래와 같은 재귀적인 메커니즘을 가진다:		In-Order Traversal은 이진 탐색 트리를 오름차순으로 순회하는 탐색법이다. 이는 아래와 같은 재귀적인 메커니즘을 가진다:
	# 왼쪽 서브트리를 먼저 방문		# 왼쪽 서브트리를 먼저 방문

2025년 9월 12일 (금) 05:11에 Pinkgo님의 편집

2025-09-12T05:11:31Z

← 이전 판		2025년 9월 12일 (금) 05:11 판
4번째 줄:		4번째 줄:

	==개요==		==개요==
			[[파일:Figure 1. Binary Search Tree.jpg\|섬네일\|258x258픽셀\|Figure 1. Binary Search Tree]]
	해당 문서는 이진 트리(binary tree)의 한 종류인 이진 탐색 트리(binary search tree)에 대해서 다룬다. 먼저, 이진 트리는 루트(root)를 가진 트리 구조이며, 각 노드는 최대 두 개의 자식을 가진다. 이때 자식 노드는 왼쪽(left child)또는 오른쪽(right child)으로 구분된다. 이러한 이진 트리 구조는 figure 1에 잘 나타나 있다. 그 중에서도 이진 탐색 트리는 자료 구조의 한 종류로, 사전(dictionary) 연산(검색, 삽입, 삭제, 최소값, 최대값, 후속자/전임자 찾기)을 효율적으로 수행할 수 있게 한다.		해당 문서는 이진 트리(binary tree)의 한 종류인 이진 탐색 트리(binary search tree)에 대해서 다룬다. 먼저, 이진 트리는 루트(root)를 가진 트리 구조이며, 각 노드는 최대 두 개의 자식을 가진다. 이때 자식 노드는 왼쪽(left child)또는 오른쪽(right child)으로 구분된다. 이러한 이진 트리 구조는 figure 1에 잘 나타나 있다. 그 중에서도 이진 탐색 트리는 자료 구조의 한 종류로, 사전(dictionary) 연산(검색, 삽입, 삭제, 최소값, 최대값, 후속자/전임자 찾기)을 효율적으로 수행할 수 있게 한다.

46번째 줄:		47번째 줄:

	===Maximum and Minimum===		===Maximum and Minimum===
			[[파일:Figure 2. Min-Max.jpg\|섬네일\|250x250픽셀\|Figure 2. Min-Max]]
	이진 탐색 트리에서 최솟값/최댓값을 탐색하는 것은 매우 쉽다. 최솟값은 가장 왼쪽에 위치한 노드이며, 최댓값은 가장 오른쪽에 위치한 노드이기 때문이다. 따라서 원리는 같으므로, 최솟값을 탐색하는 코드만 언급한다:		이진 탐색 트리에서 최솟값/최댓값을 탐색하는 것은 매우 쉽다. 최솟값은 가장 왼쪽에 위치한 노드이며, 최댓값은 가장 오른쪽에 위치한 노드이기 때문이다. 따라서 원리는 같으므로, 최솟값을 탐색하는 코드만 언급한다:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
65번째 줄:		67번째 줄:

	===Predecessor/Successor===		===Predecessor/Successor===
			<gallery widths="300px" heights="300px">
			Figure 3. Predecessor-Successor Case 1.jpg\|Figure 3. Predecessor-Successor Case 1
			Figure 4. Predecessor-Successor Case 2.jpg\|Figure 4. Predecessor-Successor Case 2.jpg
			</gallery>
	어떤 sorted list 자료구조의 predecessor와 successor의 정의는 아래와 같다:		어떤 sorted list 자료구조의 predecessor와 successor의 정의는 아래와 같다:
	* Predecessor: 어떤 노드 X의 바로 앞 원소.		* Predecessor: 어떤 노드 X의 바로 앞 원소.
74번째 줄:		80번째 줄:

	===In-Order Traversal===		===In-Order Traversal===
			[[파일:Figure 5. In-Order Traversal.jpg\|섬네일\|398x398픽셀\|Figure 5. In-Order Traversal]]
	In-Order Traversal은 이진 탐색 트리를 오름차순으로 순회하는 탐색법이다. 이는 아래와 같은 재귀적인 메커니즘을 가진다:		In-Order Traversal은 이진 탐색 트리를 오름차순으로 순회하는 탐색법이다. 이는 아래와 같은 재귀적인 메커니즘을 가진다:
	# 왼쪽 서브트리를 먼저 방문		# 왼쪽 서브트리를 먼저 방문