Java Reference
In-Depth Information
unbalanced, then insertion can be slowȌperhaps as slow as insertion into a linked
list. (See
Figure 13
.)
If a binary search tree is balanced, then adding an element takes O(log(n)) time.
If new elements are fairly random, the resulting tree is likely to be well balanced.
However, if the incoming elements happen to be in sorted order already, then the
resulting tree is completely unbalanced. Each new element is inserted at the end, and
the entire tree must be traversed every time to find that end!
Binary search trees work well for random data, but if you suspect that the data in your
application might be sorted or have long runs of sorted data, you should not use
a
binary search tree. There are more sophisticated tree structures whose methods
keep
trees balanced at all times. In these tree structures, one can guarantee that finding,
adding, and removing elements takes O(log(n)) time. To learn more about those
advanced data structures, you may want to enroll in a course about data structures.
726
727
Figure 13
An Unbalanced Binary Search Tree
