CIS 3223 Lab07 – Implementing Binary Search Trees in Matlab

-- This is Extra Credit Lab –  

DUE: (before the next lab, 10:30am Friday, March 21, 2008)

 

Binary Search Trees (BST) in Matlab

 

The natural implementation of BST is using pointers. The challenge in this lab is to implement Binary Search Trees using Matlab that does not support pointers. How could we do it? One approach is to define array key that stores key values of tree nodes. Index i in array key defines the position of a node in the tree as follows: if node with index i is a parent node, its left child has index 2i and its right child has index 2i+1. Root node has index i. key[i] is the key value of i-th node.

 

TASKS

  1. (20 p) Write the pseudocode suited for Matlab BST implementation of Traversal, Insert and Delete operations.

 

  1. Write Matlab code that implements

 

    1. (10 p) Traversal (input is BST, output the sorted list of keys)
    2. (15 p) Insert (input is BST and the new number, output is updated BST)
    3. (20 p) Delete. (input is BST tree and the number to be deleted, output is updated BST. NOTE: this is the most difficult problem)

 

  1. (15 p) Generate a sequence of 10 random numbers. Starting from the empty tree, insert the 10 numbers in the tree, one by one using your matlab function. List the generated numbers and plot the resulting tree.

 

    1. Generate BST by hand.
    2. Generate the BST using insert Matlab function.
    3. Compare if the resulting BSTs – they should be the same

 

  1. (10 p) Use the traversal function to list the 10 numbers in a sorted order. Check if the result is correct. Report the results.

 

  1. (10 p) Delete the smallest, then the 5-th smallest, and then the largest elements from the BST using delete routing. Report the results

 

    1. Delete the nodes from the BST by hand.
    2. Delete the nodes using delete Matlab function.
    3. Compare if the resulting BSTs – they should be the same