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

GNU libavl 2.0.1

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

15.4.1 Steps 1 and 2: Search and Insert

We search much as before. Despite use of the parent pointers, we preserve the use of q as the parent of p because the termination condition is a value of NULL for p, and NULL has no parent. (Thus, q is not, strictly speaking, always p's parent, but rather the last node examined before p.)

Because of parent pointers, there is no need for variable z, used in earlier implementations of AVL insertion to maintain y's parent.

y = tree-&#62;pavl_root;
for (q = NULL, p = tree-&#62;pavl_root; p != NULL; q = p, p = p-&#62;pavl_link[dir]) 
{ int cmp = tree-&#62;pavl_compare (item, p-&#62;pavl_data, tree-&#62;pavl_param); if (cmp == 0) return &p-&#62;pavl_data; dir = cmp > 0; if (p-&#62;pavl_balance != 0) y = p; }
This code is included in @refalso{523

The node to create and insert the new node is based on that for PBSTs. There is a special case for a node inserted into an empty tree:

&#60;@xref{\NODE\, , Step 2: Insert PBST node; pbst =>.&#62; pavl,492}
n-&#62;pavl_balance = 0;
if (tree-&#62;pavl_root == n)
  return &n-&#62;pavl_data;
This code is included in @refalso{523

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