이전 포스트에서 알아본 이진 검색 트리는 검색과 삽입 삭제 모두 O(log n)의 빠른 속도를 제공하지만, 원소의 입력 순서에 따라 이진 트리가 치우치게 되면 성능이 O(log n)으로 악화되는 문제가 있습니다. 이를 위해서는 이진 트리가 균형을 유지하도록 해야되는데, 이를 위해서는 별도로 트리가 균형잡히도록 변형시키거나, 삽입과 삭제 과정에서 자동적으로 균형을 맞춰주도록 해야 합니다. 이 중 후자를 자가 균형 이진 탐색 트리(self-balancing binary search tree)라고 합니다. 이러한 트리 구현에는 대표적으로 AVL 트리, 레드-블랙 트리 등이 있습니다. 하지만 이러한 트리는 구현하기가 상당히 까다롭다는 단점이 있습니다. 그래서 빠른 구현이 필요한 대회 등에서는, 다른 자가 균형 BST보다는 덜 효율적이지만 비교적 구현이 간단한 트리가 필요한데, 그 중 하나가 트립(treap)입니다. 이번 포스트에서는 이 트립을 알아보도록 하겠습니다.
-
트립의 정의
트립은 트리(tree)와 힙(heap)의 합성어입니다. 트립은 각 노드가 값이외의 별도의 우선순위(priority)를 가지고 있습니다. 트립은 값의 측면에서는 이진검색트리의 특성(왼쪽 트리는 자신보다 작은 값들, 오른쪽 트리는 자신보다 큰 값들)을 가지지만, 우선순위는 힙의 특성(부모의 우선순위는 자식의 우선순위 보다 높다)를 유지하게 됩니다. 이 우선순위 값은 입력 순서에 상관없이 랜덤한 값으로 주어집니다. 이렇게 만들어진 트립은우선순위 순서대로 값을 넣은 이진 탐색 트리와 동일하게 됩니다. 즉, 값의 입력 순서를 랜덤하게 해준 이진 탐색 트리라 볼 수 있습니다. 따라서 운이 안좋으면 치우쳐진 트리를 얻을 수도 있겠지만, 그러한 가능성은 낮습니다. -
트립의 구현
트립을 구현하기 전, 트립은 서브트리를 변화시키는 작업을 많이 해야 하기 때문에, 각 서브트리에 대한 참조를 얻을 수 있도록 정의를 추가해줍니다. 또한 우선순위 값도 랜덤으로 배치해주도록 합니다.struct BinaryTree<T: Comparable>: Equatable { private indirect enum BinaryTreeNode<T: Comparable>: Equatable { case none case some(BinaryTree<T>, T, BinaryTree<T>) } private var root: BinaryTreeNode<T> private let priority : UInt // 현재 노드의 우선순위 init() { root = .none priority = UInt.random(in: UInt.min...UInt.max) // 우선 순위를 랜덤으로 부여해준다. } // 현재 노드의 우선순위를 그대로 유지하면서 // 새로운 노드로 바꿔치기 하기 위한 생성자 private init(_ node: BinaryTreeNode<T>, _ priority: UInt) { self.root = node self.priority = priority } var value: T? { switch root { case .none: return nil case let .some(_, value, _): return value } } private(set) var left: BinaryTree? { set { // 내부적으로만 쓰는 setter기 때문에 // nil을 넣는 경우는 없어서 무시하도록 한다. guard let newValue = newValue else { return } switch self.root { case .none: return case let .some(_, current, right): self.root = .some(newValue,current,right) } } get { switch root { case .none: return nil case let .some(left, _, _): return left } } } private(set) var right: BinaryTree? { set { guard let newValue = newValue else { return } switch self.root { case .none: return case let .some(left, current, _): self.root = .some(left,current,newValue) } } get { switch root { case .none: return nil case let .some(_, _, right): return right } } } // 양쪽 서브트리를 한꺼번에 구하기 위한 변수 private(set) var subTrees: (BinaryTree<T>, BinaryTree<T>)? { set { guard let newValue = newValue else { return } switch self.root { case .none: return case let .some(_, current, _): self.root = .some(newValue.0,current,newValue.1) } } get { switch root { case .none: return nil case let .some(left, _, right): return (left,right) } } } }트립은 여전히 이진 탐색 트리이기 때문에, 값을 찾거나 순회하는 알고리즘은 완전히 동일합니다. 바뀌는 것은 삽입과 삭제 부분입니다.
삽입을 하는 경우, 이진 탐색 트리의 삽입 조건뿐 아니라, 우선순에 대한 규칙을 준수해야 하는데, 다음 두가지 경우 중 하나가 됩니다. (삽입 하려는 값이 들어있는 노드를 newNode, 기존 이진 탐색 트리의 루트를 root라 하겠습니다.)
-
newNode.priority < root.priority: 힙 조건을 만족시키기 때문에, 하위 트리에 값을 삽입하면 됩니다. 어느쪽 트리에 넣을지는 값의 크기를 비교해서 결정하면 됩니다.
-
newNode.priority >= root.priority: 힙 조건을 만족시키지 않기 때문에, newNode가 새로운 root가 되어야 합니다. 이때 기존 트리를 새로 들어온 키를 기준으로 좌우로 나누는 작업이 필요합니다. 이를 위해 기존 insert 메소드를 다음과 같이 변경합니다.
extension BinaryTree { mutating func insert(_ value: T) { // 새로운 노드를 만들어 우선순위를 부여한다. var newNode:BinaryTree<T> = BinaryTree() newNode.root = .some(BinaryTree<T>(), value, BinaryTree<T>()) self._insert(newNode) } mutating private func _insert( _ newNode: BinaryTree<T>) { switch root { case .none: self = newNode case .some(var left, let current, var right): guard let value = newNode.value else { return } var newNode = newNode // 새로 들어온 노드의 우선순위가 // 현재 트리의 root보다 크거나 같을 경우 if self.priority <= newNode.priority { // 트리를 새로 삽입할 값 기준으로 쪼갠다. let splited = self.split(value) newNode.subTrees = splited self = newNode } else if current < value { // 우선순위가 낮을 경우에는 그대로 하위에 넣으면 된다. right._insert(newNode) self.right = right } else { left._insert(newNode) self.left = left } } } // 트리를 key를 기준으로 쪼갠다. mutating private func split(_ key: T) -> (BinaryTree<T>, BinaryTree<T>) { switch root { case .none: // 트리가 없는 경우, 빈 트리를 반환한다. return (BinaryTree(), BinaryTree()) case .some(var left, let current, var right): if current < key { // 현재 트리의 root값이 key 보다 작은 경우 let newRight = right.split(key) // 오른쪽 트리를 쪼갠다. self.right = newRight.0 return (self,newRight.1) } // 반대의 경우는 왼쪽 트리를 쪼갠다. let newLeft = left.split(key) self.left = newLeft.1 return (newLeft.0,self) } } }삭제를 하는 경우는, 삭제하고 합치는 과정에서 트립의 특성을 유지하도록 해줘야 합니다. 즉 merge함수만 수정해주면 됩니다.
extension BinaryTree { private func merge(with merged: BinaryTree<T>) -> BinaryTree<T> { // 합치려는 트리가 빈트리면 원본 그대로 반환한다. if merged.root == .none { return self } var origin = self var merged = merged switch origin.root { case .none: // 원본 트리가 비어있으면, 합치려는 트리 자체를 반환한다. return merged case let .some(_, _, right): // 합치려는 트리가 priority가 더 높은 경우 // merged가 새로운 root가 되게 만든다. if let left = merged.left, self.priority <= merged.priority { merged.left = origin.merge(with: left) return merged } // 그렇지 않은 경우, // 원래대로 오른쪽과 합친다. origin.right = right.merge(with: merged) return origin } } } -
-
트립 전체 구현
다음은 트립의 전체 구현 소스코드입니다.struct BinaryTree<T: Comparable>: Equatable { private indirect enum BinaryTreeNode<T: Comparable>: Equatable { case none case some(BinaryTree<T>, T, BinaryTree<T>) } private var root: BinaryTreeNode<T> private let priority : UInt init() { root = .none priority = UInt.random(in: UInt.min...UInt.max) } private init(_ node: BinaryTreeNode<T>, _ priority: UInt) { self.root = node self.priority = priority } var value: T? { switch root { case .none: return nil case let .some(_, value, _): return value } } private(set) var left: BinaryTree? { set { guard let newValue = newValue else { return } switch self.root { case .none: return case let .some(_, current, right): self.root = .some(newValue,current,right) } } get { switch root { case .none: return nil case let .some(left, _, _): return left } } } private(set) var right: BinaryTree? { set { guard let newValue = newValue else { return } switch self.root { case .none: return case let .some(left, current, _): self.root = .some(left,current,newValue) } } get { switch root { case .none: return nil case let .some(_, _, right): return right } } } private(set) var subTrees: (BinaryTree<T>, BinaryTree<T>)? { set { guard let newValue = newValue else { return } switch self.root { case .none: return case let .some(_, current, _): self.root = .some(newValue.0,current,newValue.1) } } get { switch root { case .none: return nil case let .some(left, _, right): return (left,right) } } } } extension BinaryTree { var list:[T] { switch root { case .none: return [] case let .some(left, current, right): return left.list + [current] + right.list } } func find(_ value: T) -> Bool { switch root { case .none: return false case let .some(left, current, right): if current == value { return true } else if current < value { return right.find(value) } else { return left.find(value) } } } mutating func insert(_ value: T) { var newNode:BinaryTree<T> = BinaryTree() newNode.root = .some(BinaryTree<T>(), value, BinaryTree<T>()) self._insert(newNode) } mutating private func _insert( _ newNode: BinaryTree<T>) { switch root { case .none: self = newNode case .some(var left, let current, var right): guard let value = newNode.value else { return } var newNode = newNode if self.priority <= newNode.priority { let splited = self.split(value) newNode.subTrees = splited self = newNode } else if current < value { right._insert(newNode) self.right = right } else { left._insert(newNode) self.left = left } } } mutating private func split(_ key: T) -> (BinaryTree<T>, BinaryTree<T>) { switch root { case .none: return (BinaryTree(), BinaryTree()) case .some(var left, let current, var right): if current < key { let newRight = right.split(key) self.right = newRight.0 return (self,newRight.1) } let newLeft = left.split(key) self.left = newLeft.1 return (newLeft.0,self) } } mutating func remove(_ value: T) { switch root { case .none: return case .some(var left, let current, var right): if current == value { self = left.merge(with: right) } else if current < value { right.remove(value) self.right = right } else { left.remove(value) self.left = left } } } private func merge(with merged: BinaryTree<T>) -> BinaryTree<T> { if merged.root == .none { return self } var origin = self var merged = merged switch origin.root { case .none: return merged case let .some(_, _, right): if let left = merged.left, self.priority <= merged.priority { merged.left = origin.merge(with: left) return merged } origin.right = right.merge(with: merged) return origin } } }
트립은 확률에 기대서 균형된 트리의 생성을 기대하는 알고리즘이며, 시간 복잡도 등의 특성은 BST와 동일합니다.