Skip to content
Implementation of some Binary Search Trees in C
C Objective-C C++ CMake Shell
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
doc
src
test
.gitignore
.travis.yml
CMakeLists.txt
LICENSE.txt
README.md
install_dependencies.sh
test.sh
tree.png

README.md

BST

Implementation of some Binary Search Trees in C

Build Status

Trees

The following BST are implemented :

  • AVL
  • Red–black tree

The implementation is chosen at the compile time by specifying a MACRO. Check the CMakeLists.txt file.
By default AVL is chosen.

Collection

There is generic collection defined. The collection will contain some Element which is just a typedef int.

Tree drawing

ASCII

You can draw the tree in ASCII with the function show_collection_in_ascii :

        355
        / \
       /   \
      /     \
     /       \
    /         \
   81         444
  / \         / \
 /   \       /   \
28   284    /     \
          409     624
          /       / \
        400      /   \
               467   759

GraphViz

You can also draw with Graphviz. The function create_dot_file_for_collection create a dot file which can be interpreted by the dot command. Example :

# Create an SVG representing the tree
dot -Tsvg generatedFile > tree_in_svg.svg

tree_png

TODO

  • Use a key/value system to store element in collection
  • Implement remove element function
  • Benchmark
You can’t perform that action at this time.