www.delorie.com/gnu/docs/avl/libavl_114.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

7.2 Data Types

Red-black trees need their own data structure. Otherwise, there's no appropriate place to store each node's color. Here's a C type for a color and a structure for an RB node, using the rb_ prefix that we've adopted for this module:

 
/* Color of a red-black node. */
enum rb_color 
{ RB_BLACK, /* Black. */ RB_RED /* Red. */ }; /* A red-black tree node. */ struct rb_node
{ struct rb_node *rb_link[2]; /* Subtrees. */ void *rb_data; /* Pointer to data. */ unsigned char rb_color; /* Color. */ };
This code is included in @refalso{192

The maximum height for an RB tree is higher than for an AVL tree, because in the worst case RB trees store nodes less efficiently:

 
/* Maximum RB height. */
#ifndef RB_MAX_HEIGHT
#define @cindex RB_MAX_HEIGHT macro
RB_MAX_HEIGHT 48
#endif
This code is included in @refalso{192

The other data structures for RB trees are the same as for BSTs or AVL trees.

Exercises:

1. Why is it okay to have both an enumeration type and a structure member named rb_color? [answer]


  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003