spChalk/O1-CompleteBinaryTree

A Generic Complete Binary Tree implementation , with O(1) Amortized Complexity in Insertion & O(1) Complexity in Removal of last node and Getting the last node.

Complete Binary Tree

A Generic Complete Binary Tree implementation , with O(1) Amortized Complexity in :

• Insertion

& O(1) Complexity in :

• Removal of last node

• Getting the last node

Usage

Run with Default Arguments

$ cd ~/O1-CompleteBT/CBT_Impl

Set Strings as tree items (Default):

$ make run

or

$ make run ITEM_TYPE=str

Set Integers as tree items:

$ make run ITEM_TYPE=int

Run with Custom Arguments

$ cd ~/O1-CompleteBT/CBT_Impl

$ make 

$ ./O1_cbt  <size_of_tree>  <minimum_num_of_elements>  <maximum_num_of_elements>

Note : Running with default arguments, will create and print a Complete Binary Tree consisting of 22 nodes.
(size_of_tree = 22).
Then, there will be 100.000 , 1.000.000 and 10.000.000 insertions and removals in order to demonstrate O(1) Amortized Complexity.
(minimum_num_of_elements = 100.000 , maximum_num_of_elements = 10.000.000)

Clean

$ make clean

Check for memory leaks (Requires Valgrind installation)

$ make check