Extended binary search tree

Introduction

This is a project form the discipline Basic Data Structures II, at Universidade Federal do Rio Grande do Norte (UFRN) in which we had to implement a binary search tree with some additional methods as described below:

• nthElement(int n) - Returns the element at position n (indexed by 1) in a in-order traversal.
• position(T key) - Returns the position of the element key in a in-order traversal.
• median() - Returns the node (or element) of the median of the tree.
• isPerfect() - Returns a Boolean indicating if the tree is perfect or not.
• isComplete() - Returns a Boolean indicating if the tree is complete or not.
• toString() - Returns a string with the level traversal of the tree.

Many of those methods would be simpler to be done by storing the in-order traversal of the tree in an array or other data structure, but that isn’t the most efficient way of doing that. To make it more efficient, each node stores the quantity of sub trees it has to the left and to the right. The definition of a node, in C, would be

typedef struct Node_t
{
    int key;
    struct Node_t *left;
    struct Node_t *right;
    // number of subtrees to the left and to the right
    int nLeft;
    int nRight;
} Node;

Building

To build it just clone the repository and enter the directory

$ git clone https://github.com/heartb1t/extended-bst
$ cd extended-bst

And then run make

$ make

To remove the binary and all of the object files, run

# remove binary and object files
$ make clean
# remove only object files
$ make clean_obj
# remove only binary file
$ make clean_bin

The resulting binary is bst.

Dependencies

To compile you’ll need:

• make
• g++ version 4.4+ or clang version 3.3+

On BSD, the package that contains g++ version 4.4+ is eg++ (usually), and you might need to install it via the package manager or ports. The default clang and make should work, though.

Running

bst receives two parameters:

• A file containing the level traversal of the tree, separated by either spaces of newlines, like the following

100 50 150 25 70 120 170

or

100
50
150
25
70
120
170

• And a file containing commands to be executed on the tree built from the file above, i.e.:

ENESIMO 3
POSICAO 4
COMPLETA
INSIRA 35
REMOVA 50

• To execute the program, go to the directory bst is located at (after building) and run it with:

$ ./bst <tree-file> <command-file>
# example usage: ./bst BINARYTREE.txt COMMANDS.txt

Supported commands

Here is a list of the supported commands and what they execute on the tree:

• ENESIMO N - Returns the N th of the in-order traversal of the tree. It call the function nthElement().
• POSICAO VAL - Returns the position of VAL on the in-order traversal. It calls the function position().
• MEDIANA - Returns the node (or element) of the median of the tree. It calls the function median().
• CHEIA - Returns a Boolean indicating if the tree is perfect or not. It calls the function isPerfect().
• COMPLETA - Returns a Boolean indicating if the tree is complete or not. It calls the function isComplete().
• IMPRIMA - Returns a string with the level traversal of the tree. It calls the function toString().
• INSIRA VAL - Inserts VAL into the tree. It calls the function insert().
• REMOVA VAL - Removes VAL from the tree. It calls the function remove().

Report

Here is a brief explanation of the solution approach to each of the functions required to be implemented with the asymptotic complexity analysis for each one of them.

Complexity analysis and approach to solution

Part of the project was to do a complexity analysis of each function mentioned in the introduction. Here is a brief overview of each function with its asymptotic complexity analysis.

• nthElement(int n): O(h) where h is the height of the tree. Seen as the in-order traversal of a binary search tree represents its elements in ascending order, we can define the nth element as the element with n-1 elements to its left. Using the amount of nodes to the left and the right, stored, respectively, in the variables nLeft and nRight, the operation can be done faster. In the best case, the element to be returned is the root of the tree, and hence its complexity is O(1). In the worst case, the element to be returned is a leaf in the smallest level of the tree, e O(h) operations of comparison are made.
• position(T key): O(h) where h is the height of the tree. Similarly to the nthElement, the comparisons are made considering the amount of nodes to the left and to the right, the only difference being that instead of returning the node we return the amount of elements that are to the left of the node being search for, including the its parent and the nodes left to its parent if it is to the right of the root. The best and worst cases work identically to nthElement.
• median(): O(h) where h is the height of the tree. Since each node has a variable containing the amount of nodes it has to its left and right, this method consists of a call to the function nthElement(nodes/2) with the parameter nodes which is equal to the number of nodes to the left and right of the root of the tree plus one (the root itself). The complexity is the same as nthElement.
• isPerfect(): O(n) where n is the number of nodes in the tree. Since a binary tree is perfect if and only if each node has two children if it is not a leaf or none otherwise, we simply need to test if all of the nodes have an equal amount of nodes in its left and right sub trees, if it differs at any node, than the tree is not perfect.
• isComplete(): O(n) where n is the number of nodes in the tree. It is made a level traversal on the tree and if a node has less than two children, the next level of the tree is the last. If there exists any node in the supposed last level that isn’t a leaf, then the tree is not complete. To know in which level we are, a variable that stores the amount of nodes expected in the next level is used, since a level always has double the amount of nodes of its previous level (except in the last level).
• toString(): O(n) where n is the number of nodes in the tree. It is necessary to access every node of the tree to print them. We utilize a stack as auxiliary data structure with spatial complexity O(n).

Authors

This project was developed by João Pedro de Amorim Paula and Max William S. Filgueira.