1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binary Search tree

  1. Aug 10, 2014 #1

    Maylis

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    Binary search trees

    In these problems you will set up a binary search tree and write some associated functions that make
    the search tree useful.

    Loading the data file students.mat (downloaded with this assignment) places a cell array called
    Students in the workspace. Students contains a list of student names and corresponding ID
    numbers. In this first task, you will write a function to insert a student's name and ID number
    into a binary search tree keyed to the ID numbers. Your function will have the declaration line

    Code (Text):
    function newTree = bstInsert(bst, rootInd, name, idNumber)
    The inputs are
    1. bst: a structure array with fieldnames
    ##\bullet## name
    ##\bullet## ID
    ##\bullet## left
    ##\bullet## right
    (very similar to what was described in the lecture videos) representing the binary search tree.
    You may assume that the struct array is not empty and that the root of the binary search
    tree is the first element of the array.
    2. rootInd: the current root index
    3. name: the name to be inserted into the search tree
    4. idNum: the ID number to be inserted into the search tree

    Remember that a new element with the name and ID number to be inserted must be appended
    to the struct array bst before any elements of bst can be modi ed to point to its index.

    The most natural way to write this function is with a recursive implementation that simply com-
    pares the ID number to a current node, and based on the result of that comparison calls itself
    recursively on the left or right subtree of the current node.

    Note: For this problem, use the convention that if a key to be inserted is equal to an existing
    key, the key to be inserted will be placed in the left subtree of the existing key.
    The following code is useful for testing bstInsert. It initializes a binary search tree with the rst
    row of the cell array Students and uses bstInsert to place the remainder of the student names
    and ID numbers in the search tree.
    Code (Text):
    load students;
    studentTree = struct('name',Students{1,1},...
    'ID',Students{1,2},...
    'left',0,...
    'right',0);

    for k = 2:size(Students,1)
    studentTree = bstInsert(studentTree,1,Students{k,1},Students{k,2});
    end
    It may also be useful to modify the function bstinorder that was made available along with the
    lecture videos to view the elements of the binary search tree you create.


    2. Relevant equations



    3. The attempt at a solution
    This is the given code for bstinorder
    Code (Text):
    function bstinorder(tree,index)
    % Print the part of a tree under index using inorder traversal
    % Input the tree and the index
    % Assumes the fields are 'key', 'left' and 'right'

    % descend the left subtree
    if tree(index).left ~=0
      bstinorder(tree,tree(index).left)
    end

    % print current key when there is none smaller
    disp(tree(index).key);

    % descend the right subtree
    if tree(index).right ~=0
      bstinorder(tree,tree(index).right)
    end
    The studentTree structure array only contains one student

    Code (Text):
    studentTree =

         name: 'Jim'
           ID: 19907875
         left: 0
        right: 0
    Here is my modification.
    Code (Text):
    function newTree = bstInsert(bst, rootInd, name, idNumber)
    % Print the part of a tree under index using inorder traversal
    % Input the tree and the index
    % Assumes the fields are 'key', 'left' and 'right'

    % descend the left subtree
    if bst(rootInd).left ~= 0
     newTree = bstInsert(bst,bst(rootInd).left,bst(rootInd).name,bst(rootInd).idNumber);
    end

    % print current key when there is none smaller
    disp(bst(rootInd).name);

    % descend the right subtree
    if bst(rootInd).right ~= 0
      newTree = bstInsert(bst,bst(rootInd).left,bst(rootInd).name,bst(rootInd).idNumber);
    end
    I know since Jim has a value of left and right of 0, he must be a leaf node. His student ID also is the largest one, so I know he most be the bottom right leaf nodes in the binary tree. However, I don't know how to append the next student to be his parent. I run this and get the following error

    Code (Text):
    Error in bstInsert (line 7)
    if bst(rootInd).left ~=0

    Output argument "newTree" (and maybe others) not assigned
    during call to
    "C:\Users\Owner\Documents\MATLAB\bstInsert.m>bstInsert".
     
  2. jcsd
  3. Aug 11, 2014 #2
    As written, your function will not assign a value to newTree unless either the left or right branch are zero.
    There must be more to bstInsert that you are not showing us.

    Also, the last two argument of bstInsert are not used in the code you show.

    You're also not telling us whether any of your disp's are being executed.
     
  4. Aug 11, 2014 #3

    Maylis

    User Avatar
    Gold Member

    I copy pasted the entire code I wrote for bstInsert. I modified it to at least include all input arguments
    Code (Text):
    function newTree = bstInsert(bst, rootInd, name, idNumber)
    % Print the part of a tree under index using inorder traversal
    % Input the tree and the index
    % Assumes the fields are 'key', 'left' and 'right'

    % descend the left subtree
    if bst(rootInd).left ~= 0 && bst(rootInd).ID > idNumber && strcmpi(bst(rootInd).name,name)
     newTree = bstInsert(bst,bst(rootInd).left,bst(rootInd).name,bst(rootInd).idNumber);
    end

    % print current key when there is none smaller
    disp(bst(rootInd).name);

    % descend the right subtree
    if bst(rootInd).right ~= 0 && bst(rootID).ID < idNumber && strcmpi(bst(rootInd).name,name)
      newTree = bstInsert(bst,bst(rootInd).left,bst(rootInd).name,bst(rootInd).idNumber);
    end
    The first student, Jim, does display

    Code (Text):
    Jim
    Error in bstInsert (line 7)
    if bst(rootInd).left ~= 0 && bst(rootInd).ID > idNumber

    Output argument "newTree" (and maybe others) not
    assigned during call to
    "C:\Users\Owner\Documents\MATLAB\bstInsert.m>bstInsert".
     
    Last edited: Aug 11, 2014
  5. Aug 11, 2014 #4
    If that's all of bstInsert, then the error message makes sense.
    What do you want to do when both left and right are zero? As it stands now, you print bst(rootInd).name ("Jim") and then return from bstInsert with no value to assign to newTree (hence the "not assigned" error).

    So what should you do when both left and right are 0?
     
    Last edited: Aug 11, 2014
  6. Aug 11, 2014 #5

    Maylis

    User Avatar
    Gold Member

    I got help from a grad student for my class, so the problem has been solved now.
     
  7. Aug 11, 2014 #6

    rcgldr

    User Avatar
    Homework Helper

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Binary Search tree
  1. Binary trees (Replies: 1)

Loading...