Binary Trees

[Dkob1]

Are the ones in bold right?

Given a search key k and a node v of a binary search tree T, drag and drop the proper action to each condition occurring in the find(k) operation:

- If a search key k is less than the key stored at node v, then the search continues in the left subtree.

- If a search key k is equal to the key stored at node v, then the search terminates.

- If a search key k is greater than the key stored at node v, then the search continues in the right subtree.

[helios]

- If a search key k is less than the key stored at node v, then the search continues in the left subtree.

- If a search key k is greater than the key stored at node v, then the search continues in the right subtree.

For these two, it depends on how the tree is defined. The most I can say is that if one branch is used for the < case, then the other branch must be used for the > case.

- Time spent per node in the search is O(n).

It depends on the complexity of the comparison function.

- Searching a key on the binary tree with height h runs in O(1) time.

Searching a binary tree takes O(h * m), where m is the complexity of the comparison function.

An AVL tree has the height-balance property such that for each internal node v of a binary tree T, the heights of the children of v differ by at most 2 .

Wikipedia says: "in an AVL tree, the heights of the two child subtrees of any node differ by at most one".

The answer I didn't comment on is correct.

[Dkob1]

It doesn't really say how a tree is defined or the type of complexity. I think it's just based on how it is generally because that is all that is stated in the question.

[helios]

Then it's an ill-stated problem.

[Dkob1]

ok thanks.