まあざっくりいうと 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