Библиотека Dlib. Пример использования шаблона класса binary_search_tree.

    Бинарное дерево поиска имеет две реализации: с использованием AVL бинарных деревьев binary_search_tree_kernel_1 и красно-черные бинарные деревья binary_search_tree_kernel_2. 

template <typename domain, 
          typename range, 
          typename mem_manager = memory_manager<char>::kernel_1a, 
          typename compare = std::less<domain> 
         > 
class binary_search_tree;

domain — тип ключа, должен позволять использовать специализации swap и  std::less, а также иметь конструктор по умолчанию.
range — тип значения, должен позволять использовать специализации swap и иметь конструктор по умолчанию.

#include <iostream>
#include <stdlib.h>
#include "../dlib/binary_search_tree.h"

//используем реализацию AVL бинарных деревьев
typedef dlib::binary_search_tree<int, int>::kernel_1a bst;


/*Функция печатает информацию о высоте дерева и количестве узлов*/
void printTreeInfo(const bst& tree)
{
   std::cout << "Size: "  << tree.size();
   std::cout << "  Height: " << tree.height() << "\n";
}

int main(int argc, char** argv)
{
    bst tree;

// добавляем в дерево числа от 1 до 99.
    for ( int i = 1; i<100; i++ ){
       int r = 0;
       int d = i;
       tree.add(d, r);
    }
 
// поиск значения по ключу
    int* f = tree[99];
    if ( f ) std::cout << "find\n";
   
    printTreeInfo(tree);

// очистка дерева
    tree.clear();
 
    printTreeInfo(tree);

// добавляем в дерево случайные числа в диапазоне от 0 до 99
    for ( int i = 1; i<100; i++ ){
       int r = 0;
       int d = rand() % 100;
       tree.add(d, r);
    }
   
    printTreeInfo(tree);
   
    return 0;
} 

Вывод программы:

find
Size: 99  Height: 7
Size: 0   Height: 0
Size: 99  Height: 8