四十三庵

蔀の雑記帳

Binary Search Tree(二分探索木)

データ構造とアルゴリズム (新・情報 通信システム工学)

BSTとは

  • 任意の要素の取得がO(logN)で済む構造
  • 計算量がO(logN)ですむ証明が難しかった

実装

  • 最初Structでやろうとしたら、再帰にできなくて死んだ
  • ただ再帰でやることを思いついてしまうと、実装時間としてはそんなにかかんなかった
    • if文2回ネスト(2×2)する程度だし
  • counter変数作ろうしたら、ジェネリクス使うと、staticプロパティが持てないことに気づく
    • どうしようかなーと思ってSwift Algorithm Club見たらめちゃくちゃシンプルで感動した
  • deleteはなんか本のやり方で書こうとしたら上手くいかなかった
    • インスタンスが自殺するやり方はなさそう
  • AVL木の実装見てて急に気づいたが、削除する際は、parentから参照を削除、childから参照を削除すればOK
    • 親がいない→Node自体を削除

自分で書いたやつ

import Foundation

class BinarySearchTree<T: Comparable> {
    private(set) var value: T
    private(set) var parent: BinarySearchTree?
    private(set) var left: BinarySearchTree?
    private(set) var right: BinarySearchTree?
    public var count: Int {
      return (left?.count ?? 0) + 1 + (right?.count ?? 0)
    }
    
    init(value: T) {
        self.value = value
    }
    
    deinit {
        
    }
    
    func insert(value: T) {
        // 同じ値は挿入不可
        guard self.value != value else { print("this value is exist"); return }
        // ルートより小さかった場合、左の要素を探索
        if value < self.value {
            if let left = left {
                left.insert(value: value)
            } else {
                left = BinarySearchTree(value: value)
                left?.parent = self
            }
        } else {
            if let right = right {
                right.insert(value: value)
            } else {
                right = BinarySearchTree(value: value)
                right?.parent = self
            }
        }
    }
    
    @discardableResult func delete(node: BinarySearchTree) -> BinarySearchTree? {
        // 削除対象がルートと等しい、小さい、大きいの3パターンで分岐
        if node === self {
            // 削除する要素の子要素の状況で分岐
            if left == nil && right == nil {
                return nil
            } else if left == nil && right != nil {
                return right
            } else if left != nil && right == nil {
                return left
            } else {
                // 右の要素の最小値を返す処理
            }
        } else if node.value < self.value {
            node.left = delete(node: node.left!)
            return node
        } else if node.value > self.value {
            node.right = delete(node: node.right!)
            return node
        }
        return nil
    }
    
    private func isRoot(value: T) -> Bool {
        return parent == nil ? true : false
    }
}

var bst = BinarySearchTree(value: 3)
bst.insert(value: 2)
bst.insert(value: 5)
bst.insert(value: 1)
bst.insert(value: 7)
bst.insert(value: 8)
bst.insert(value: 2)
bst.right?.value
bst.left?.left?.value
bst.right?.right?.right?.right?.right?.value // Playgroundでデバッグした跡みたい
bst.count
bst.delete(node: bst)
bst