Two binary search trees contains exactly the same number of

Two binary search trees contains exactly the same number of entries of information but in different orders.
Do they give the same performance in terms of key searching?
If not, why?

Solution

To implement a BST that stores some data with each key, we would use the following class definitions (changes are in red):