3.18. C++
operator--andoperator++move the current node pointer to the predecessor or successor respectively,
i.e., the nodes which have the previous or next key.
The algorithms for all these operations are explained in [Cormen, Thomas H. and Leiserson, Charles E.
and Rivest, Ronald L. and Stein, Clifford,Introduction to Algorithms, Third Edition, (2009)].
The.end()iterator points to the dummy node, it has 1 inIsnil, which implies that the node has no
key and/or value. It can be viewed as a “landing zone” inHDD^33 and often calledsentinel[see N. Wirth,
Algorithms and Data Structures, 1985]^34.
The “parent” field of the dummy node points to the root node, which serves as a vertex of the tree and
contains information.
GCC
#include <stdio.h>
#include
struct map_pair
{
int key;
const char *value;
};
struct tree_node
{
int M_color; // 0 - Red, 1 - Black
struct tree_node M_parent;
struct tree_node M_left;
struct tree_node *M_right;
};
struct tree_struct
{
int M_key_compare;
struct tree_node M_header;
size_t M_node_count;
};
void dump_tree_node (struct tree_node *n, bool is_set, bool traverse, bool dump_keys_and_values⤦
Ç)
{
printf ("ptr=0x%p M_left=0x%p M_parent=0x%p M_right=0x%p M_color=%d\n",
n, n->M_left, n->M_parent, n->M_right, n->M_color);
void *point_after_struct=((char*)n)+sizeof(struct tree_node);if (dump_keys_and_values)
{
if (is_set)
printf ("key=%d\n", *(int*)point_after_struct);
else
{
struct map_pair *p=(struct map_pair *)point_after_struct;
printf ("key=%d value=[%s]\n", p->key, p->value);
};
};if (traverse==false)
return;if (n->M_left)
dump_tree_node (n->M_left, is_set, traverse, dump_keys_and_values);(^33) Hard Disk Drive
(^34) http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf