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かなんかでループで実装もできます。

まあそんなかんじで。