< Free Open Study > |
After studying this chapter, you should be able to
Define and use the following terminology:
Binary tree
Binary search tree
Ancestor
Root
Parent
Child
Descendant
Level
Height
Subtree
Define a binary search tree at the logical level
Show what a binary search tree would look like after a series of insertions and deletions
Implement the following binary search tree algorithms in C++:
Inserting an element
Deleting an element
Retrieving an element
Modifying an element
Copying a tree
Traversing a tree in preorder, inorder, and postorder
Discuss the Big-O efficiency of a given binary search tree operation
Describe an algorithm for balancing a binary search tree
Show how a binary tree can be represented in an array, with implicit positional links between the elements
Define the terms full binary tree and complete binary tree
So far, we have discussed some of the advantages of using a linear linked list to store sorted information. One drawback of using a linear linked list, however, is the time it takes to search a long list. A sequential or linear search of (possibly) all the nodes in the entire list is an O(N) operation. In Chapter 3, we saw how a binary search could find an element in a sorted list stored sequentially in an array; this kind of search is an O(log_{2}N) operation. It would be nice if we could binary search a linked list, but no practical way exists to find the midpoint of a linked list of nodes. We can, however, reorganize the list's elements into a linked structure that is just perfect for binary searching: the binary search tree. The binary search tree provides us with a structure that retains the flexibility of a linked list but allows for quicker O(log_{2}N) access to any node in the list.
This chapter introduces some basic tree vocabulary and then develops the algorithms and implementations of the operations needed to use a binary search tree.
< Free Open Study > |
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) |