DS Project Documentation

BST & AVL tree Implementations

   

Supervisor: Dr Shimaa Ibrahim.

Supervisor assistant: Eng Mohamed Hassan.

Student: Mahmoud Sayed Abd El-Magied.

 

Project description:

The project contains two types of binary tree data structure implementations: - generic implementations -

• Binary Search Tree (BST)
• AVL tree

The implemented trees in this project hold always data as a combination of key and value.

The project enables users to do several operations

• Insert data: inserting new key and its value.
• Modify data: modifying value of specific key
• Insert or modify: insert key and its value if the key doesn’t exist, otherwise modifying the key’s value with the new value.
• Contains key: determine if the key exists or not.
• Get value: get the value if specific key.
• Print: print the data in non-decreasing order according to its keys.

 

Project components and tools:

I used Eclipse CDT to implement this project and used git as a version control system.

The project contains:

• Map header: contains the tree’s attributes and functions definitions.
• DS namespace: contains the tree class and its implementation.
• Map class: contains the tree attributes and functions implementations.

You can find the project here: BST generic implementation

 

Project classes:

• BST class

map
+ map() map(T1, T2) ~map() containsKey(T1) getValue() insert(T1, T2) modify(T1, T2) insertOrModify(T1, T2) print()	default constructor constructor destructor bool T1 void void void void
- _search(node*, T1) _insert(node*, node*, T1, T2) _modify(node*, T1, T2) _print(node*) _destroy(node*)	node* void void void void

• AVL class

map
+ map() map(T1, T2) ~map() containsKey(T1) getValue() insertAVL(T1, T2) modify(T1, T2) insertOrModifyAVL(T1, T2) print()	default constructor constructor destructor bool T1 void void void void
- _search(node*, T1) _insertAVL(node*, node*, T1, T2) _modify(node*, T1, T2) _print(node*) singleRotateLeft(node*) singleRotateRight(node*) doubleRotateLeft(node*) doubleRotateRight(node*) _destroy(node*)	node* void void void void