Binary Search Trees
Date: 02/06/2003 at 18:47:59 From: Ben Ullian Subject: C++ and AP Computer Science Exam Consider the following characters to be entered into an empty binary search tree. 'A' 'B' 'C' 'D' 'E' 'F' 'G' Which of the following sequences represent(s) an order of insertion that will result in a binary search tree where each node in the tree has the same number of nodes in its left and right subtrees? I. 'D' 'B' 'F' 'A' 'E' 'C' 'G' II. 'D' 'E' 'F' 'G' 'C' 'B' 'A' III. 'D' 'F' 'G' 'E' 'B' 'A' 'C' (A) I only (B) II only (C) III only (D) I and III only (E) I, II, and III No matter which order you use, you always end up with a binary tree that has even subtrees on both right and left sides. Since there are 7 elements, the tree should fully fill the first three levels. Without any significance to the letters (they are said to be "just characters"), the order doesn't seem to have any meaning. In terms of binary *search* trees, the process used is to divide a list into halves, choose the half with the thing you want, then split that into halves and select recursively until you end up with the thing you are looking for. This makes a type of tree (splitting) formation, but I do not think that this applies here because you don't know the character you are "searching" for.
Date: 02/07/2003 at 03:21:58 From: Doctor Jacques Subject: Re: C++ and AP Computer Science Exam Hi Ben, There are two different things to consider in binary trees: (1) How we search a binary tree for a given element. (2) How the tree is built incrementally by inserting elements. The question here relates to problem (2). Note that there may be many different search trees for the same data, depending on the order in which elements are inserted. The easy way to build a tree is best illustrated by considering the second sequence: 'D' 'E' 'F' 'G' 'C' 'B' 'A' We start by inserting D - there is no choice available in this, we just store D as the root: D Now we insert E. We do that by searching the tree for E; if we don't find it, we insert it at the next empty place where it would have to be. As E > D, we have to move right from D, and we find an empty place, so we store E there: D \ E To insert F, we start at D, move right, find E, move right (since F > E), and find an empty place, so we store F there: D \ E \ F The procedure for G is similar: D \ E \ F \ G To insert C, we start at D, and, since C < D, we look left and find an empty slot: D / \ C E \ F \ G To insert B, we follow the path D -> C -> (left) : D / \ C E / \ B F \ G And finally, we insert A by following the path D -> C -> B -> (left) D / \ C E / \ B F / \ A G You will notice that, in this case, some nodes do NOT have the same number of children in their left and right subtrees; for example node C has 2 children on the left subtree and none on the right subtree - we say that the tree is not "balanced." I'll let you use the same procedure for the other two insertion sequences. If the tree were balanced, there would be just 3 levels: we could find an element by doing at most three comparisons. In the example above, we may, in some cases, need 4 comparisons. If the tree is to be used intensively, it is best to have it balanced. The procedure described above is the "easy" way to insert elements. There are other, more complicated procedures that can be used to build the tree in such a way that it is almost balanced; this improves performance on searching. One of these methods involves re-arranging some nodes at each step in order to keep the tree balanced. You will find easily that (with this easy procedure) the worst case happens when the elements to be inserted are already in ascending or descending order - in that case, you end up with a linear structure, in which each node has only one child; it's no longer a "binary" tree. On the other hand, if the elements are inserted in random order, there is a good chance that the resulting tree will be decently balanced, but you can never be sure of that. Please feel free to write back if you want to discuss this further. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.