주제: 삽입, 삭제 작업에 용이한 데이터 구조
Binary Search Trees
- BST(Binary Search Trees), 이진 탐색 트리는 빠른 조회, 삽입 및 삭제 작업을 용이하게 하는 데이터 구조이다. 간단하게 설명하자면, 한쪽을 선택하면 다른 쪽의 가능성을 모두 무시하고 문제를 절반으로 줄일 수 있다.
규칙
- 왼쪽 자식의 값은 부모의 값보다 작야아 한다.
- 오른쪽 자식의 값은 부모의 값보다 크거나 같아야 한다.
- 이에따라 결과적으로 조회, 삽입 및 삭제는 평균 시간 복잡도 O(log n)을 가지며, 배열 및 연결 리스트와 같은 선형 데이터 구조보다 훨씬 빠르다.
Look up
- 노드를 방문할 때마다 두 가지 가정을 할 수 있다.
- 검색 값이 현재 값보다 작으면 왼쪽 하위 트리에 있다.
- 검색 값이 현재 값보다 크면 오른쪽 하위 트리에 있다.
- BST의 규칙을 활용하여 불필요한 검사를 피하고 결정을 내릴 때마다 검색 공산을 절반으로 줄여서 BST 노드 조회의 평균 시간 복잡도를 O(log n)을 보장할 수 있다.
Insertion
- 만약 배열의 맨 앞에 삽입할 때 다른 모든 요소가 한 위치씩 뒤로 이동하여 O(n) 시간 복잡도를 가지는 것이, BST의 규칙을 활용하여 삽입하면 평균 시간 복잡도 O(log n)을 보장할 수 있다.
Removal
- 노드에 자식이 있는 경우 복잡할 수 있지만, BST에서 요소를 제거하는 것은 평균 시간 복잡도 O(log n)을 보장할 수 있다.
결론
- Binary Search Tree는 결국 추가, 제거 및 조회 작업의 단계 수를 크게 줄여, 기존 배열보다 효율이 좋다.
구현
Node
import Foundation
public class BinaryNode<Element> {
public var value: Element
public var leftChild: BinaryNode?
public var rightChild: BinaryNode?
public init(value: Element) {
self.value = value
}
}
extension BinaryNode: CustomStringConvertible {
public var description: String {
diagram(for: self)
}
private func diagram(
for node: BinaryNode?,
_ top: String = "",
_ root: String = "",
_ bottom: String = ""
) -> String {
guard let node = node else {
return root + "nil\n"
}
if node.leftChild == nil && node.rightChild == nil {
return root + "\(node.value)\n"
}
return diagram(for: node.rightChild,top + " ", top + "┌──", top + "| " ) + root + "\(node.value)\n" + diagram(for: node.leftChild, bottom + "│ ", bottom + "└──", bottom + " ")
}
}
Binary Search Tree
기본 구조
public struct BinarySearchTree<Element: Comparable> {
public private(set) var root: BinaryNode<Element>?
public init() { }
}
extension BinarySearchTree: CustomStringConvertible {
public var description: String {
guard let root = root else { return "empty tree" }
return String(describing: root)
}
}Inserting elements
- BST 규칙에 따라, 왼쪽 자식 노드의 값은 현재 노드의 값보다 작아야 한다.
- 오른쪽 자식 노드의 값은 현재 노드의 값보다 크거나 같아야 한다.
extension BinarySearchTree {
public mutating func insert(_ value: Element) {
root = insert(from: root, value: value)
}
private func insert(from node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element> {
guard let node = node else {
return BinaryNode(value: value)
}
if value < node.value {
node.leftChild = insert(from: node.leftChild, value: value)
} else {
node.rightChild = insert(from: node.rightChild, value: value)
}
return node
}
}Finding elements
extension BinarySearchTree {
public func contains(_ value: Element) -> Bool {
var current = root
while let node = current {
if node.value = value {
return true
}
if value < node.value {
current = node.leftChild
} else {
current = node.rightChild
}
}
return false
}
}removing elements
- 리프 노드 제거
- 리프 노드를 제거하는 것은 간단하다. 단순하게 리프 노드를 분리하면 되기 때문이다.
- 하나의 자식 노드를 가진 노드 제거
- 하나의 자식 노드를 가진 노드를 제거할 때는 해당 노드의 자식 노드를 그 부모 노드와 연결해 주면 된다.
- 예를 들어, 왼쪽 자식 노드만을 가진 노드를 제거한다면, 왼쪽 자식 노드를 해당 노드의 부모 노드와 연결해주면 된다.
- 오른쪽 자식 노드만을 가진 경우도 동일하다.
- 두 개 이상의 자식 노드를 가진 노드 제거
- 제거한 노드에 대해 오른쪽 자식에서 가장 작은 값을 가진 노드를 찾아서 해당 노드의 값을 오른쪽 자식에서 가장 작은 값과 교체한다. 교체한 다음 제거할 노드를 제거 한다.
private extension BinaryNode {
var min: BinaryNode {
leftChild?.min ?? self
}
}
extension BinarySearchTree {
public mutating func remove(_ value: Element) {
root = remove(node: root, value: value)
}
private func remove(node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element>? {
guard let node = node else {
return nil
}
if value == node.value {
// 리프 노드 제거
if node.leftChild == nil && node.rightChild == nil {
return nil
}
// 하나의 자식 노드를 가진 노드 제거
if node.leftChild == nil {
return node.rightChild
}
if node.rightChild == nil {
return node.leftChild
}
// 노드의 자식이 여러개 있을 때
node.value = node.rightChild!.min.value
node.rightChild = remove(node: node.rightChild, value: node.value)
} else if value < node.value {
node.leftChild = remove(node: node.leftChild, value: value)
} else {
node.rightChild = remove(node: node.rightChild, value: value)
}
return node
}
}이진 트리가 이진 검색 트리인지 확인하는 함수
extension BinaryNode where Element: Comparable {
var isBinarySearchTree: Bool {
isBST(self, min: nil, max: nil)
}
private func isBST(_ tree: BinaryNode<Element>?, min: Element?, max: Element? ) -> Bool {
guard let tree = tree else {
return true
}
// tree 오른쪽 비교
if let min = min, tree.value <= min {
return false
// tree 왼쪽 비교
} else if let max = max, tree.value > max {
return false
}
return isBST(tree.leftChild, min: min, max: tree.value) && isBST(tree.rightChild, min: tree.value, max: max)
}
}Equatable을 만족하는 Binary Search Tree
extension BinarySearchTree: Equatable {
public static func == (lhs: BinarySearchTree, rhs: BinarySearchTree) -> Bool {
isEqual(lhs.root, rhs.root)
}
private static func isEqual<Element: Equatable>( _ node1: BinaryNode<Element>?, _ node2: BinaryNode<Element>?) -> Bool {
guard let node1 = node1, let node2 = node2 else {
return node1 == nil && node2 == nil
}
return node1.value == node2.value && isEqual(node1.leftChild, node2.leftChild) && isEqual(node1.rightChild, node2.rightChild)
}
}출처(참고문헌)
제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.
감사합니다
