Thursday, October 22, 2020

binary search tree: tree search


まあざっくりいうと binary search tree では左の子ノードが必ず小さく、右の子ノードが必ず大きく、という相関関係があるので、探索が O(h) (hは木の高さ)でわりと早い、という法則があります。

例えば、

fun searchTree(x, k) {
    if x.key == k or x == null
        return x
    if x.key < k {
      searchTree(x.right, k)
    } else {
      searchTree(x.left, k)
   }
}

こんなかんじで、再帰的に探索したり、または whileかなんかでループで実装もできます。

まあそんなかんじで。

No comments:

Post a Comment