Binary search tree, Data Structure & Algorithms

Assignment Help:

Objectives

The purpose of this project is to give you significant exposure to Binary Search Trees (BST), tree traversals, and recursive code.

Background

An arbitrary BST is seldom balanced. The left and right subtrees of a node may have different heights or contain different numbers of nodes, potentially leading to O( N ) performance for operations such as insert, find, and remove. There are several techniques for improving performance and insuring O( lg N ) performance by "balancing" the tree. Some of these will be discussed in class.

Description

In this project, you will explore balancing BST based on the weights of its subtrees. Here we define the weight of a BST to be the number of nodes in that tree. A node in a BST is weight-balanced if the weights of its left and right subtrees differ by no more than 1. A weight-balanced BST is a BST in which every node is weight-balanced. An important property of weight-balanced BST is that the value at any node, X, is a median of the values at all nodes in the subtree rooted at X.

How You're Program Works

Your program is invoked with two command line arguments. The first argument is the name of a file of integers (separated by whitespace) to read and insert into your BST. The second argument is the level to which your BSTs should be printed. Recall that the root is at level zero. For example

unix> ant run -Dargs="integers.dat 4"

Your program performs the following steps

  • Read the integers found in the file specified on the command line and insert them into an initially empty BST, let's call it T, ignoring duplicates.
  • Print the number of integers read from the file (including duplicates).
  • Print the number of nodes in T, the height and median value of T and then print the contents of T in level-order up to the level specified on the command line.
  • Weight-balance T according to the (admittedly inefficient) algorithm below.

    Weight Balance tree T

       find the median of T

       create a new BST, T', with a single node (the root) whose value is the median of T

       retrieve and insert elements of all nodes of T except the median into T'.

       replace T with T'           // T' has a weight-balanced root

       call this procedure to balance the left and right subtrees of T

Print the number of nodes in the weight-balanced tree, the height and median of the weight-balance tree and the contents of the tree in level-order up to the level specified on the command line.

Your Tasks

Design and implement a BST tree class which supports the required operations for this project. You are free to write your own BST from scratch or use some or all of the author's code as a starting point.

Project Requirements, Notes and Hints

    (R) Level-order printing

If the tree's height is less than the specified number of levels to print, then print the entire tree.

Tree nodes must be printed as ordered triples of values in the format ( x, y, z ), where x is the value found in the node's parent (print -1 for the root's parent), y is the value found in the node being printed and z is the weight of the tree rooted at that node.

Your level-order tree print must start with a label on a new line for each level, and print 4 nodes per line if there are more than 4 nodes at a given level.

The format for printing trees is shown in the sample output below.

(N) A level-order traversal requires use of a queue. Elements in the queue should contain appropriate data to print the required information.

(N) You are free to use any classes provided by the Java 6 API.

(N) The median of a set of values is the value "in the middle". If there are an even number of values, then there are two values "in the middle". In this project you should use the smaller of the two as the median.

(N) The algorithm given to weight-balance the tree is not the only possible algorithm, but we ask you to use this one so that your project output matches ours.

(H) Test your code with small files first, using non-random data then move to larger, more complex files.

(H) Some methods are better implemented as recursive functions, others as iterative functions. Choose your implementation carefully.

(H) By convention and for ease of coding, define the height of an empty tree as -1.

(H) Consider adding a new data member to each node which is the weight of the tree rooted at that node. The weight will make it easier to find the median and must be printed with each node. New nodes start with weight = 1. Nodes visited while finding the insertion point for a new node have their weight incremented if the integer being inserted is not a duplicate.

(H) Use the weight in the tree nodes described above to help find the median value. The median may be found with either a recursive or iterative algorithm.


Related Discussions:- Binary search tree

Analyze an algorithm, In order to analyze an algorithm is to find out the a...

In order to analyze an algorithm is to find out the amount of resources (like time & storage) that are utilized to execute. Mostly algorithms are designed to work along with inputs

Column major representation, Column Major Representation In memory th...

Column Major Representation In memory the second method of representing two-dimensional array is the column major representation. Under this illustration, the first column of

Binary search technique, Q. Describe the basic concept of binary search tec...

Q. Describe the basic concept of binary search technique? Is it more efficient than the sequential search?         Ans : The bin ary search technique:- This tec

Dijkstra's algorithm, Q. Explain Dijkstra's algorithm for finding the short...

Q. Explain Dijkstra's algorithm for finding the shortest path in the graph given to us.  Ans: The Dijkstra's algorithm: This is a problem which is concerned with finding

Time complexity, how to learn about time complexity of a particular algorit...

how to learn about time complexity of a particular algorithm

Discuss the brute force algorithm, Question 1 What do you mean by Amortiza...

Question 1 What do you mean by Amortization? Question 2 Explain the following Big Oh notation (O) Omega notation (Ω) Theta notation (Θ)   Question 3 Di

Determine in brief the painter algorithm, Determine in brief the Painter A...

Determine in brief the Painter Algorithm a) The farthest polygon, namely the rectangle PQRS, is stored first. (b) The next farthest, the quadrilateral ABCD, is superpo

Infix expression to postfix form using the stack function, Q. Convert the f...

Q. Convert the following given Infix expression to Postfix form using the stack function: x + y * z + ( p * q + r ) * s , Follow general precedence rule and suppose tha

Recursion, difference between recursion and iteration

difference between recursion and iteration

STACK, 5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and P...

5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and POP) using a singly linked list L. The operations PUSH and POP should still take O(1) time.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd