MLib Alpha 1 API Reference

AVL Trees

this header file contains the declaration of types and functions used to manage generic AVL balanced binary trees. These can be used to build more complex mapping containers.

AVL trees are very fast at lookup and insertion, and a bit slower at deletion (removing one node may need up to log2(depth) rotations).

This interface is intentionally small and simple. We do not support iterators, deep copies of trees, etc..

M_AvlNode


  typedef struct M_AvlNodeRec_*   M_AvlNode;

a handle to a generic AVL tree node. see M_AvlNodeRec

M_AvlNodeRec


  typedef struct M_AvlNodeRec_
  {
    M_AvlNode  links[2];
    M_Int8     balance;
    M_Byte     cache;
    M_UShort   pad;

  } M_AvlNodeRec;

the generic AVL node structure. It is normally derived by more complete types..

fields

links	handles to the left and right childs for this node
balance	avl node's current balance (-1, 0 or +1)
cache	this field is used internally to reduce node comparisons during insertions and removals..
pad	ignored field. used for padding (on 32-bit systems)

M_AvlInsertionRec


  typedef struct M_AvlInsertionRec_
  {
    M_AvlNode*  pnode;
    M_AvlNode*  protate;

  } M_AvlInsertionRec, *M_AvlInsertion;

a structure used during AVL tree insertion

m_avl_tree_insert_prologue


  MLIB_API(void)
  m_avl_tree_insert_prologue( M_AvlInsertion  insert,
                              M_AvlNode       new_node );

this function is called to rebalance the tree after an insertion was performed.

input

protate	parent pointer to the rotation node
new_node	new node created by the insertion

m_avl_tree_remove_prologue


  MLIB_API(M_AvlNode)
  m_avl_tree_remove_prologue( M_AvlRemoval  remove );

inserts a new node for a given lookup key in a generic AVL tree.

this function can also be used to reset the node corresponding to a given key.

input

proot	pointer to root tree node
key	lookup key
compare	comparison function
compare_data	user-provided data for the comparison function

return

handle of removed node. NULL if the key wasn't found

note

when the tree doesn't contain the lookup key, this function does nothing and returns NULL in '*pswap'

otherwise, it removes the key node from the tree, and returns its handle in '*pswap'. The caller must destroy the node itself.

generated on Tue Oct 09 23:59:46 2001