Chapter 13Binary Search TreesCopyright © 2005 Pearson Addison-Wesley. All rights reserved.13-2Chapter ObjectivesDefine a binary search tree abstract data structureDemonstrate how a binary search tree can be used to solve problemsExamine various binary search tree implementationsCompare binary search tree implementationsCopyright © 2005 Pearson Addison-Wesley. All rights reserved.13-3Binary Search TreesA binary search tree is a binary tree with the added property that for each node, the left child is less than the parent is less than or equal to the right childGiven this refinement of our earlier definition of a binary tree, we can now include additional operationsCopyright © 2005 Pearson Addison-Wesley. All rights reserved.13-4FIGURE 13.1 The operations on a binary search treeCopyright © 2005 Pearson Addison-Wesley. All rights reserved.13-5Listing 13.1Copyright © 2005 Pearson Addison-Wesley. All rights reserved.13-6Listing 13.1 (cont.) Copyright © 2005 Pearson Addison-Wesley. All rights reserved.13-7FIGURE 13.2 UML description of the BinarySearchTreeADTCopyright © 2005 Pearson Addison-Wesley. All rights reserved.13-8Implementing Binary Search Trees With LinksWe can simply extend our definition of...