BST

Projects | 2019 | Links: GitHub

Optimized binary search tree implementation in C++.

Note: Binary search trees are not balanced by definition. This implementation does not guarantee O(log n) complexity when searching or deleting.

Features

• Pretty good performance compared to many other implementations on the internet.
• No recursion except for debugging purposes.
• Node-based on-delete balancing is supported. If you don’t need it, you can easily disable it.
• Unique / non-unique element insertion.
• 2 deletion methods are supported:
  1. With payload copying (efficient, when it’s size is less than 2 * sizeof(void*)).
  2. With pointer rearrangement.
• Debug tree printing with indentation.
• Lightweight, only one header file.