DS Module 4
Binary Search Trees, Selection Trees,
Forests
BINARY SEARCH TREES
• Definition: A binary search tree is a binary tree. It may be
empty. If it is not empty, it satisfies the following properties:
1. Every element has a key, and no two elements have the
same key, that is, the keys are unique.
2. The keys in a nonempty left subtree must be smaller than
the key in the root of the subtree.
3. The keys in a nonempty right subtree must be larger than
the key in the root of the subtree.
4. The left and right subtrees are also binary search trees.
Searching A Binary Search Tree
Inserting Into A Binary Search Tree
Deletion From A Binary Search Tree
SELECTION TREES
• Suppose we have k ordered sequences, called runs, that are to be
merged into a single ordered sequence.
• Each run consists of some records and is in nondecreasing order of a
designated field called the key.
• Let n be the number of records in all k runs together. The merging
task can be accomplished by repeatedly outputting the record with
the smallest key.
• The smallest has to be found from k possibilities, and it could be the
leading record in any of the k runs.
• The most direct way to merge k runs is to make k-1 comparisons to
determine the next record to output.
• For k > 2, we can achieve a reduction in the number of comparisons
needed to find the next smallest element by using the selection tree
data structure. There are two kinds of selection trees: winner trees
and loser trees
Winner Trees
• A winner tree is a complete binary tree in
which each node represents the smallest of its
two children.
• Thus root node represents the smallest node
in the tree.
Loser Trees
• A selection tree in which each non leaf node
retains a pointer to the loser is called a loser
tree.
Forests
• A forest is a set of n ≥ 0 disjoint trees.
Example:
Fig 5.37 Three-tree forest
A E G
D H I
B C F
Transforming a forest into binary tree
• If T1, T2, T3, T4, ….., Tn is a forest of trees, then
the binary tree corresponding to this forest,
denoted by B(T1, T2, T3, T4, ….., Tn)
1. Is empty if n=0
2. Has root = root(T1), has left subtree=B(T11, T12,
T13, T14, ….., T1m ) where subtree=B(T11, T12, T13,
T14, ….., T1m are subtrees of root(T1) and has
right subtree = B(T2, T3, T4, ….., Tn)
• Binary tree representation of the forest of
Fig5.37
A
B E
C F G
D H
I
Forest traversals
Forest preorder
1. If F is empty then return
2. Visit the root of the first tree of F
3. Traverse the subtrees of the first tree in forest
preorder
4. Traverse the remaining trees of F in forest preorder
Forest inorder
1. If F is empty then return
2. Traverse the subtrees of the first tree in
forest inorder
3. Visit the root of the first tree of F
4. Traverse the remaining trees of F in forest
inorder
Forest postorder
1. If F is empty then return
2. Traverse the subtrees of the first tree in
forest postorder
3. Traverse the remaining trees of F in forest
postorder
4. Visit the root of the first tree of F