(a) Insert into an initially empty binary search tree ...



The Binary Search Tree Property

Each node of a Binary Search Tree (BST) stores a piece of data, called the key . Each node has below it a left subtree and a right subtree. The topmost node is called the root and a node with no subtrees is called a leaf.

The most important property of a BST is that for a node with key k , every key in the left subtree is less than k and every key in the right subtree is greater than k.

| |

[pic]

| | | |

Searching in a Binary Search Tree

To search for a key k in a Binary Search Tree (BST), we start at the root node:

• If k is less than the root's key, we descend to the left.

• If k is greater than the root's key, we descend to the right.

Then we repeat the procedure from our new location and continue to descend through the tree. We finally stop when either

• we find k in a node, or

• we can't go down any farther, in which case k is not in the tree.

[pic]

Balanced trees

Note that, in the worst case, a search will follow the longest path from the root to a leaf. A tree is balanced if all root-to-leaf paths are short. Balanced trees are usually short and wide.

1. Insert into an initially empty binary search tree items with the following keys (in this order): 30, 40, 23, 58, 48, 26, 11, 13. Draw the tree after each insertion.

Solution:

[pic]

2. A different binary search tree results when we try to insert the same sequence in an empty binary tree in a different order. Give an example of this with at least 5 elements.

[pic]

3. Consider binary tree that have single characters stored at each internal node. Draw one binary tree that will spell out the phrase: ANUPSIDEDOWNTREE when nodes are visited in preorder, and UNPADIESDNWTOERE when visited in inorder. (Draw only one tree!)

[pic]

[pic]

4. What is an Abstract Data Type? How is it different from an Data Structure? How are ADTs specified in Java?

5. What are the preorder, inorder, and postorder traversals of the binary tree below:

M

G T

D K R W

A H L V

U

[pic]

6. Draw the complete binary tree that is formed when the following values are inserted in the order given: 4, 13, 5, 3,7,30.

[pic]

7. Arrange nodes that contain the letters:A,C,E,L,F,V and Z into two binary search trees:

a). one that has max height,

b). one that has min height.

[pic]

8. Beginning with an empty binary search tree, what binary search tree is formed when you insert the following values in the order given?

a) W,T,N,J,E,B,A

b) W,T,N,A,B,E,J

c) A,B,W,J,N,T,E

[pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download