+
+ # O(n) in worst case, average is O(h) with h: tree height
+ #
+ # var tree = new BinTreeMap[Int, String]
+ # assert not tree.has_key(1)
+ # for i in [4, 2, 1, 5, 3] do tree[i] = "n{i}"
+ # assert not tree.has_key(0)
+ # assert tree.has_key(2)
+ # assert not tree.has_key(6)
+ redef fun has_key(key: K): Bool do
+ if is_empty then return false
+ var res = search_down(root.as(not null), key)
+ if res != null then
+ cache_node = res
+ return true
+ end
+ return false
+ end
+
+ private var cache_node: nullable N = null
+