Binary Search Tree Homework - Setup BST & Write Functions

In summary: Red-Black tree https://en.wikipedia.org/wiki/Red%E2%80%93black_treeAVL tree https://en.wikipedia.org/wiki/AVL_tree2-3 tree https://en.wikipedia.org/wiki/2%E2%80%933_treeScapegoat tree https://en.wikipedia.org/wiki/Scapegoat_treeSplay tree https://en.wikipedia.org/wiki/Splay_treeTango tree https://en.wikipedia.org/wiki/Tango_treeTreap https://en.wikipedia.org/wiki/TreapWeight-balanced tree https://en.wikipedia.org/wiki/Weight-balanced_treeAA tree https://en.wikipedia.org/wiki/AA_tree
  • #1
gfd43tg
Gold Member
950
50

Homework Statement


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:
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:
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.


Homework Equations





The Attempt at a Solution


This is the given code for bstinorder
Code:
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:
studentTree = 

     name: 'Jim'
       ID: 19907875
     left: 0
    right: 0

Here is my modification.
Code:
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:
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".
 
Physics news on Phys.org
  • #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.
 
  • #3
I copy pasted the entire code I wrote for bstInsert. I modified it to at least include all input arguments
Code:
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:
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:
  • #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:
  • #5
I got help from a grad student for my class, so the problem has been solved now.
 
  • #6

1. What is a Binary Search Tree?

A Binary Search Tree (BST) is a data structure that is used to store and organize data in a hierarchical manner. It is a type of binary tree in which the value of each node is greater than all the values in its left subtree and less than all the values in its right subtree.

2. What is the purpose of setting up a Binary Search Tree?

The purpose of setting up a Binary Search Tree is to efficiently store and retrieve data in a sorted manner. This data structure is particularly useful for searching and sorting algorithms as it allows for faster access to data compared to other data structures like arrays or linked lists.

3. What are the basic functions that need to be written for a Binary Search Tree?

The basic functions that need to be written for a Binary Search Tree include insert, delete, and search. The insert function allows for adding new nodes to the tree in the correct position, the delete function removes nodes from the tree while maintaining its structure, and the search function allows for finding a specific node within the tree.

4. How do you set up a Binary Search Tree?

To set up a Binary Search Tree, you first need to create a Node class that will represent each node in the tree. Then, you can use this class to create the root node and add additional nodes by following the rules of a BST. This includes comparing the value of the new node to the value of the root node and placing it in the correct position.

5. What are the advantages of using a Binary Search Tree?

There are several advantages of using a Binary Search Tree. Firstly, it allows for efficient searching, inserting, and deleting operations with a time complexity of O(log n). Additionally, it maintains data in a sorted manner, making it useful for applications that require data to be sorted. It also allows for easy traversal of data in ascending or descending order.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
5K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
15
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
976
  • Engineering and Comp Sci Homework Help
Replies
4
Views
5K
  • Programming and Computer Science
Replies
3
Views
3K
Back
Top