CHAPTER 51. C++ CHAPTER 51. C++
Hence, the lookup algorithm is straightforward: if the value that you are looking for is smaller than the current node’s key
value: move left, if it is bigger: move right, stop if the value required is equal to the node key’s value. That is why the
searching algorithm may search for numbers, text strings, etc, as long as a key comparison function is provided.
All keys have unique values.
Having that, one needs≈log 2 nsteps in order to find a key in a balanced binary tree withnkeys. This implies that≈ 10 steps
are needed≈ 1000 keys, or≈ 13 steps for≈ 10000 keys. Not bad, but the tree has always to be balanced for this: i.e., the
keys has to be distributed evenly on all levels. The insertion and removal operations do some maintenance to keep the tree
in a balanced state.
There are several popular balancing algorithms available, including the AVL tree and the red-black tree. The latter extends
each node with a “color” value to simplify the balancing process, hence, each node may be “red” or “black”.
Both GCC’s and MSVC’sstd::mapandstd::settemplate implementations use red-black trees.
std::setcontains only keys.std::mapis the “extended” version of std::set: it also has a value at each node.
MSVC
#include
// structure is not packed!
struct tree_node
{
struct tree_node Left;
struct tree_node Parent;
struct tree_node Right;
char Color; // 0 - Red, 1 - Black
char Isnil;
//std::pair Myval;
unsigned int first; // called Myval in std::set
const char second; // not present in std::set
};
struct tree_struct
{
struct tree_node *Myhead;
size_t Mysize;
};
void dump_tree_node (struct tree_node *n, bool is_set, bool traverse)
{
printf ("ptr=0x%p Left=0x%p Parent=0x%p Right=0x%p Color=%d Isnil=%d\n",
n, n->Left, n->Parent, n->Right, n->Color, n->Isnil);
if (n->Isnil==0)
{
if (is_set)
printf ("first=%d\n", n->first);
else
printf ("first=%d second=[%s]\n", n->first, n->second);
}
if (traverse)
{
if (n->Isnil==1)
dump_tree_node (n->Parent, is_set, true);
else
{
if (n->Left->Isnil==0)
dump_tree_node (n->Left, is_set, true);
if (n->Right->Isnil==0)
dump_tree_node (n->Right, is_set, true);
};
};
};