doc/srcdoc/gavl.tmpl

   1 <!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook V4.1//EN"[]>
   2
   3 <book id="GAVLdoc">
   4  <bookinfo>
   5   <title>Generic AVL Tree Implementation (GAVL)</title>
   6
   7   <authorgroup>
   8    <author>
   9     <firstname>Pavel</firstname>
  10     <surname>Pisa</surname>
  11     <affiliation>
  12      <address>
  13       <email>pisa@cmp.felk.cvut.cz</email>
  14      </address>
  15     </affiliation>
  16    </author>
  17   </authorgroup>
  18
  19   <copyright>
  20    <year>2003</year>
  21    <holder>Pavel Pisa</holder>
  22   </copyright>
  23
  24   <abstract>
  25    <para>Implementation of AVL tree with some interesting features.
  26     All algorithms for insertion, deletion, traversal etc. are implemented without
  27     function call recursion or tree node stacks. The only exception is routine to
  28     check correctness of tree used for debugging purposes. The implementation has
  29     more advantages. It can work with partially unbalanced trees with balance
  30     factor (height difference) outside range &lt;-1,1&gt;. The balancing
  31     subroutine is common for insertion and deletion. Provided macros enables
  32     to build trees with strict item type checking which avoids necessity to use
  33     type-casting from (void *).
  34    </para>
  35   </abstract>
  36
  37  </bookinfo>
  38
  39  <toc></toc>
  40
  41  <chapter id="intro">
  42   <title>Introduction</title>
  43   <para>
  44    There are more concepts how to store data items sorted by some key values.
  45    The most commonly used ones are:
  46    <itemizedlist>
  47     <listitem>
  48      <para>sorted conntinuous arrays of items or pointers to items</para>
  49     </listitem>
  50     <listitem>
  51      <para>binary search trees (splash tree, AVL-tree, RB-tree)</para>
  52     </listitem>
  53     <listitem>
  54      <para>more childs per node search trees (B-tree)</para>
  55     </listitem>
  56    </itemizedlist>
  57   </para>
  58   <para>
  59    The binary search trees are considered most efficient for in memory
  60    operations when frequent tree updates are present. If update frequency
  61    is very low, sorted arrays of pointers could be more efficient. If the
  62    node retrieval operations are time consuming the n-nary search trees
  63    could be used.
  64   </para>
  65   <para>
  66    The provided GAVL library tries to offer fast and API friendly
  67    set of functions and macros usable for in-memory stored AVL trees
  68    of user specified items. The tree node chaining informations
  69    must be added to each stored item for holding of the tree node
  70    topology. The GAVL library can use user specified field of items
  71    or small malloced structure for holding of node chaining information.
  72   </para>
  73   <para>
  74    The tree search, insert and delete functions can work with and enforce tree
  75    with unique items or can be used in mode when more items with same
  76    search key value are allowed. The balancing and other functions
  77    are written such way, that they tolerate even degraded tree
  78    which does not fulfill AVL tree definition. The operations do not
  79    result in further degradation or program exceptions.
  80    Even future tree operations tends to enhance balancing if the height
  81    differences (balance factors) of degraded tree has been correctly updated.
  82   </para>
  83
  84
  85  </chapter>
  86
  87  <chapter id="gavlfunc">
  88   <title>Functions Description</title>
  89   <sect1><title>Generic AVL tree</title>
  90 !F../../ulut/ul_gavl.h
  91 !F../../ulut/ul_gavlprim.c
  92 !F../../ulut/ul_gavl.c
  93   </sect1>
  94   <sect1><title>Custom AVL Tree Instances</title>
  95    <para>
  96     The provided macros allows to define all AVL tree
  97     functions for tree with user defined root and item types.
  98     The next defined function names are prefixed by custom selected
  99     <replaceable>cust_prefix</replaceable>:
 100
 101     <variablelist>
 102
 103      <varlistentry>
 104       <term>
 105        <funcsynopsis><funcprototype>
 106         <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_node2item</function></funcdef>
 107         <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 108         <paramdef>const gavl_node_t * <parameter>node</parameter></paramdef>
 109        </funcprototype></funcsynopsis>
 110       </term>
 111       <listitem>
 112        <para>
 113          Conversion from AVL tree node to user custom defined item
 114        </para>
 115       </listitem>
 116      </varlistentry>
 117
 118      <varlistentry>
 119       <term>
 120   <funcsynopsis><funcprototype>
 121    <funcdef><replaceable>cust_key_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_node2key </function></funcdef>
 122    <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 123    <paramdef>const gavl_node_t * <parameter>node</parameter></paramdef>
 124   </funcprototype></funcsynopsis>
 125       </term>
 126       <listitem>
 127        <para>
 128          Conversion from AVL tree node to pointer to defined ordering key
 129        </para>
 130       </listitem>
 131      </varlistentry>
 132      <varlistentry>
 133       <term>
 134   <funcsynopsis><funcprototype>
 135    <funcdef>int <function><replaceable>cust_prefix</replaceable>_search_node </function></funcdef>
 136    <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 137    <paramdef>const <replaceable>cust_item_t</replaceable> * <parameter>key</parameter></paramdef>
 138    <paramdef>gavl_node_t ** <parameter>nodep</parameter></paramdef>
 139   </funcprototype></funcsynopsis>
 140       </term>
 141       <listitem>
 142        <para>
 143          Search for node or place for node by key
 144        </para>
 145       </listitem>
 146      </varlistentry>
 147      <varlistentry>
 148       <term>
 149   <funcsynopsis><funcprototype>
 150    <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_find </function></funcdef>
 151    <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 152    <paramdef>const <replaceable>cust_key_t</replaceable> * <parameter>key</parameter></paramdef>
 153   </funcprototype></funcsynopsis>
 154       </term>
 155       <listitem>
 156        <para>
 157     Pointer to item with key value or <constant>NULL</constant>
 158        </para>
 159       </listitem>
 160      </varlistentry>
 161      <varlistentry>
 162       <term>
 163   <funcsynopsis><funcprototype>
 164    <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_find_first </function></funcdef>
 165    <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 166    <paramdef>const <replaceable>cust_key_t</replaceable> * <parameter>key</parameter></paramdef>
 167   </funcprototype></funcsynopsis>
 168       </term>
 169       <listitem>
 170        <para>
 171    Same as above, but first matching item is found.
 172        </para>
 173       </listitem>
 174      </varlistentry>
 175      <varlistentry>
 176       <term>
 177   <funcsynopsis><funcprototype>
 178    <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_find_after </function></funcdef>
 179    <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 180    <paramdef>const <replaceable>cust_key_t</replaceable> * <parameter>key</parameter></paramdef>
 181   </funcprototype></funcsynopsis>
 182       </term>
 183       <listitem>
 184        <para>
 185    Finds the first item with key value higher than value pointed
 186    by <parameter>key</parameter> or returns <constant>NULL</constant>.
 187        </para>
 188       </listitem>
 189      </varlistentry>
 190      <varlistentry>
 191       <term>
 192   <funcsynopsis><funcprototype>
 193    <funcdef>int <function><replaceable>cust_prefix</replaceable>_insert </function></funcdef>
 194    <paramdef><replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 195    <paramdef><replaceable>cust_item_t</replaceable> * <parameter>item</parameter></paramdef>
 196   </funcprototype></funcsynopsis>
 197       </term>
 198       <listitem>
 199        <para>
 200          Insert new item into AVL tree. If the operation is successful
 201          positive value is returned. If key with same key value already
 202          exists negative value is returned
 203        </para>
 204       </listitem>
 205      </varlistentry>
 206      <varlistentry>
 207       <term>
 208   <funcsynopsis><funcprototype>
 209    <funcdef>int <function><replaceable>cust_prefix</replaceable>_delete_node </function></funcdef>
 210    <paramdef><replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 211    <paramdef>gavl_node_t * <parameter>node</parameter></paramdef>
 212   </funcprototype></funcsynopsis>
 213       </term>
 214       <listitem>
 215        <para>
 216          Deletes/unlinks node from custom AVL tree
 217        </para>
 218       </listitem>
 219      </varlistentry>
 220      <varlistentry>
 221       <term>
 222   <funcsynopsis><funcprototype>
 223    <funcdef>int <function><replaceable>cust_prefix</replaceable>_delete </function></funcdef>
 224    <paramdef><replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 225    <paramdef><replaceable>cust_item_t</replaceable> * <parameter>item</parameter></paramdef>
 226   </funcprototype></funcsynopsis>
 227       </term>
 228       <listitem>
 229        <para>
 230       Deletes/unlinks item from custom AVL tree
 231        </para>
 232       </listitem>
 233      </varlistentry>
 234      <varlistentry>
 235       <term>
 236   <funcsynopsis><funcprototype>
 237    <funcdef>gavl_node_t * <function><replaceable>cust_prefix</replaceable>_first_node </function></funcdef>
 238    <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 239   </funcprototype></funcsynopsis>
 240       </term>
 241       <listitem>
 242        <para>
 243     Returns the first node or <constant>NULL</constant> if the tree is empty
 244        </para>
 245       </listitem>
 246      </varlistentry>
 247      <varlistentry>
 248       <term>
 249   <funcsynopsis><funcprototype>
 250    <funcdef>gavl_node_t * <function><replaceable>cust_prefix</replaceable>_last_node </function></funcdef>
 251    <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 252   </funcprototype></funcsynopsis>
 253       </term>
 254       <listitem>
 255        <para>
 256       Returns last node or <constant>NULL</constant> if the tree is empty
 257        </para>
 258       </listitem>
 259      </varlistentry>
 260
 261      <varlistentry>
 262       <term>
 263        <funcsynopsis><funcprototype>
 264         <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_first</function></funcdef>
 265         <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 266        </funcprototype></funcsynopsis>
 267       </term>
 268       <listitem>
 269        <para>
 270          Returns pointer to the first item of the tree or <constant>NULL</constant>
 271        </para>
 272       </listitem>
 273      </varlistentry>
 274
 275      <varlistentry>
 276       <term>
 277        <funcsynopsis><funcprototype>
 278         <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_last</function></funcdef>
 279         <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 280        </funcprototype></funcsynopsis>
 281       </term>
 282       <listitem>
 283        <para>
 284          Returns pointer to last item of the tree or <constant>NULL</constant>
 285        </para>
 286       </listitem>
 287      </varlistentry>
 288
 289      <varlistentry>
 290       <term>
 291        <funcsynopsis><funcprototype>
 292         <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_next</function></funcdef>
 293         <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 294         <paramdef>const <replaceable>cust_item_t</replaceable> * <parameter>item</parameter></paramdef>
 295        </funcprototype></funcsynopsis>
 296       </term>
 297       <listitem>
 298        <para>
 299          Returns pointer to next item of the tree or <constant>NULL</constant>
 300          if there is no more items
 301        </para>
 302       </listitem>
 303      </varlistentry>
 304
 305      <varlistentry>
 306       <term>
 307        <funcsynopsis><funcprototype>
 308         <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_prev</function></funcdef>
 309         <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 310         <paramdef>const <replaceable>cust_item_t</replaceable> * <parameter>item</parameter></paramdef>
 311        </funcprototype></funcsynopsis>
 312       </term>
 313       <listitem>
 314        <para>
 315          Returns pointer to previous item of the tree or <constant>NULL</constant>
 316          if there is no more items
 317        </para>
 318       </listitem>
 319      </varlistentry>
 320
 321      <varlistentry>
 322       <term>
 323   <funcsynopsis><funcprototype>
 324    <funcdef>int <function><replaceable>cust_prefix</replaceable>_is_empty </function></funcdef>
 325    <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 326   </funcprototype></funcsynopsis>
 327       </term>
 328       <listitem>
 329        <para>
 330     Returns non-zero value if there is no node in the tree
 331        </para>
 332       </listitem>
 333      </varlistentry>
 334
 335      <varlistentry>
 336       <term>
 337   <funcsynopsis><funcprototype>
 338    <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_cut_first </function></funcdef>
 339    <paramdef><replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
 340   </funcprototype></funcsynopsis>
 341       </term>
 342       <listitem>
 343        <para>
 344     Returns the first item or <constant>NULL</constant> if the tree is empty.
 345     The returned item is unlinked from the tree without tree rebalance
 346        </para>
 347       </listitem>
 348      </varlistentry>
 349
 350     </variablelist>
 351
 352    </para>
 353
 354    <refentry>
 355    <refmeta>
 356    <refentrytitle><phrase id="API-GAVL-CUST-NODE-INT-IMP">GAVL_CUST_NODE_INT_IMP</phrase></refentrytitle>
 357    </refmeta>
 358    <refnamediv>
 359     <refname>GAVL_CUST_NODE_INT_IMP</refname>
 360     <refpurpose>
 361       Implementation of new custom tree with internal node
 362     </refpurpose>
 363    </refnamediv>
 364    <refsynopsisdiv>
 365     <title>Synopsis</title>
 366      <funcsynopsis><funcprototype>
 367       <funcdef> <function>GAVL_CUST_NODE_INT_IMP </function></funcdef>
 368       <paramdef> <parameter>cust_prefix</parameter></paramdef>
 369       <paramdef> <parameter>cust_root_t</parameter></paramdef>
 370       <paramdef> <parameter>cust_item_t</parameter></paramdef>
 371       <paramdef> <parameter>cust_key_t</parameter></paramdef>
 372       <paramdef> <parameter>cust_root_node</parameter></paramdef>
 373       <paramdef> <parameter>cust_item_node</parameter></paramdef>
 374       <paramdef> <parameter>cust_item_key</parameter></paramdef>
 375       <paramdef> <parameter>cust_cmp_fnc</parameter></paramdef>
 376      </funcprototype></funcsynopsis>
 377    </refsynopsisdiv>
 378    <refsect1>
 379     <title>Arguments</title>
 380     <variablelist>
 381      <varlistentry>
 382       <term><parameter>cust_prefix</parameter></term>
 383       <listitem>
 384        <para>
 385            defines prefix for builded function names
 386        </para>
 387       </listitem>
 388      </varlistentry>
 389      <varlistentry>
 390       <term><parameter>cust_root_t</parameter></term>
 391       <listitem>
 392        <para>
 393            user defined structure type of root of the tree
 394        </para>
 395       </listitem>
 396      </varlistentry>
 397      <varlistentry>
 398       <term><parameter>cust_item_t</parameter></term>
 399       <listitem>
 400        <para>
 401            user defined structure type of items stored in the tree
 402        </para>
 403       </listitem>
 404      </varlistentry>
 405      <varlistentry>
 406       <term><parameter>cust_key_t</parameter></term>
 407       <listitem>
 408        <para>
 409                    type of the key used for sorting of the items
 410        </para>
 411       </listitem>
 412      </varlistentry>
 413      <varlistentry>
 414       <term><parameter>cust_root_node</parameter></term>
 415       <listitem>
 416        <para>
 417            the field of the root structure pointing to the tree root node
 418        </para>
 419       </listitem>
 420      </varlistentry>
 421      <varlistentry>
 422       <term><parameter>cust_item_node</parameter></term>
 423       <listitem>
 424        <para>
 425            the field of item structure used for chaining of items
 426        </para>
 427       </listitem>
 428      </varlistentry>
 429      <varlistentry>
 430       <term><parameter>cust_item_key</parameter></term>
 431       <listitem>
 432        <para>
 433            the key field of item structure defining order of items
 434        </para>
 435       </listitem>
 436      </varlistentry>
 437      <varlistentry>
 438       <term><parameter>cust_cmp_fnc</parameter></term>
 439       <listitem>
 440        <para>
 441            the keys compare function
 442        </para>
 443       </listitem>
 444      </varlistentry>
 445     </variablelist>
 446    </refsect1>
 447    <refsect1>
 448     <title>Description</title>
 449     <para>
 450       There are two macros designed for building custom AVL trees. The macro
 451       <constant>GAVL_CUST_NODE_INT_DEC</constant> declares functions for custom tree manipulations
 452       and is intended for use in header files.
 453       The macro <constant>GAVL_CUST_NODE_INT_IMP</constant> builds implementations for non-inlined
 454       functions declared by <constant>GAVL_CUST_NODE_INT_DEC</constant>. The <parameter>cust_cmp_fnc</parameter> is used
 455       for comparison of item keys in the search and insert functions. The types
 456       of two input arguments of <parameter>cust_cmp_fnc</parameter> functions must correspond
 457       with <parameter>cust_key_t</parameter> type. Return value should be positive for case when
 458       the first pointed key value is greater then second, negative for reverse
 459       case and zero for equal pointed values.
 460     </para>
 461    </refsect1>
 462    </refentry>
 463
 464
 465   </sect1>
 466  </chapter>
 467
 468  <chapter id="gavlexample">
 469   <title>Examples of GAVL Usage</title>
 470   <sect1><title>Generic AVL Tree</title>
 471    <para>
 472     This chapter describes use of generic AVL tree. This tree has advantage,
 473     that same functions could operate with any user provided items, but
 474     operations return type is <type>void</type>* and needs type-casting to
 475     user item type.
 476    </para>
 477    <programlisting>#include &#60;malloc.h&#62;
 478 #include &#34;ul_gavl.h&#34;</programlisting>
 479
 480    <para>
 481     The above code fragment includes basic GAVL declarations.
 482    </para>
 483
 484    <programlisting>typedef struct test1_item {
 485   int my_val;
 486   /* more user data ... */
 487 } test1_item_t;</programlisting>
 488
 489    <para>
 490     New item type is declared. Type have to contain or be connected to
 491     some key value. The <type>integer</type> number
 492     <structfield>my_val</structfield> will be used as key value in this example.
 493     The tree root instance definition follows.
 494    </para>
 495
 496    <programlisting>gavl_root_t test1_tree={
 497   .root_node = NULL,
 498   .node_offs = -1,
 499   .key_offs = UL_OFFSETOF(test1_item_t, my_val),
 500   .cmp_fnc = gavl_cmp_int
 501 };</programlisting>
 502
 503    <para>
 504     The field <structfield>root_node</structfield> have to be initialized to
 505     <constant>NULL</constant>.
 506     The value -1 for the <structfield>node_offs</structfield> field directs
 507     GAVL functions to allocate external node structure for each inserted item.
 508     The macro <constant>UL_OFFSETOF</constant> computes offset of
 509     <structfield>my_val</structfield> field in <type>test1_item_t</type>
 510     item. The last assignment select one of predefined functions for
 511     key values comparison.
 512    </para>
 513
 514    <para>
 515     Almost same declarations and definitions could be used if the node
 516     chaining structure is contained inside item structure. That is shown in
 517     the next code fragments.
 518    </para>
 519
 520    <programlisting>typedef struct test2_item {
 521   gavl_node_t my_node;
 522   int my_val;
 523   /* more user data ... */
 524 } test2_item_t;</programlisting>
 525
 526    <para>
 527     The item declaration contains field with <type>gavl_node_t</type> type
 528     in this case. This field is used for storage of tree topology information.
 529    </para>
 530
 531    <programlisting>gavl_root_t test2_tree={
 532   .root_node = NULL,
 533   .node_offs = UL_OFFSETOF(test2_item_t, my_node),
 534   .key_offs = UL_OFFSETOF(test2_item_t, my_val),
 535   .cmp_fnc = gavl_cmp_int
 536 };</programlisting>
 537
 538    <para>
 539     The field <structfield>node_offs</structfield> contains offset of the
 540     node structure inside item now. Next fragments are part of the function
 541     working with defined tree. There would be no difference in the functions
 542     calls for items with external nodes.
 543    </para>
 544
 545    <programlisting>  cust2_item_t *item;
 546   int i;
 547   gavl_node_t *node;</programlisting>
 548
 549    <para>
 550     Declare some local variables first. Insert 100 items into tree then.
 551    </para>
 552
 553    <programlisting>  for(i=0;i&#60;items_cnt;i++){
 554     item=malloc(sizeof(test2_item_t));
 555     item-&#62;my_val=i;
 556     if(gavl_insert(&#38;test2_tree,item,0)&#60;0)
 557       printf(&#34;gavl_insert error\n&#34;);
 558   }</programlisting>
 559
 560    <para>
 561     The tree is expected to store items with unique key values.
 562     If more items with same key values should be allowed, then the
 563     value of <parameter>mode</parameter> parameter in <function>gavl_insert</function>
 564     function call have to be changed from 0 to <constant>GAVL_FAFTER</constant>.
 565    </para>
 566
 567    <programlisting>  for(i=0;i&#60;102;i++){
 568     if(!(item=(cust2_item_t *)gavl_find(&#38;test2_tree,&#38;i)))
 569       printf(&#34;no item %d\n&#34;,i);
 570     else
 571       if(item-&#62;my_val!=i)
 572         printf(&#34;gavl_find mismatch\n&#34;);
 573   }</programlisting>
 574
 575    <para>
 576     Some test of retrieving item corresponding to specified key.
 577     The tree in order traversal is in the next code sample.
 578    </para>
 579
 580    <programlisting>  node=gavl_first_node(&#38;test2_tree)
 581   while(node){
 582     item=(cust2_item_t *)gavl_node2item(&#38;test2_tree,node);
 583     /* do something with item
 584      * insert and delete allowed there except delete of the actual item
 585      */
 586     node=gavl_next_node(node);
 587     /* do something with item
 588      * insert and delete allowed there except delete of next item
 589      */
 590   }</programlisting>
 591
 592    <para>
 593     Example of the item deletion is in the next fragment.
 594     The function <function>gavl_delete</function>
 595     guarantees that trial of deleting item, which is not part of the tree,
 596     is detected and negative value is returned. There is one prerequisite
 597     for this behavior for items with internal nodes that have never been
 598     part of any tree. The field <structfield>parent</structfield>
 599     of node structure stored in the item have to be  initialized to
 600     <constant>NULL</constant> value.
 601    </para>
 602
 603    <programlisting>  for(i=0;i&#60;80;i++){
 604     if(!(item=(cust2_item_t *)gavl_find(&#38;test2_tree,&#38;i)))
 605       continue;
 606     if(gavl_delete(&#38;test2_tree,item)&#60;0)
 607       printf(&#34;gavl_delete error\n&#34;);
 608     free(item);
 609   }</programlisting>
 610
 611    <para>
 612     The function <function>gavl_cut_first</function> can significantly simplify
 613     deletion of all nodes of the tree without need of traversal over the tree.
 614     This function does not rebalance the tree, but keeps tree consistent.
 615    </para>
 616
 617    <programlisting>  while((item=(cust2_item_t *)gavl_cut_first(&#38;test2_tree))!=NULL)
 618     free(item);</programlisting>
 619   </sect1>
 620
 621   <sect1><title>Customized AVL Tree</title>
 622    <para>
 623     The function templates are provided for faster and type-safe
 624     custom tree definition and manipulation. These templates expect
 625     user defined items with internal node structures and key comparison
 626     function with key pointer input parameters. The type of these
 627     parameters is required to be pointer to the key type.
 628    </para>
 629    <para>
 630     Next code fragment is intended to be part of the declarations
 631     of user defined custom tree and items for some data storage
 632     purpose. The header with these definitions should be included
 633     from all modules directly working with specified tree.
 634    </para>
 635
 636    <programlisting>#include &#34;ul_gavl.h&#34;
 637
 638 typedef int cust_key_t;
 639
 640 typedef struct cust2_item {
 641   cust2_key_t my_val;
 642   gavl_node_t my_node;
 643   /* more user item data ... */
 644 } cust2_item_t;
 645
 646 typedef struct cust2_root {
 647   gavl_node_t *my_root;
 648   /* more user root/tree data ... */
 649 } cust2_root_t;
 650
 651 int cust_cmp_fnc(cust_key_t *a, cust_key_t *b);</programlisting>
 652
 653    <para>
 654     As can be seen from above code fragment, the key field with user declared
 655     type (<type>cust_key_t</type>) and internal node structure are required
 656     for items. The only one field with type <type>gavl_node_t</type>* is required
 657     for the custom tree root  structure.
 658    </para>
 659    <para>
 660     The use of the macro <constant>GAVL_CUST_NODE_INT_DEC</constant> declares
 661     all tree manipulation functions for the custom tree. The function names are
 662     prefixed by prefix specified as the first parameter of macro invocation.
 663     This declaration can be included in user header files as well.
 664    </para>
 665
 666    <programlisting>GAVL_CUST_NODE_INT_DEC(cust2, cust2_root_t, cust2_item_t, cust2_key_t,\
 667   my_root, my_node, my_val, cust_cmp_fnc)</programlisting>
 668
 669    <para>
 670     The implementation of the custom tree functions is realized
 671     by use of macro <constant>GAVL_CUST_NODE_INT_IMP</constant> with same
 672     parameters as for <constant>GAVL_CUST_NODE_INT_DEC</constant> macro.
 673    </para>
 674
 675    <programlisting>#include &#34;ul_gavlcust.h&#34;
 676
 677 GAVL_CUST_NODE_INT_IMP(cust2, cust2_root_t, cust2_item_t, cust2_key_t,\
 678   my_root, my_node, my_val, cust_cmp_fnc)
 679
 680 cust2_root_t cust2_tree;</programlisting>
 681
 682    <para>
 683     Static tree root instance is included at last line of above code fragment as well.
 684    </para>
 685    <para>
 686     The next sample function for the custom tree shows same operation
 687     as have been described for generic tree.
 688    </para>
 689
 690    <programlisting>void test_cust_tree(void)
 691 {
 692   int i;
 693   cust2_item_t *item;
 694
 695   /* build tree */
 696   for(i=1;i&#60;=100;i++){
 697     item=malloc(sizeof(cust2_item_t));
 698     item-&#62;my_val=i;
 699     if(cust2_insert(&#38;cust2_tree,item)&#60;0)
 700       printf(&#34;cust2_insert error\n&#34;);
 701   }
 702
 703   /* traverse tree */
 704   printf(&#34;Custom tree cust2:\n&#34;);
 705   for(item=cust2_first(&#38;cust2_tree);item;item=cust2_next(&#38;cust2_tree,item))
 706     printf(&#34;%d &#34;,item-&#62;my_val);
 707   printf(&#34;\n&#34;);
 708
 709   /* delete part of the tree */
 710   for(i=1;i&#60;=80;i++){
 711     item=cust2_find(&#38;cust2_tree,&#38;i);
 712     if(cust2_delete(&#38;cust2_tree,item)&#60;0)
 713       printf(&#34;cust2_delete error\n&#34;);
 714     free(item);
 715   }
 716
 717   /* traverse in reverse order */
 718   printf(&#34;Custom tree cust2:\n&#34;);
 719   for(item=cust2_last(&#38;cust2_tree);item;item=cust2_prev(&#38;cust2_tree,item))
 720     printf(&#34;%d &#34;,item-&#62;my_val);
 721   printf(&#34;\n&#34;);
 722
 723   /* delete all remaining items */
 724   while((item=cust2_cut_first(&#38;cust2_tree))!=NULL)
 725     free(item);
 726 }</programlisting>
 727
 728   </sect1>
 729  </chapter>
 730
 731 <!--
 732 <equation>
 733   <title>A TeX Equation</title>
 734   <mediaobject>
 735     <imageobject role="html">
 736       <imagedata fileref="texmath.png" format="PNG">
 737     </imageobject>
 738     <textobject role="tex"><phrase>$C = \alpha + \beta Y^{\gamma}
 739     + \epsilon$</phrase></textobject>
 740   </mediaobject>
 741 </equation>
 742 -->
 743
 744  <chapter id="gavlalg">
 745   <title>Used Algorithms Background</title>
 746   <sect1><title>Tree Balancing Operations</title>
 747   <para>
 748     This section describes used algorithms for keeping
 749     AVL tree balanced.
 750   </para>
 751
 752 <!-- ***************************************************** -->
 753
 754   <para>Next convention is used for height and balance computations for node
 755    <inlineequation>
 756     <alt>$\textrm{X}$
 757     </alt>
 758     <inlinemediaobject>
 759      <imageobject>
 760       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 761      </imageobject>
 762     </inlinemediaobject>
 763    </inlineequation>. The height of subtree starting at
 764    <inlineequation>
 765     <alt>$\textrm{X}$
 766     </alt>
 767     <inlinemediaobject>
 768      <imageobject>
 769       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 770      </imageobject>
 771     </inlinemediaobject>
 772    </inlineequation> is labeled as
 773    <inlineequation>
 774     <alt>$x=height(\textrm{X})$
 775     </alt>
 776     <inlinemediaobject>
 777      <imageobject>
 778       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 779      </imageobject>
 780     </inlinemediaobject>
 781    </inlineequation>. Height difference (balance factor) for node
 782    <inlineequation>
 783     <alt>$\textrm{X}$
 784     </alt>
 785     <inlinemediaobject>
 786      <imageobject>
 787       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 788      </imageobject>
 789     </inlinemediaobject>
 790    </inlineequation> is labeled as
 791    <inlineequation>
 792     <alt>$\Delta x=height(left(\textrm{X}))-height(right(\textrm{X}))$
 793     </alt>
 794     <inlinemediaobject>
 795      <imageobject>
 796       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 797      </imageobject>
 798     </inlinemediaobject>
 799    </inlineequation>.
 800   </para>
 801  <sect2>
 802   <title>Tree Balancing Case 1</title>
 803   <para>
 804    <figure>
 805     <title>Tree balancing case 1</title>
 806     <mediaobject>
 807       <imageobject>
 808         <imagedata align="center" fileref="fig/gavl_t11.pdf" format="EPS" scale="75" >
 809       </imageobject>
 810       <imageobject>
 811         <imagedata align="center" fileref="fig/gavl_t11.gif" format="GIF" scale="75" >
 812       </imageobject>
 813       <caption><para>Before operation</para></caption>
 814     </mediaobject>
 815     <mediaobject>
 816       <imageobject>
 817         <imagedata align="center" fileref="fig/gavl_t12.pdf" format="EPS" scale="75" >
 818       </imageobject>
 819       <imageobject>
 820         <imagedata align="center" fileref="fig/gavl_t12.gif" format="GIF" scale="75" >
 821       </imageobject>
 822       <caption><para>After operation</para></caption>
 823     </mediaobject>
 824    </figure>
 825   </para>
 826   <para>
 827    <equation>
 828     <alt>\begin{eqnarray*}
 829 \Delta s &#38; = &#38; n-b\qquad \geq 2\\
 830 \Delta n &#38; = &#38; a-p\qquad \geq 0
 831 \end{eqnarray*}
 832
 833     </alt>
 834     <mediaobject>
 835      <imageobject>
 836       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 837      </imageobject>
 838     </mediaobject>
 839    </equation> The height of subtree
 840    <inlineequation>
 841     <alt>$\textrm{S}$
 842     </alt>
 843     <inlinemediaobject>
 844      <imageobject>
 845       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 846      </imageobject>
 847     </inlinemediaobject>
 848    </inlineequation> is defined by highest branch, which is branch grovinggrowing from node
 849    <inlineequation>
 850     <alt>$\textrm{A}$
 851     </alt>
 852     <inlinemediaobject>
 853      <imageobject>
 854       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 855      </imageobject>
 856     </inlinemediaobject>
 857    </inlineequation>. This leads to next equations.
 858    <equation>
 859     <alt>\begin{eqnarray*}
 860 n &#38; = &#38; a+1\\
 861 s &#38; = &#38; a+2\\
 862 p &#38; = &#38; a-\Delta n\\
 863 b &#38; = &#38; a+1-\Delta s
 864 \end{eqnarray*}
 865
 866     </alt>
 867     <mediaobject>
 868      <imageobject>
 869       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 870      </imageobject>
 871     </mediaobject>
 872    </equation>The height of branches
 873    <inlineequation>
 874     <alt>$\textrm{N}$
 875     </alt>
 876     <inlinemediaobject>
 877      <imageobject>
 878       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 879      </imageobject>
 880     </inlinemediaobject>
 881    </inlineequation> and
 882    <inlineequation>
 883     <alt>$\textrm{S}$
 884     </alt>
 885     <inlinemediaobject>
 886      <imageobject>
 887       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 888      </imageobject>
 889     </inlinemediaobject>
 890    </inlineequation> is marked as
 891    <inlineequation>
 892     <alt>$n1$
 893     </alt>
 894     <inlinemediaobject>
 895      <imageobject>
 896       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 897      </imageobject>
 898     </inlinemediaobject>
 899    </inlineequation> and
 900    <inlineequation>
 901     <alt>$s1$
 902     </alt>
 903     <inlinemediaobject>
 904      <imageobject>
 905       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 906      </imageobject>
 907     </inlinemediaobject>
 908    </inlineequation> after balancing.
 909    <equation>
 910     <alt>\begin{eqnarray*}
 911 \Delta s1 &#38; = &#38; p-b\\
 912 \Delta n1 &#38; = &#38; a-s1
 913 \end{eqnarray*}
 914
 915     </alt>
 916     <mediaobject>
 917      <imageobject>
 918       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 919      </imageobject>
 920     </mediaobject>
 921    </equation>
 922    <equation>
 923     <alt>\begin{eqnarray*}
 924 s1 &#38; = &#38; \max (p,b)+1\\
 925 s1 &#38; = &#38; \max (a-\Delta n,a+1-\Delta s)+1\\
 926 s1 &#38; = &#38; a+1+\max (-\Delta n,1-\Delta s)\\
 927 s1 &#38; = &#38; a+1-\min (\Delta n,\Delta s-1)
 928 \end{eqnarray*}
 929
 930     </alt>
 931     <mediaobject>
 932      <imageobject>
 933       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 934      </imageobject>
 935     </mediaobject>
 936    </equation>
 937    <equation>
 938     <alt>\begin{eqnarray*}
 939 \Delta s1 &#38; = &#38; a-\Delta n-a-1+\Delta s\\
 940 \Delta s1 &#38; = &#38; \Delta s-\Delta n-1\\
 941 \Delta n1 &#38; = &#38; a-a-1+\min (\Delta n,\Delta s-1)\\
 942 \Delta n1 &#38; = &#38; \min (\Delta n-1,\Delta s-2)\\
 943 \Delta n1 &#38; = &#38; \left\langle \begin{array}{cc}
 944  \Delta n-1 &#38; \qquad \Delta s\geq \Delta n+1\\
 945  \Delta s-2 &#38; \qquad \Delta s\leq \Delta n+1\end{array}
 946 \right.
 947 \end{eqnarray*}
 948
 949     </alt>
 950     <mediaobject>
 951      <imageobject>
 952       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 953      </imageobject>
 954     </mediaobject>
 955    </equation>Because balancing in case 1 does not guarantee that new tree has lower height than original tree, it is necessary to compute tree height change (tree height lowering).
 956    <equation>
 957     <alt>\begin{eqnarray*}
 958 s-n1 &#38; = &#38; s-(\max (a,s1)+1)\\
 959  &#38; = &#38; a+2-(\max (a,a+1+\max (-\Delta n,1-\Delta s))+1)\\
 960  &#38; = &#38; 1-\max (0,\max (1-\Delta n,2-\Delta s))\\
 961  &#38; = &#38; \min (1,\Delta n,\Delta s-1)\qquad \Delta n\geq 0,\Delta s\geq 2\\
 962  &#38; = &#38; \min (1,\Delta n)\\
 963 s-n1 &#38; = &#38; \left\langle \begin{array}{cc}
 964  1 &#38; \qquad \Delta n\neq 0\\
 965  0 &#38; \qquad \Delta n=1\end{array}
 966 \right.
 967 \end{eqnarray*}
 968
 969     </alt>
 970     <mediaobject>
 971      <imageobject>
 972       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
 973      </imageobject>
 974     </mediaobject>
 975    </equation></para></sect2>
 976   <sect2><title>Tree Balancing Case 2</title>
 977    <para>
 978    <figure>
 979     <title>Tree balancing case 2</title>
 980     <mediaobject>
 981       <imageobject>
 982         <imagedata align="center" fileref="fig/gavl_t21.pdf" format="EPS" scale="75" >
 983       </imageobject>
 984       <imageobject>
 985         <imagedata align="center" fileref="fig/gavl_t21.gif" format="GIF" scale="75" >
 986       </imageobject>
 987       <caption><para>Before operation</para></caption>
 988     </mediaobject>
 989     <mediaobject>
 990       <imageobject>
 991         <imagedata align="center" fileref="fig/gavl_t22.pdf" format="EPS" scale="75" >
 992       </imageobject>
 993       <imageobject>
 994         <imagedata align="center" fileref="fig/gavl_t22.gif" format="GIF" scale="75" >
 995       </imageobject>
 996       <caption><para>After operation</para></caption>
 997     </mediaobject>
 998    </figure>
 999   </para>
1000   <para>This case has advantage, that it reduces tree height for all node height combinations. Tree height is given by branch
1001    <inlineequation>
1002     <alt>$\textrm{P}$
1003     </alt>
1004     <inlinemediaobject>
1005      <imageobject>
1006       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1007      </imageobject>
1008     </inlinemediaobject>
1009    </inlineequation>
1010    <inlineequation>
1011     <alt>$\textrm{B}$
1012     </alt>
1013     <inlinemediaobject>
1014      <imageobject>
1015       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1016      </imageobject>
1017     </inlinemediaobject>
1018    </inlineequation> or
1019    <inlineequation>
1020     <alt>$\textrm{P}$
1021     </alt>
1022     <inlinemediaobject>
1023      <imageobject>
1024       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1025      </imageobject>
1026     </inlinemediaobject>
1027    </inlineequation>
1028    <inlineequation>
1029     <alt>$\textrm{C}$
1030     </alt>
1031     <inlinemediaobject>
1032      <imageobject>
1033       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1034      </imageobject>
1035     </inlinemediaobject>
1036    </inlineequation>.
1037    <equation>
1038     <alt>\begin{eqnarray*}
1039 \Delta s &#38; = &#38; n-d\qquad \geq 2\\
1040 \Delta n &#38; = &#38; a-p\qquad \leq -1
1041 \end{eqnarray*}
1042
1043     </alt>
1044     <mediaobject>
1045      <imageobject>
1046       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1047      </imageobject>
1048     </mediaobject>
1049    </equation>
1050    <equation>
1051     <alt>\begin{eqnarray*}
1052 n &#38; = &#38; p+1\\
1053 s &#38; = &#38; p+2\\
1054 d &#38; = &#38; p+1-\Delta s\\
1055 a &#38; = &#38; p+\Delta n
1056 \end{eqnarray*}
1057
1058     </alt>
1059     <mediaobject>
1060      <imageobject>
1061       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1062      </imageobject>
1063     </mediaobject>
1064    </equation>
1065    <equation>
1066     <alt>\begin{eqnarray*}
1067 \textrm{for}\, b\geq c\qquad c &#38; = &#38; b-\Delta p\qquad p=b+1\\
1068 \textrm{for}\, c\geq b\qquad b &#38; = &#38; c+\Delta p\qquad p=c+1
1069 \end{eqnarray*}
1070
1071     </alt>
1072     <mediaobject>
1073      <imageobject>
1074       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1075      </imageobject>
1076     </mediaobject>
1077    </equation>When
1078    <inlineequation>
1079     <alt>$b\geq c$
1080     </alt>
1081     <inlinemediaobject>
1082      <imageobject>
1083       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1084      </imageobject>
1085     </inlinemediaobject>
1086    </inlineequation> then the height differences
1087    <inlineequation>
1088     <alt>$\Delta s1$
1089     </alt>
1090     <inlinemediaobject>
1091      <imageobject>
1092       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1093      </imageobject>
1094     </inlinemediaobject>
1095    </inlineequation>,
1096    <inlineequation>
1097     <alt>$\Delta n1$
1098     </alt>
1099     <inlinemediaobject>
1100      <imageobject>
1101       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1102      </imageobject>
1103     </inlinemediaobject>
1104    </inlineequation> and
1105    <inlineequation>
1106     <alt>$\Delta p1$
1107     </alt>
1108     <inlinemediaobject>
1109      <imageobject>
1110       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1111      </imageobject>
1112     </inlinemediaobject>
1113    </inlineequation> for nodes
1114    <inlineequation>
1115     <alt>$\textrm{S}$
1116     </alt>
1117     <inlinemediaobject>
1118      <imageobject>
1119       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1120      </imageobject>
1121     </inlinemediaobject>
1122    </inlineequation>,
1123    <inlineequation>
1124     <alt>$\textrm{N}$
1125     </alt>
1126     <inlinemediaobject>
1127      <imageobject>
1128       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1129      </imageobject>
1130     </inlinemediaobject>
1131    </inlineequation> and
1132    <inlineequation>
1133     <alt>$\textrm{P}$
1134     </alt>
1135     <inlinemediaobject>
1136      <imageobject>
1137       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1138      </imageobject>
1139     </inlinemediaobject>
1140    </inlineequation> of the balanced tree can be computed from next equations.
1141    <equation>
1142     <alt>\begin{eqnarray*}
1143 b\geq c &#38; , &#38; \Delta p\geq 0\\
1144 n1 &#38; = &#38; b+1\\
1145 p1 &#38; = &#38; b+2\\
1146 s1 &#38; = &#38; \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
1147 \Delta s1 &#38; = &#38; c-d=b-\Delta p-b-2+\Delta s\\
1148 \Delta s1 &#38; = &#38; \Delta s-2-\Delta p\\
1149 \Delta n1 &#38; = &#38; a-b=b+1+\Delta n-b\\
1150 \Delta n1 &#38; = &#38; \Delta n+1\\
1151 \Delta p1 &#38; = &#38; n1-s1=b+1-\max (b-\Delta p,b+2-\Delta s)-1\\
1152 \Delta p1 &#38; = &#38; \min (\Delta p,\Delta s-2)\qquad \Delta p\geq 0,\Delta s\geq 2
1153 \end{eqnarray*}
1154
1155     </alt>
1156     <mediaobject>
1157      <imageobject>
1158       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1159      </imageobject>
1160     </mediaobject>
1161    </equation>When
1162    <inlineequation>
1163     <alt>$c\geq b$
1164     </alt>
1165     <inlinemediaobject>
1166      <imageobject>
1167       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1168      </imageobject>
1169     </inlinemediaobject>
1170    </inlineequation> then the height differences
1171    <inlineequation>
1172     <alt>$\Delta s1$
1173     </alt>
1174     <inlinemediaobject>
1175      <imageobject>
1176       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1177      </imageobject>
1178     </inlinemediaobject>
1179    </inlineequation>,
1180    <inlineequation>
1181     <alt>$\Delta n1$
1182     </alt>
1183     <inlinemediaobject>
1184      <imageobject>
1185       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1186      </imageobject>
1187     </inlinemediaobject>
1188    </inlineequation> and
1189    <inlineequation>
1190     <alt>$\Delta p1$
1191     </alt>
1192     <inlinemediaobject>
1193      <imageobject>
1194       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1195      </imageobject>
1196     </inlinemediaobject>
1197    </inlineequation> for nodes
1198    <inlineequation>
1199     <alt>$\textrm{S}$
1200     </alt>
1201     <inlinemediaobject>
1202      <imageobject>
1203       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1204      </imageobject>
1205     </inlinemediaobject>
1206    </inlineequation>,
1207    <inlineequation>
1208     <alt>$\textrm{N}$
1209     </alt>
1210     <inlinemediaobject>
1211      <imageobject>
1212       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1213      </imageobject>
1214     </inlinemediaobject>
1215    </inlineequation> and
1216    <inlineequation>
1217     <alt>$\textrm{P}$
1218     </alt>
1219     <inlinemediaobject>
1220      <imageobject>
1221       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1222      </imageobject>
1223     </inlinemediaobject>
1224    </inlineequation> of the balanced tree can be computed from next equations.
1225    <equation>
1226     <alt>\begin{eqnarray*}
1227 c\geq b &#38; , &#38; \Delta p\leq 0\\
1228 s1 &#38; = &#38; c+1\\
1229 p1 &#38; = &#38; c+2\\
1230 n1 &#38; = &#38; \max (a,b)+1=\max (c+1+\Delta n,c+\Delta p)+1\\
1231 \Delta s1 &#38; = &#38; c-d=c-c-2+\Delta s\\
1232 \Delta s1 &#38; = &#38; \Delta s-2\\
1233 \Delta n1 &#38; = &#38; a-b=c+1+\Delta n-c-\Delta p\\
1234 \Delta n1 &#38; = &#38; \Delta n+1-\Delta p\\
1235 \Delta p1 &#38; = &#38; n1-s1=\max (c+1+\Delta n,c+\Delta p)+1-c-1\\
1236 \Delta p1 &#38; = &#38; \max (\Delta n,\Delta s-1)\qquad \Delta n\leq -1,\Delta p\leq 0
1237 \end{eqnarray*}
1238
1239     </alt>
1240     <mediaobject>
1241      <imageobject>
1242       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1243      </imageobject>
1244     </mediaobject>
1245    </equation></para></sect2>
1246 </sect1>
1247 <sect1><title>Height of the AVL Tree</title><para>Minimal number of nodes
1248    <inlineequation>
1249     <alt>$T$
1250     </alt>
1251     <inlinemediaobject>
1252      <imageobject>
1253       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1254      </imageobject>
1255     </inlinemediaobject>
1256    </inlineequation> can be computed recursively.
1257    <equation>
1258     <alt>\[
1259 T(h)=T(h-1)+T(h-2)+1,\, T(0)=0,\, T(1)=1\]
1260
1261     </alt>
1262     <mediaobject>
1263      <imageobject>
1264       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1265      </imageobject>
1266     </mediaobject>
1267    </equation>1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986</para><para>
1268    <equation>
1269     <alt>\[
1270 T(h)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{(h+2)}-1\]
1271
1272     </alt>
1273     <mediaobject>
1274      <imageobject>
1275       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1276      </imageobject>
1277     </mediaobject>
1278    </equation>
1279    <equation>
1280     <alt>\[
1281 T(h)=\frac{1}{\sqrt{5}}\, 2^{(h+2)\, log_{2}\left(\frac{1+\sqrt{5}}{2}\right)}-1\]
1282
1283     </alt>
1284     <mediaobject>
1285      <imageobject>
1286       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1287      </imageobject>
1288     </mediaobject>
1289    </equation>
1290    <equation>
1291     <alt>\[
1292 h=\left(log_{2}(T+1)-log_{2}\left(\frac{1}{\sqrt{5}}\right)\right)log_{2}^{-1}\left(\frac{1+\sqrt{5}}{2}\right)-2\]
1293
1294     </alt>
1295     <mediaobject>
1296      <imageobject>
1297       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1298      </imageobject>
1299     </mediaobject>
1300    </equation>
1301    <equation>
1302     <alt>\[
1303 log_{2}^{-1}\left(\frac{1+\sqrt{5}}{2}\right)=1.44042\]
1304
1305     </alt>
1306     <mediaobject>
1307      <imageobject>
1308       <imagedata fileref="img/gavl_eq1.gif" format="GIF">
1309      </imageobject>
1310     </mediaobject>
1311    </equation></para><para>An AVL tree with n nodes has height between log2 (n + 1) and 1.44 * log2 (n + 2) - 0.328. An AVL tree with height h has between pow (2, (h + .328) / 1.44) - 1 and pow (2, h) - 1 nodes.</para><para>A red-black tree with n nodes has height at least log2 (n + 1) but no more than 2 * log2 (n + 1). A red-black tree with height h has at least pow (2, h / 2) - 1 nodes but no more than pow (2, h) - 1. </para>
1312
1313 <!-- ***************************************************** -->
1314
1315   </sect1>
1316  </chapter>
1317 </book>