이진탐색트리란?
이진 탐색 트리(Binary Search Tree, BST)는 이진 트리의 일종으로, 다음 세 가지 조건을 만족하는 트리입니다.
- 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값의 노드들만 존재합니다.
- 각 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값의 노드들만 존재합니다.
- 왼쪽과 오른쪽 서브트리 모두 이진 탐색 트리입니다.
이진 트리: 노드의 최대 Branch가 2인 트리
주요 용도
이진 탐색 트리는 데이터의 정렬, 검색, 삽입, 삭제 등의 연산을 빠르게 수행할 수 있는 자료구조로서 여러 용도로 사용됩니다. 주요 용도는 다음과 같습니다:
- 데이터 정렬: 이진 탐색 트리는 중위 순회(in-order traversal)를 수행하면 데이터를 정렬된 순서대로 얻을 수 있습니다. 이러한 특징 때문에 이진 탐색 트리는 정렬 알고리즘의 구현에 사용될 수 있습니다.
- 데이터 검색: 이진 탐색 트리는 이진 탐색 원리를 사용하여 데이터를 빠르게 검색할 수 있습니다. 이는 데이터베이스 시스템, 탐색 기반의 응용 프로그램 등에서 사용되며, 효율적인 검색을 필요로 하는 여러 분야에서 활용됩니다.
- 데이터 삽입 및 삭제: 이진 탐색 트리는 삽입 및 삭제 연산을 효율적으로 수행할 수 있어, 동적으로 변하는 데이터 집합을 관리하는 데 사용됩니다. 예를 들어, 자원 관리, 컬렉션 관리, 우선순위 큐 등에서 이용할 수 있습니다.
- 범위 쿼리: 이진 탐색 트리는 특정 범위의 데이터를 빠르게 조회할 수 있어 범위 쿼리를 수행하는 응용 프로그램에서 활용됩니다.
이러한 이유로, 이진 탐색 트리는 여러 분야에서 광범위하게 활용되는 자료구조입니다. 그러나 이진 탐색 트리의 성능은 트리의 균형 여부에 크게 영향을 받으므로, 균형 이진 탐색 트리(AVL 트리, 레드-블랙 트리 등)와 같은 변형된 자료구조를 사용하는 것이 더욱 효율적일 수 있습니다.
시간 복잡도
탐색 시
- depth (트리의 높이) 를 h라고 표기한다면, O(h)
- n개의 노드를 가진다면, $h = log_2{n} $ 에 가까우므로, 시간 복잡도는 $ O(log{n}) $
- 참고: 빅오 표기법에서 에서의 log의 밑은 10이 아니라, 2
- 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함
장점
- 탐색, 삽입, 삭제 연산이 평균적으로 O(log N)의 시간 복잡도를 가집니다. 이는 정렬된 배열에 비해 빠른 연산 속도를 제공합니다.
- 이진 탐색 트리는 동적인 자료구조로, 삽입과 삭제 연산이 가능하며, 데이터가 계속 변경되는 상황에서도 사용할 수 있습니다.
단점
-
최악의 경우(모든 노드가 하나의 자식만 갖는 경우) 이진 탐색 트리의 높이가 N이 되어, 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(N)이 됩니다.
-
균형을 유지하는 추가 작업이 필요합니다. 이를 해결하기 위해 균형 이진 탐색 트리(AVL 트리, 레드-블랙 트리 등)를 사용할 수 있습니다.
적합한 상황
- 데이터를 정렬된 순서로 유지하면서 빠른 탐색, 삽입, 삭제 연산이 필요한 경우
- 데이터가 계속 변경되는 동적인 상황에서 사용할 수 있는 자료구조가 필요한 경우
부적합한 상황
- 데이터가 정렬된 상태로 고정되어 있고, 탐색만 수행하는 경우(이 경우 정렬된 배열이 더 적합합니다)
- 최악의 경우 시간 복잡도가 높아지는 경우를 허용할 수 없는 경우(균형 이진 탐색 트리를 고려해야 합니다)
사용 시 주의사항:
- 트리가 최악의 경우에 높이가 N이 되는 것을 방지하기 위해 균형을 유지해야 합니다. 균형 이진 탐색 트리를 사용하거나, 노드를 삽입할 때 트리를 재균형화하는 작업을 수행해야 합니다.
- 트리를 순회하거나 탐색할 때 재귀적 방법을 사용하면 쉽게 구현할 수 있지만, 스택 오버플로우가 발생할 수 있으므로 반복적 방법을 사용하는 것이 좋습니다.
- 이진 탐색 트리에서 데이터를 삭제할 때, 삭제할 노드가 두 개의 자식 노드를 갖는 경우에는 오른쪽 서브트리의 최소값 노드(후계자 노드)로 대체하거나 왼쪽 서브트리의 최대값 노드(선행자 노드)로 대체해야 합니다. 이렇게 하면 이진 탐색 트리의 성질이 유지됩니다.
- 이진 탐색 트리의 탐색, 삽입, 삭제 연산의 성능은 트리의 높이에 의존적입니다. 따라서 균형 이진 탐색 트리를 사용하거나, 노드를 삽입할 때 트리를 재균형화하는 작업을 수행해야 합니다.
- 이진 탐색 트리를 사용할 때, 중복되는 데이터를 처리하는 방법을 결정해야 합니다. 중복 데이터를 허용하지 않는 경우, 트리에 이미 존재하는 값이 들어오면 무시하거나, 트리의 노드에 카운트 값을 추가하여 중복 데이터의 개수를 기록할 수 있습니다. 중복 데이터를 허용하는 경우, 왼쪽 서브트리에 중복 데이터를 저장하는 등의 방법으로 처리할 수 있습니다.
구현
JS
반복문으로 구현
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new TreeNode(value);
if (this.root === null) {
this.root = newNode;
return;
}
let currentNode = this.root;
while (true) {
let direction = "right";
if (value < currentNode.value) {
direction = "left";
}
if (currentNode[direction] === null) {
currentNode[direction] = newNode;
break;
}
currentNode = currentNode[direction];
}
}
search(value) {
let currentNode = this.root;
while (currentNode !== null) {
if (value < currentNode.value) {
currentNode = currentNode.left;
} else if (value > currentNode.value) {
currentNode = currentNode.right;
} else {
return true;
}
}
return false;
}
findMin() {
let current = this.root;
while (current.left !== null) {
current = current.left;
}
return current.value;
}
findMax() {
let current = this.root;
while (current.right !== null) {
current = current.right;
}
return current.value;
}
remove(value) {
this.root = this.removeNode(this.root, value);
}
removeNode(node, value) {
// 1. 노드가 null 일때
if (node === null) {
return null;
}
if (value < node.value) {
// 2. 지우려는 값이 노드의 값보다 작을 경우
node.left = this.removeNode(node.left, value);
return node;
} else if (value > node.value) {
// 3. 지우려는 값이 노드의 값보다 클 경우
node.right = this.removeNode(node.right, value);
return node;
} else {
// 4. 지우려는 값이 노드의 값과 같을때
if (node.left === null && node.right === null) {
// 4-1. 리프 노드일때
node = null;
return node;
}
if (node.left === null) {
// 4-2. 좌측 자식노드가 없는 경우
node = node.right;
return node;
} else if (node.right === null) {
// 4-3. 우측 자식노드가 없는 경우
node = node.left;
return node;
} else {
// 4-4. 지우려는 노드가 양쪽의 자식 노드를 모두 가지고 있는 경우
const minNode = this.findMinNode(node.right);
node.value = minNode.value;
node.right = this.removeNode(node.right, minValue.value);
return node;
}
}
}
findMinNode(node) {
if (node === null) {
return node;
}
while (node.left !== null) {
node = node.left;
}
return node;
}
// 중위 순회를 사용하여 트리의 노드 값을 문자열로 변환
inOrderTraversal(node, callback) {
if (node !== null) {
this.inOrderTraversal(node.left, callback);
callback(node.value);
this.inOrderTraversal(node.right, callback);
}
}
// 트리의 현재 모양을 출력
print() {
let result = "";
this.inOrderTraversal(this.root, (value) => {
result += value + " ";
});
console.log("트리: ", result.trim());
}
}
// Test cases
const bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(45);
bst.insert(60);
bst.insert(80);
console.log(bst.search(45)); // 출력: true
console.log(bst.search(100)); // 출력: false
console.log(bst.findMin()); // 출력: 20
console.log(bst.findMax()); // 출력: 80
bst.remove(20);
console.log(bst.findMin()); // 출력: 30
bst.remove(80);
console.log(bst.findMax()); // 출력: 70
// 삭제 테스트
const bst2 = new BinarySearchTree();
// 트리 생성
bst2.insert(50);
bst2.insert(30);
bst2.insert(20);
bst2.insert(40);
bst2.insert(70);
bst2.insert(60);
bst2.insert(80);
// 테스트 케이스 1: 리프 노드 삭제 (4-1)
bst2.remove(20);
console.log("케이스 1: 20 삭제 후 트리");
bst2.print(); // 20이 삭제된 트리 출력
// 테스트 케이스 2: 오른쪽 자식 노드만 가지고 있는 노드 삭제 (4-2)
bst2.remove(30);
console.log("케이스 2: 30 삭제 후 트리");
bst2.print(); // 30이 삭제된 트리 출력
// 테스트 케이스 3: 왼쪽 자식 노드만 가지고 있는 노드 삭제 (4-3)
bst2.remove(70);
console.log("케이스 3: 70 삭제 후 트리");
bst2.print(); // 70이 삭제된 트리 출력
// 테스트 케이스 4: 두 개의 자식 노드를 모두 가지고 있는 노드 삭제 (4-4)
bst2.remove(50);
console.log("케이스 4: 50 삭제 후 트리");
bst2.print(); // 50이 삭제된 트리 출력재귀적 구현
class TreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class RecursiveBinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
if (this.root === null) {
this.root = new TreeNode(value);
return;
}
this.insertNode(this.root, value);
}
insertNode(node, value) {
if (value < node.value) {
if (node.left === null) {
node.left = new TreeNode(value);
return;
}
return this.insertNode(node.left, value);
} else if (value > node.value) {
if (node.right === null) {
node.right = new TreeNode(value);
return;
}
return this.insertNode(node.right, value);
}
}
search(value) {
return this.searchNode(this.root, value);
}
searchNode(node, value) {
if (node === null) {
return false;
}
if (value < node.value) {
return this.searchNode(node.left, value);
} else if (value > node.value) {
return this.searchNode(node.right, value);
} else {
return true;
}
}
findMaxValue() {
if (this.root === null) {
return undefined;
}
return this.findMaxValueR(this.root);
}
findMaxValueR(node) {
if (node.right !== null) {
return this.findMaxValueR(node.right);
}
return node.value;
}
findMinValue() {
if (this.root === null) {
return undefined;
}
return this.findMinValueR(this.root);
}
findMinValueR(node) {
if (node.left !== null) {
return this.findMinValueR(node.left);
}
return node.value;
}
findMinNode(node) {
if (node !== null && node.left !== null) {
return this.findMinNode(node.left);
}
return node;
}
remove(value) {
if (this.root === null) {
return false;
}
this.root = this.removeNode(this.root, value);
}
removeNode(node, value) {
// 1 to left
if (value < node.value) {
node.left = this.removeNode(node.left, value);
return node;
} else if (value > node.value) {
// 2 to right
node.right = this.removeNode(node.right, value);
return node;
} else {
// 3 remove
// 3-1 leaf
if (node.left === null && node.right === null) {
node = null;
return node;
} else if (node.left === null) {
// 3-2 left null
node = node.right;
return node;
} else if (node.right === null) {
// 3-3 right null
node = node.left;
return node;
}
// 3-4 has two children node
const minNode = this.findMinNode(node.right);
node.value = minNode.value;
node.right = this.removeNode(node.right, minNode.value);
return node;
}
}
// 중위 순회를 사용하여 트리의 노드 값을 문자열로 변환
inOrderTraversal(node, callback) {
if (node !== null) {
this.inOrderTraversal(node.left, callback);
callback(node.value);
this.inOrderTraversal(node.right, callback);
}
}
// 트리의 현재 모양을 출력
print() {
let result = "";
this.inOrderTraversal(this.root, (value) => {
result += value + " ";
});
console.log("트리: ", result.trim());
}
}
// Test cases
const bst = new RecursiveBinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(70);
bst.insert(20);
bst.insert(45);
bst.insert(60);
bst.insert(80);
bst.print(); // 20이 삭제된 트리 출력
console.log(bst.search(45)); // 출력: true
console.log(bst.search(100)); // 출력: false
console.log(bst.findMinValue()); // 출력: 20
console.log(bst.findMaxValue()); // 출력: 80
bst.remove(20);
console.log(bst.findMinValue()); // 출력: 30
bst.remove(80);
console.log(bst.findMaxValue()); // 출력: 70
// 삭제 테스트
const bst2 = new RecursiveBinarySearchTree();
// 트리 생성
bst2.insert(50);
bst2.insert(30);
bst2.insert(20);
bst2.insert(40);
bst2.insert(70);
bst2.insert(60);
bst2.insert(80);
// 테스트 케이스 1: 리프 노드 삭제 (4-1)
bst2.remove(20);
console.log("케이스 1: 20 삭제 후 트리");
bst2.print(); // 20이 삭제된 트리 출력
// 테스트 케이스 2: 오른쪽 자식 노드만 가지고 있는 노드 삭제 (4-2)
bst2.remove(30);
console.log("케이스 2: 30 삭제 후 트리");
bst2.print(); // 30이 삭제된 트리 출력
// 테스트 케이스 3: 왼쪽 자식 노드만 가지고 있는 노드 삭제 (4-3)
bst2.remove(70);
console.log("케이스 3: 70 삭제 후 트리");
bst2.print(); // 70이 삭제된 트리 출력
// 테스트 케이스 4: 두 개의 자식 노드를 모두 가지고 있는 노드 삭제 (4-4)
bst2.remove(50);
console.log("케이스 4: 50 삭제 후 트리");
bst2.print(); // 50이 삭제된 트리 출력Python
이진 탐색 트리에 데이터 넣기
이진 탐색 트리 조건에 부합하게 데이터를 넣어야 함
class NodeMgmt:
def __init__(self, head):
self.head = head
def insert(self, value):
self.current_node = self.head
while True:
if value < self.current_node.value:
if self.current_node.left != None:
self.current_node = self.current_node.left
else:
self.current_node.left = Node(value)
break
else:
if self.current_node.right != None:
self.current_node = self.current_node.right
else:
self.current_node.right = Node(value)
break
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)이진 탐색 트리 탐색
class NodeMgmt:
def __init__(self, head):
self.head = head
def insert(self, value):
self.current_node = self.head
while True:
if value < self.current_node.value:
if self.current_node.left != None:
self.current_node = self.current_node.left
else:
self.current_node.left = Node(value)
break
else:
if self.current_node.right != None:
self.current_node = self.current_node.right
else:
self.current_node.right = Node(value)
break
def search(self, value):
self.current_node = self.head
while self.current_node:
if self.current_node.value == value:
return True
elif value < self.current_node.value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return Falseclass NodeMgmt:
def __init__(self, head):
self.head = head
def insert(self, value):
self.current_node = self.head
while True:
if value < self.current_node.value:
if self.current_node.left != None:
self.current_node = self.current_node.left
else:
self.current_node.left = Node(value)
break
else:
if self.current_node.right != None:
self.current_node = self.current_node.right
else:
self.current_node.right = Node(value)
break
head = Node(1)
BST = NodeMgmt(head)
BST.insert(2)
BST.insert(3)
BST.insert(0)
BST.insert(4)
BST.insert(8)
BST.search(-1)이진 탐색 트리 삭제
- 매우 복잡함. *경우를 나누어서 이해하는 것이 좋음
Leaf Node 삭제
- Leaf Node: Child Node 가 없는 Node
- 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.
Child Node 가 하나인 Node 삭제
-
삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.
Child Node 가 두 개인 Node 삭제
-
삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
-
삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
삭제할 Node의 오른쪽 자식중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키게 할 경우
- 삭제할 Node의 오른쪽 자식 선택
- 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
- 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
- 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
- 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
- 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함
이진 탐색 트리 삭제 코드 구현과 분석
삭제할 Node 탐색
-
삭제할 Node가 없는 경우도 처리해야 함
-
이를 위해 삭제할 Node가 없는 경우는 False를 리턴하고, 함수를 종료 시킴
# def delete(self, value):
searched = False
self.current_node = self.head
self.parent = self.head
while self.current_node:
if self.current_node.value == value:
searched = True
break
elif value < self.current_node.value:
self.parent = self.current_node
self.current_node = self.current_node.left
else:
self.parent = self.current_node
self.current_node = self.current_node.right
if searched == False:
return False
### 이후부터 Case들을 분리해서, 코드 작성Case1: 삭제할 Node가 Leaf Node인 경우
# self.current_node 가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태
if self.current_node.left == None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = None
else:
self.parent.right = None
del self.current_nodeCase2: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
if self.current_node.left != None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = self.current_node.left
else:
self.parent.right = self.current_node.left
elif self.current_node.left == None and self.current_node.right != None:
if value < self.parent.value:
self.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.rightCase3-1: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 왼쪽에 있을 때)
- 기본 사용 가능 전략
- **삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.**
- 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
- 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
- 경우의 수가 또다시 두가지가 있음
- **Case3-1-1:** 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- **Case3-1-2:** 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
- 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임
if self.current_node.left != None and self.current_node.right != None: # case3
if value < self.parent.value: # case3-1
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.left = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.change_node.leftCase3-2: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽에 있을 때)
- 기본 사용 가능 전략
- **삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.**
- 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
- 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
- 경우의 수가 또다시 두가지가 있음
- **Case3-2-1:** 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- **Case3-2-2:** 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
- 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻이기 때문임
else:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.right = self.change_node
self.change_node.left = self.current_node.left
self.change_node.right = self.current_node.right파이썬 전체 코드 구현
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class NodeMgmt:
def __init__(self, head):
self.head = head
def insert(self, value):
self.current_node = self.head
while True:
if value < self.current_node.value:
if self.current_node.left != None:
self.current_node = self.current_node.left
else:
self.current_node.left = Node(value)
break
else:
if self.current_node.right != None:
self.current_node = self.current_node.right
else:
self.current_node.right = Node(value)
break
def search(self, value):
self.current_node = self.head
while self.current_node:
if self.current_node.value == value:
return True
elif value < self.current_node.value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return False
def delete(self, value):
# 삭제할 노드 탐색
searched = False
self.current_node = self.head
self.parent = self.head
while self.current_node:
if self.current_node.value == value:
searched = True
break
elif value < self.current_node.value:
self.parent = self.current_node
self.current_node = self.current_node.left
else:
self.parent = self.current_node
self.current_node = self.current_node.right
if searched == False:
return False
# case1
if self.current_node.left == None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = None
else:
self.parent.right = None
# case2
elif self.current_node.left != None and self.current_node.right == None:
if value < self.parent.value:
self.parent.left = self.current_node.left
else:
self.parent.right = self.current_node.left
elif self.current_node.left == None and self.current_node.right != None:
if value < self.parent.value:
self.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.right
# case 3
elif self.current_node.left != None and self.current_node.right != None:
# case3-1
if value < self.parent.value:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.left = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.change_node.left
# case 3-2
else:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
self.parent.right = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.current_node.left
return True참고: http://ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html
파이썬 전체 코드 테스트
- random 라이브러리 활용
- random.randint(첫번째 숫자, 마지막 숫자): 첫번째 숫자부터 마지막 숫자 사이에 있는 숫자를 랜덤하게 선택해서 리턴
- 예: random.randint(0, 99): 0에서 99까지 숫자중 특정 숫자를 랜덤하게 선택해서 리턴해줌
# 0 ~ 999 숫자 중에서 임의로 100개를 추출해서, 이진 탐색 트리에 입력, 검색, 삭제
import random
# 0 ~ 999 중, 100 개의 숫자 랜덤 선택
bst_nums = set()
while len(bst_nums) != 100:
bst_nums.add(random.randint(0, 999))
# print (bst_nums)
# 선택된 100개의 숫자를 이진 탐색 트리에 입력, 임의로 루트노드는 500을 넣기로 함
head = Node(500)
binary_tree = NodeMgmt(head)
for num in bst_nums:
binary_tree.insert(num)
# 입력한 100개의 숫자 검색 (검색 기능 확인)
for num in bst_nums:
if binary_tree.search(num) == False:
print ('search failed', num)
# 입력한 100개의 숫자 중 10개의 숫자를 랜덤 선택
delete_nums = set()
bst_nums = list(bst_nums)
while len(delete_nums) != 10:
delete_nums.add(bst_nums[random.randint(0, 99)])
# 선택한 10개의 숫자를 삭제 (삭제 기능 확인)
for del_num in delete_nums:
if binary_tree.delete(del_num) == False:
print('delete failed', del_num)
Move fast & break things