5.2 Data Types

We need to define data types for AVL trees like we did for BSTs. AVL tree nodes contain all the fields that a BST node does, plus a field recording its balance factor:

146. <AVL node structure 146> =
/* An AVL tree node. */
struct avl_node 
  {
    struct avl_node *avl_link[2];  /* Subtrees. */
    void *avl_data;                /* Pointer to data. */
    signed char avl_balance;       /* Balance factor. */
  };

This code is included in 143.

We're using avl_ as the prefix for all AVL-related identifiers.

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