part of its data as a function of its immediate children's
data. Furthermore, augmented data defined in this way can be
efficiently maintained as the tree changes over time.
part of its data as a function of its immediate children's
data. Furthermore, augmented data defined in this way can be
efficiently maintained as the tree changes over time.
For example, suppose we define the "size" of a node as the sum
of the "size" of its immediate children, plus 1. In such an
annotated BST with height H, we can find the node that would
For example, suppose we define the "size" of a node as the sum
of the "size" of its immediate children, plus 1. In such an
annotated BST with height H, we can find the node that would
struct abt_node node; // Embedded binary tree element.
int data; // Primary value.
int count; // Number of nodes in subtree,
struct abt_node node; // Embedded binary tree element.
int data; // Primary value.
int count; // Number of nodes in subtree,
// strcmp-type return value.
static int
compare_elements (const struct abt_node *a_, const struct abt_node *b_,
// strcmp-type return value.
static int
compare_elements (const struct abt_node *a_, const struct abt_node *b_,
reaugment_elements (struct abt_node *node_,
const struct abt_node *left,
const struct abt_node *right,
reaugment_elements (struct abt_node *node_,
const struct abt_node *left,
const struct abt_node *right,
{
int p_pos = p->down[0] ? node_to_element (p->down[0])->count : 0;
if (position == p_pos)
return node_to_element (p);
else if (position < p_pos)
{
int p_pos = p->down[0] ? node_to_element (p->down[0])->count : 0;
if (position == p_pos)
return node_to_element (p);
else if (position < p_pos)
((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
/* Node in an augmented binary tree. */
((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
/* Node in an augmented binary tree. */
{
struct abt_node *up; /* Parent (NULL for root). */
struct abt_node *down[2]; /* Left child, right child. */
{
struct abt_node *up; /* Parent (NULL for root). */
struct abt_node *down[2]; /* Left child, right child. */
{
struct abt_node *root; /* Tree's root, NULL if empty. */
abt_compare_func *compare; /* To compare nodes. */
{
struct abt_node *root; /* Tree's root, NULL if empty. */
abt_compare_func *compare; /* To compare nodes. */