Treelib

AVL Tree Implementation in C & C++

About The Project

A Long while ago I had to write a Virtual Address Space Manager for primOS -
At the time, an AVL Tree seemed like a fitting data structure for searching & managing an address space,
since its height is kept to a certain minimum boundary, which is a very common operation

I did eventually find a working, open-source implementation online that fit the bill (See Acknowledgements Section),
I never had the time to research the inner-workings of AVL Trees.
This project is a Working, Tested, and Benchmarked Iterative-Only Generic Implementation of AVL Trees in C & C++

Project Structure

The project has the same structure as my other project util2, except that I added benchmarks & Proper Testing

Getting Started

Prerequisites

• CMake
• Working compiler toolchain, preferably clang
  Windows: You should use llvm
  Linux:
  1. installing-specific-llvm-version
  2. configuring-symlinks
  3. You Don't have to use LLVM, gcc works too

Building & (Maybe) Running

Downloading

If you're only interested in the library itself, i.e no Testing/Benchmarking:

git clone https://github.com/inonitz/tree/tree.git --branch onlylibrary desired_folder_path_from_cwd
cd desired_folder_path_from_cwd/tree

If you want to build Tests/Benchmarks Too:

git clone --recurse-submodules https://github.com/inonitz/tree/tree.git --branch master desired_folder_path_from_cwd
cd desired_folder_path_from_cwd/tree

Configuring

Because This project is somewhat big and building manually is cumbersome,
I Wrote build scripts build.sh, build.ps1 for Linux & Windows Respectively

By Default, The project will try to build EVERYTHING - If you do not want that,
add the following flags to your cmake invocation (Or If Building with the scripts, disable in your platforms' Script):

• -DTREELIB_BUILD_TESTS=OFF (Enabled By Default)
• -DENABLE_SANITIZER_ADDRESS=OFF (Enabled By Default)
• -DENABLE_SANITIZER_UNDEFINED=OFF (Enabled By Default)
• -DENABLE_SANITIZER_MEMORY=OFF (Enabled By Default)

Windows:

.\build.ps1 -Help
.\build.ps1 -BuildType release -LinkType shared -Action configure
.\build.ps1 -BuildType release -LinkType shared -Action build
.\build.ps1 -BuildType release -LinkType shared -Action runtests/runbench

Linux:

./build.sh --help
./build.sh release static configure
./build.sh release static build
./build.sh release static runtests/runbench

Usage

In Source Build

In your CMakeLists.txt:

add_subdirectory(your_directory/tree)

Also, Don't forget to link to the library:

target_link_libraries(your_target_executable/library PRIVATE TREELIB::treelib)

Out-Of-Source (Submodule/etc...) Build

git submodule add https://github.com/inonitz/tree your_dependency_folder/tree
git submodule init
git submodule update

In your CMakeLists.txt:

add_subdirectory(your_dependency_folder/tree)

Also, Don't forget to link to the library:

target_link_libraries(your_target_executable/library PRIVATE TREELIB::treelib)

Benchmarks

Benchmarks will be added soon enough, thanks to google benchmarks' Over engineering :)

Roadmap/TODO

• Modularize testing using add_test() with CTest
• Modularize Benchmarks using something similar to add_test
• Re-verify Benchmark for C Version
• the binaryTreeDeepCopy function @Line-102 needs to be finished. Function does nothing right now. Also add test for it

Contributing

If you have a suggestion, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement".

License

Distributed under the MIT License. See LICENSE file for more information.

Acknowledgements

• GoogleBenchmark
• GoogleTest
• CMocka
• CMake
• Intrusive AVL Tree by Eric Biggers

References

• Modern CMake
• Best-README
• AVL Tree Playlist by William Fiset
• Jenny's Data Structures & Algorithm Course
  • In particular, her videos regarding AVL Tree Rotations
• W3Schools AVL Trees
• There are many more to add, will be added soon.