--- /dev/null
+<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook V4.1//EN"[]>
+
+<book id="GAVLdoc">
+ <bookinfo>
+ <title>Generic AVL Tree Implementation (GAVL)</title>
+
+ <authorgroup>
+ <author>
+ <firstname>Pavel</firstname>
+ <surname>Pisa</surname>
+ <affiliation>
+ <address>
+ <email>pisa@cmp.felk.cvut.cz</email>
+ </address>
+ </affiliation>
+ </author>
+ </authorgroup>
+
+ <copyright>
+ <year>2003</year>
+ <holder>Pavel Pisa</holder>
+ </copyright>
+
+ <abstract>
+ <para>Implementation of AVL tree with some interesting features.
+ All algorithms for insertion, deletion, traversal etc. are implemented without
+ function call recursion or tree node stacks. The only exception is routine to
+ check correctness of tree used for debugging purposes. The implementation has
+ more advantages. It can work with partially unbalanced trees with balance
+ factor (height difference) outside range <-1,1>. The balancing
+ subroutine is common for insertion and deletion. Provided macros enables
+ to build trees with strict item type checking which avoids necessity to use
+ type-casting from (void *).
+ </para>
+ </abstract>
+
+ </bookinfo>
+
+ <toc></toc>
+
+ <chapter id="intro">
+ <title>Introduction</title>
+ <para>
+ There are more concepts how to store data items sorted by some key values.
+ The most commonly used ones are:
+ <itemizedlist>
+ <listitem>
+ <para>sorted conntinuous arrays of items or pointers to items</para>
+ </listitem>
+ <listitem>
+ <para>binary search trees (splash tree, AVL-tree, RB-tree)</para>
+ </listitem>
+ <listitem>
+ <para>more childs per node search trees (B-tree)</para>
+ </listitem>
+ </itemizedlist>
+ </para>
+ <para>
+ The binary search trees are considered most efficient for in memory
+ operations when frequent tree updates are present. If update frequency
+ is very low, sorted arrays of pointers could be more efficient. If the
+ node retrieval operations are time consuming the n-nary search trees
+ could be used.
+ </para>
+ <para>
+ The provided GAVL library tries to offer fast and API friendly
+ set of functions and macros usable for in-memory stored AVL trees
+ of user specified items. The tree node chaining informations
+ must be added to each stored item for holding of the tree node
+ topology. The GAVL library can use user specified field of items
+ or small malloced structure for holding of node chaining information.
+ </para>
+ <para>
+ The tree search, insert and delete functions can work with and enforce tree
+ with unique items or can be used in mode when more items with same
+ search key value are allowed. The balancing and other functions
+ are written such way, that they tolerate even degraded tree
+ which does not fulfill AVL tree definition. The operations do not
+ result in further degradation or program exceptions.
+ Even future tree operations tends to enhance balancing if the height
+ differences (balance factors) of degraded tree has been correctly updated.
+ </para>
+
+
+ </chapter>
+
+ <chapter id="gavlfunc">
+ <title>Functions Description</title>
+ <sect1><title>Generic AVL tree</title>
+!F../../ulut/ul_gavl.h
+!F../../ulut/ul_gavlprim.c
+!F../../ulut/ul_gavl.c
+ </sect1>
+ <sect1><title>Custom AVL Tree Instances</title>
+ <para>
+ The provided macros allows to define all AVL tree
+ functions for tree with user defined root and item types.
+ The next defined function names are prefixed by custom selected
+ <replaceable>cust_prefix</replaceable>:
+
+ <variablelist>
+
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_node2item</function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef>const gavl_node_t * <parameter>node</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Conversion from AVL tree node to user custom defined item
+ </para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_key_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_node2key </function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef>const gavl_node_t * <parameter>node</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Conversion from AVL tree node to pointer to defined ordering key
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef>int <function><replaceable>cust_prefix</replaceable>_search_node </function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef>const <replaceable>cust_item_t</replaceable> * <parameter>key</parameter></paramdef>
+ <paramdef>gavl_node_t ** <parameter>nodep</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Search for node or place for node by key
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_find </function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef>const <replaceable>cust_key_t</replaceable> * <parameter>key</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Pointer to item with key value or <constant>NULL</constant>
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_find_first </function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef>const <replaceable>cust_key_t</replaceable> * <parameter>key</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Same as above, but first matching item is found.
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_find_after </function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef>const <replaceable>cust_key_t</replaceable> * <parameter>key</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Finds the first item with key value higher than value pointed
+ by <parameter>key</parameter> or returns <constant>NULL</constant>.
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef>int <function><replaceable>cust_prefix</replaceable>_insert </function></funcdef>
+ <paramdef><replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef><replaceable>cust_item_t</replaceable> * <parameter>item</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Insert new item into AVL tree. If the operation is successful
+ positive value is returned. If key with same key value already
+ exists negative value is returned
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef>int <function><replaceable>cust_prefix</replaceable>_delete_node </function></funcdef>
+ <paramdef><replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef>gavl_node_t * <parameter>node</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Deletes/unlinks node from custom AVL tree
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef>int <function><replaceable>cust_prefix</replaceable>_delete </function></funcdef>
+ <paramdef><replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef><replaceable>cust_item_t</replaceable> * <parameter>item</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Deletes/unlinks item from custom AVL tree
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef>gavl_node_t * <function><replaceable>cust_prefix</replaceable>_first_node </function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Returns the first node or <constant>NULL</constant> if the tree is empty
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef>gavl_node_t * <function><replaceable>cust_prefix</replaceable>_last_node </function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Returns last node or <constant>NULL</constant> if the tree is empty
+ </para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_first</function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Returns pointer to the first item of the tree or <constant>NULL</constant>
+ </para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_last</function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Returns pointer to last item of the tree or <constant>NULL</constant>
+ </para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_next</function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef>const <replaceable>cust_item_t</replaceable> * <parameter>item</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Returns pointer to next item of the tree or <constant>NULL</constant>
+ if there is no more items
+ </para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_prev</function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ <paramdef>const <replaceable>cust_item_t</replaceable> * <parameter>item</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Returns pointer to previous item of the tree or <constant>NULL</constant>
+ if there is no more items
+ </para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef>int <function><replaceable>cust_prefix</replaceable>_is_empty </function></funcdef>
+ <paramdef>const <replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Returns non-zero value if there is no node in the tree
+ </para>
+ </listitem>
+ </varlistentry>
+
+ <varlistentry>
+ <term>
+ <funcsynopsis><funcprototype>
+ <funcdef><replaceable>cust_item_t</replaceable> * <function><replaceable>cust_prefix</replaceable>_cut_first </function></funcdef>
+ <paramdef><replaceable>cust_root_t</replaceable> * <parameter>root</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </term>
+ <listitem>
+ <para>
+ Returns the first item or <constant>NULL</constant> if the tree is empty.
+ The returned item is unlinked from the tree without tree rebalance
+ </para>
+ </listitem>
+ </varlistentry>
+
+ </variablelist>
+
+ </para>
+
+ <refentry>
+ <refmeta>
+ <refentrytitle><phrase id="API-GAVL-CUST-NODE-INT-IMP">GAVL_CUST_NODE_INT_IMP</phrase></refentrytitle>
+ </refmeta>
+ <refnamediv>
+ <refname>GAVL_CUST_NODE_INT_IMP</refname>
+ <refpurpose>
+ Implementation of new custom tree with internal node
+ </refpurpose>
+ </refnamediv>
+ <refsynopsisdiv>
+ <title>Synopsis</title>
+ <funcsynopsis><funcprototype>
+ <funcdef> <function>GAVL_CUST_NODE_INT_IMP </function></funcdef>
+ <paramdef> <parameter>cust_prefix</parameter></paramdef>
+ <paramdef> <parameter>cust_root_t</parameter></paramdef>
+ <paramdef> <parameter>cust_item_t</parameter></paramdef>
+ <paramdef> <parameter>cust_key_t</parameter></paramdef>
+ <paramdef> <parameter>cust_root_node</parameter></paramdef>
+ <paramdef> <parameter>cust_item_node</parameter></paramdef>
+ <paramdef> <parameter>cust_item_key</parameter></paramdef>
+ <paramdef> <parameter>cust_cmp_fnc</parameter></paramdef>
+ </funcprototype></funcsynopsis>
+ </refsynopsisdiv>
+ <refsect1>
+ <title>Arguments</title>
+ <variablelist>
+ <varlistentry>
+ <term><parameter>cust_prefix</parameter></term>
+ <listitem>
+ <para>
+ defines prefix for builded function names
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term><parameter>cust_root_t</parameter></term>
+ <listitem>
+ <para>
+ user defined structure type of root of the tree
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term><parameter>cust_item_t</parameter></term>
+ <listitem>
+ <para>
+ user defined structure type of items stored in the tree
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term><parameter>cust_key_t</parameter></term>
+ <listitem>
+ <para>
+ type of the key used for sorting of the items
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term><parameter>cust_root_node</parameter></term>
+ <listitem>
+ <para>
+ the field of the root structure pointing to the tree root node
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term><parameter>cust_item_node</parameter></term>
+ <listitem>
+ <para>
+ the field of item structure used for chaining of items
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term><parameter>cust_item_key</parameter></term>
+ <listitem>
+ <para>
+ the key field of item structure defining order of items
+ </para>
+ </listitem>
+ </varlistentry>
+ <varlistentry>
+ <term><parameter>cust_cmp_fnc</parameter></term>
+ <listitem>
+ <para>
+ the keys compare function
+ </para>
+ </listitem>
+ </varlistentry>
+ </variablelist>
+ </refsect1>
+ <refsect1>
+ <title>Description</title>
+ <para>
+ There are two macros designed for building custom AVL trees. The macro
+ <constant>GAVL_CUST_NODE_INT_DEC</constant> declares functions for custom tree manipulations
+ and is intended for use in header files.
+ The macro <constant>GAVL_CUST_NODE_INT_IMP</constant> builds implementations for non-inlined
+ functions declared by <constant>GAVL_CUST_NODE_INT_DEC</constant>. The <parameter>cust_cmp_fnc</parameter> is used
+ for comparison of item keys in the search and insert functions. The types
+ of two input arguments of <parameter>cust_cmp_fnc</parameter> functions must correspond
+ with <parameter>cust_key_t</parameter> type. Return value should be positive for case when
+ the first pointed key value is greater then second, negative for reverse
+ case and zero for equal pointed values.
+ </para>
+ </refsect1>
+ </refentry>
+
+
+ </sect1>
+ </chapter>
+
+ <chapter id="gavlexample">
+ <title>Examples of GAVL Usage</title>
+ <sect1><title>Generic AVL Tree</title>
+ <para>
+ This chapter describes use of generic AVL tree. This tree has advantage,
+ that same functions could operate with any user provided items, but
+ operations return type is <type>void</type>* and needs type-casting to
+ user item type.
+ </para>
+ <programlisting>#include <malloc.h>
+#include "ul_gavl.h"</programlisting>
+
+ <para>
+ The above code fragment includes basic GAVL declarations.
+ </para>
+
+ <programlisting>typedef struct test1_item {
+ int my_val;
+ /* more user data ... */
+} test1_item_t;</programlisting>
+
+ <para>
+ New item type is declared. Type have to contain or be connected to
+ some key value. The <type>integer</type> number
+ <structfield>my_val</structfield> will be used as key value in this example.
+ The tree root instance definition follows.
+ </para>
+
+ <programlisting>gavl_root_t test1_tree={
+ .root_node = NULL,
+ .node_offs = -1,
+ .key_offs = UL_OFFSETOF(test1_item_t, my_val),
+ .cmp_fnc = gavl_cmp_int
+};</programlisting>
+
+ <para>
+ The field <structfield>root_node</structfield> have to be initialized to
+ <constant>NULL</constant>.
+ The value -1 for the <structfield>node_offs</structfield> field directs
+ GAVL functions to allocate external node structure for each inserted item.
+ The macro <constant>UL_OFFSETOF</constant> computes offset of
+ <structfield>my_val</structfield> field in <type>test1_item_t</type>
+ item. The last assignment select one of predefined functions for
+ key values comparison.
+ </para>
+
+ <para>
+ Almost same declarations and definitions could be used if the node
+ chaining structure is contained inside item structure. That is shown in
+ the next code fragments.
+ </para>
+
+ <programlisting>typedef struct test2_item {
+ gavl_node_t my_node;
+ int my_val;
+ /* more user data ... */
+} test2_item_t;</programlisting>
+
+ <para>
+ The item declaration contains field with <type>gavl_node_t</type> type
+ in this case. This field is used for storage of tree topology information.
+ </para>
+
+ <programlisting>gavl_root_t test2_tree={
+ .root_node = NULL,
+ .node_offs = UL_OFFSETOF(test2_item_t, my_node),
+ .key_offs = UL_OFFSETOF(test2_item_t, my_val),
+ .cmp_fnc = gavl_cmp_int
+};</programlisting>
+
+ <para>
+ The field <structfield>node_offs</structfield> contains offset of the
+ node structure inside item now. Next fragments are part of the function
+ working with defined tree. There would be no difference in the functions
+ calls for items with external nodes.
+ </para>
+
+ <programlisting> cust2_item_t *item;
+ int i;
+ gavl_node_t *node;</programlisting>
+
+ <para>
+ Declare some local variables first. Insert 100 items into tree then.
+ </para>
+
+ <programlisting> for(i=0;i<items_cnt;i++){
+ item=malloc(sizeof(test2_item_t));
+ item->my_val=i;
+ if(gavl_insert(&test2_tree,item,0)<0)
+ printf("gavl_insert error\n");
+ }</programlisting>
+
+ <para>
+ The tree is expected to store items with unique key values.
+ If more items with same key values should be allowed, then the
+ value of <parameter>mode</parameter> parameter in <function>gavl_insert</function>
+ function call have to be changed from 0 to <constant>GAVL_FAFTER</constant>.
+ </para>
+
+ <programlisting> for(i=0;i<102;i++){
+ if(!(item=(cust2_item_t *)gavl_find(&test2_tree,&i)))
+ printf("no item %d\n",i);
+ else
+ if(item->my_val!=i)
+ printf("gavl_find mismatch\n");
+ }</programlisting>
+
+ <para>
+ Some test of retrieving item corresponding to specified key.
+ The tree in order traversal is in the next code sample.
+ </para>
+
+ <programlisting> node=gavl_first_node(&test2_tree)
+ while(node){
+ item=(cust2_item_t *)gavl_node2item(&test2_tree,node);
+ /* do something with item
+ * insert and delete allowed there except delete of the actual item
+ */
+ node=gavl_next_node(node);
+ /* do something with item
+ * insert and delete allowed there except delete of next item
+ */
+ }</programlisting>
+
+ <para>
+ Example of the item deletion is in the next fragment.
+ The function <function>gavl_delete</function>
+ guarantees that trial of deleting item, which is not part of the tree,
+ is detected and negative value is returned. There is one prerequisite
+ for this behavior for items with internal nodes that have never been
+ part of any tree. The field <structfield>parent</structfield>
+ of node structure stored in the item have to be initialized to
+ <constant>NULL</constant> value.
+ </para>
+
+ <programlisting> for(i=0;i<80;i++){
+ if(!(item=(cust2_item_t *)gavl_find(&test2_tree,&i)))
+ continue;
+ if(gavl_delete(&test2_tree,item)<0)
+ printf("gavl_delete error\n");
+ free(item);
+ }</programlisting>
+
+ <para>
+ The function <function>gavl_cut_first</function> can significantly simplify
+ deletion of all nodes of the tree without need of traversal over the tree.
+ This function does not rebalance the tree, but keeps tree consistent.
+ </para>
+
+ <programlisting> while((item=(cust2_item_t *)gavl_cut_first(&test2_tree))!=NULL)
+ free(item);</programlisting>
+ </sect1>
+
+ <sect1><title>Customized AVL Tree</title>
+ <para>
+ The function templates are provided for faster and type-safe
+ custom tree definition and manipulation. These templates expect
+ user defined items with internal node structures and key comparison
+ function with key pointer input parameters. The type of these
+ parameters is required to be pointer to the key type.
+ </para>
+ <para>
+ Next code fragment is intended to be part of the declarations
+ of user defined custom tree and items for some data storage
+ purpose. The header with these definitions should be included
+ from all modules directly working with specified tree.
+ </para>
+
+ <programlisting>#include "ul_gavl.h"
+
+typedef int cust_key_t;
+
+typedef struct cust2_item {
+ cust2_key_t my_val;
+ gavl_node_t my_node;
+ /* more user item data ... */
+} cust2_item_t;
+
+typedef struct cust2_root {
+ gavl_node_t *my_root;
+ /* more user root/tree data ... */
+} cust2_root_t;
+
+int cust_cmp_fnc(cust_key_t *a, cust_key_t *b);</programlisting>
+
+ <para>
+ As can be seen from above code fragment, the key field with user declared
+ type (<type>cust_key_t</type>) and internal node structure are required
+ for items. The only one field with type <type>gavl_node_t</type>* is required
+ for the custom tree root structure.
+ </para>
+ <para>
+ The use of the macro <constant>GAVL_CUST_NODE_INT_DEC</constant> declares
+ all tree manipulation functions for the custom tree. The function names are
+ prefixed by prefix specified as the first parameter of macro invocation.
+ This declaration can be included in user header files as well.
+ </para>
+
+ <programlisting>GAVL_CUST_NODE_INT_DEC(cust2, cust2_root_t, cust2_item_t, cust2_key_t,\
+ my_root, my_node, my_val, cust_cmp_fnc)</programlisting>
+
+ <para>
+ The implementation of the custom tree functions is realized
+ by use of macro <constant>GAVL_CUST_NODE_INT_IMP</constant> with same
+ parameters as for <constant>GAVL_CUST_NODE_INT_DEC</constant> macro.
+ </para>
+
+ <programlisting>#include "ul_gavlcust.h"
+
+GAVL_CUST_NODE_INT_IMP(cust2, cust2_root_t, cust2_item_t, cust2_key_t,\
+ my_root, my_node, my_val, cust_cmp_fnc)
+
+cust2_root_t cust2_tree;</programlisting>
+
+ <para>
+ Static tree root instance is included at last line of above code fragment as well.
+ </para>
+ <para>
+ The next sample function for the custom tree shows same operation
+ as have been described for generic tree.
+ </para>
+
+ <programlisting>void test_cust_tree(void)
+{
+ int i;
+ cust2_item_t *item;
+
+ /* build tree */
+ for(i=1;i<=100;i++){
+ item=malloc(sizeof(cust2_item_t));
+ item->my_val=i;
+ if(cust2_insert(&cust2_tree,item)<0)
+ printf("cust2_insert error\n");
+ }
+
+ /* traverse tree */
+ printf("Custom tree cust2:\n");
+ for(item=cust2_first(&cust2_tree);item;item=cust2_next(&cust2_tree,item))
+ printf("%d ",item->my_val);
+ printf("\n");
+
+ /* delete part of the tree */
+ for(i=1;i<=80;i++){
+ item=cust2_find(&cust2_tree,&i);
+ if(cust2_delete(&cust2_tree,item)<0)
+ printf("cust2_delete error\n");
+ free(item);
+ }
+
+ /* traverse in reverse order */
+ printf("Custom tree cust2:\n");
+ for(item=cust2_last(&cust2_tree);item;item=cust2_prev(&cust2_tree,item))
+ printf("%d ",item->my_val);
+ printf("\n");
+
+ /* delete all remaining items */
+ while((item=cust2_cut_first(&cust2_tree))!=NULL)
+ free(item);
+}</programlisting>
+
+ </sect1>
+ </chapter>
+
+<!--
+<equation>
+ <title>A TeX Equation</title>
+ <mediaobject>
+ <imageobject role="html">
+ <imagedata fileref="texmath.png" format="PNG">
+ </imageobject>
+ <textobject role="tex"><phrase>$C = \alpha + \beta Y^{\gamma}
+ + \epsilon$</phrase></textobject>
+ </mediaobject>
+</equation>
+-->
+
+ <chapter id="gavlalg">
+ <title>Used Algorithms Background</title>
+ <sect1><title>Tree Balancing Operations</title>
+ <para>
+ This section describes used algorithms for keeping
+ AVL tree balanced.
+ </para>
+
+<!-- ***************************************************** -->
+
+ <para>Next convention is used for height and balance computations for node
+ <inlineequation>
+ <alt>$\textrm{X}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>. The height of subtree starting at
+ <inlineequation>
+ <alt>$\textrm{X}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> is labeled as
+ <inlineequation>
+ <alt>$x=height(\textrm{X})$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>. Height difference (balance factor) for node
+ <inlineequation>
+ <alt>$\textrm{X}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> is labeled as
+ <inlineequation>
+ <alt>$\Delta x=height(left(\textrm{X}))-height(right(\textrm{X}))$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>.
+ </para>
+ <sect2>
+ <title>Tree Balancing Case 1</title>
+ <para>
+ <figure>
+ <title>Tree balancing case 1</title>
+ <mediaobject>
+ <imageobject>
+ <imagedata align="center" fileref="fig/gavl_t11.pdf" format="EPS" scale="75" >
+ </imageobject>
+ <imageobject>
+ <imagedata align="center" fileref="fig/gavl_t11.gif" format="GIF" scale="75" >
+ </imageobject>
+ <caption><para>Before operation</para></caption>
+ </mediaobject>
+ <mediaobject>
+ <imageobject>
+ <imagedata align="center" fileref="fig/gavl_t12.pdf" format="EPS" scale="75" >
+ </imageobject>
+ <imageobject>
+ <imagedata align="center" fileref="fig/gavl_t12.gif" format="GIF" scale="75" >
+ </imageobject>
+ <caption><para>After operation</para></caption>
+ </mediaobject>
+ </figure>
+ </para>
+ <para>
+ <equation>
+ <alt>\begin{eqnarray*}
+\Delta s & = & n-b\qquad \geq 2\\
+\Delta n & = & a-p\qquad \geq 0
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation> The height of subtree
+ <inlineequation>
+ <alt>$\textrm{S}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> is defined by highest branch, which is branch grovinggrowing from node
+ <inlineequation>
+ <alt>$\textrm{A}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>. This leads to next equations.
+ <equation>
+ <alt>\begin{eqnarray*}
+n & = & a+1\\
+s & = & a+2\\
+p & = & a-\Delta n\\
+b & = & a+1-\Delta s
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>The height of branches
+ <inlineequation>
+ <alt>$\textrm{N}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> and
+ <inlineequation>
+ <alt>$\textrm{S}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> is marked as
+ <inlineequation>
+ <alt>$n1$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> and
+ <inlineequation>
+ <alt>$s1$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> after balancing.
+ <equation>
+ <alt>\begin{eqnarray*}
+\Delta s1 & = & p-b\\
+\Delta n1 & = & a-s1
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>
+ <equation>
+ <alt>\begin{eqnarray*}
+s1 & = & \max (p,b)+1\\
+s1 & = & \max (a-\Delta n,a+1-\Delta s)+1\\
+s1 & = & a+1+\max (-\Delta n,1-\Delta s)\\
+s1 & = & a+1-\min (\Delta n,\Delta s-1)
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>
+ <equation>
+ <alt>\begin{eqnarray*}
+\Delta s1 & = & a-\Delta n-a-1+\Delta s\\
+\Delta s1 & = & \Delta s-\Delta n-1\\
+\Delta n1 & = & a-a-1+\min (\Delta n,\Delta s-1)\\
+\Delta n1 & = & \min (\Delta n-1,\Delta s-2)\\
+\Delta n1 & = & \left\langle \begin{array}{cc}
+ \Delta n-1 & \qquad \Delta s\geq \Delta n+1\\
+ \Delta s-2 & \qquad \Delta s\leq \Delta n+1\end{array}
+\right.
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </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).
+ <equation>
+ <alt>\begin{eqnarray*}
+s-n1 & = & s-(\max (a,s1)+1)\\
+ & = & a+2-(\max (a,a+1+\max (-\Delta n,1-\Delta s))+1)\\
+ & = & 1-\max (0,\max (1-\Delta n,2-\Delta s))\\
+ & = & \min (1,\Delta n,\Delta s-1)\qquad \Delta n\geq 0,\Delta s\geq 2\\
+ & = & \min (1,\Delta n)\\
+s-n1 & = & \left\langle \begin{array}{cc}
+ 1 & \qquad \Delta n\neq 0\\
+ 0 & \qquad \Delta n=1\end{array}
+\right.
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation></para></sect2>
+ <sect2><title>Tree Balancing Case 2</title>
+ <para>
+ <figure>
+ <title>Tree balancing case 2</title>
+ <mediaobject>
+ <imageobject>
+ <imagedata align="center" fileref="fig/gavl_t21.pdf" format="EPS" scale="75" >
+ </imageobject>
+ <imageobject>
+ <imagedata align="center" fileref="fig/gavl_t21.gif" format="GIF" scale="75" >
+ </imageobject>
+ <caption><para>Before operation</para></caption>
+ </mediaobject>
+ <mediaobject>
+ <imageobject>
+ <imagedata align="center" fileref="fig/gavl_t22.pdf" format="EPS" scale="75" >
+ </imageobject>
+ <imageobject>
+ <imagedata align="center" fileref="fig/gavl_t22.gif" format="GIF" scale="75" >
+ </imageobject>
+ <caption><para>After operation</para></caption>
+ </mediaobject>
+ </figure>
+ </para>
+ <para>This case has advantage, that it reduces tree height for all node height combinations. Tree height is given by branch
+ <inlineequation>
+ <alt>$\textrm{P}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>
+ <inlineequation>
+ <alt>$\textrm{B}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> or
+ <inlineequation>
+ <alt>$\textrm{P}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>
+ <inlineequation>
+ <alt>$\textrm{C}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>.
+ <equation>
+ <alt>\begin{eqnarray*}
+\Delta s & = & n-d\qquad \geq 2\\
+\Delta n & = & a-p\qquad \leq -1
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>
+ <equation>
+ <alt>\begin{eqnarray*}
+n & = & p+1\\
+s & = & p+2\\
+d & = & p+1-\Delta s\\
+a & = & p+\Delta n
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>
+ <equation>
+ <alt>\begin{eqnarray*}
+\textrm{for}\, b\geq c\qquad c & = & b-\Delta p\qquad p=b+1\\
+\textrm{for}\, c\geq b\qquad b & = & c+\Delta p\qquad p=c+1
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>When
+ <inlineequation>
+ <alt>$b\geq c$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> then the height differences
+ <inlineequation>
+ <alt>$\Delta s1$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>,
+ <inlineequation>
+ <alt>$\Delta n1$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> and
+ <inlineequation>
+ <alt>$\Delta p1$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> for nodes
+ <inlineequation>
+ <alt>$\textrm{S}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>,
+ <inlineequation>
+ <alt>$\textrm{N}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> and
+ <inlineequation>
+ <alt>$\textrm{P}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> of the balanced tree can be computed from next equations.
+ <equation>
+ <alt>\begin{eqnarray*}
+b\geq c & , & \Delta p\geq 0\\
+n1 & = & b+1\\
+p1 & = & b+2\\
+s1 & = & \max (c,d)+1=\max (b-\Delta p,b+2-\Delta s)+1\\
+\Delta s1 & = & c-d=b-\Delta p-b-2+\Delta s\\
+\Delta s1 & = & \Delta s-2-\Delta p\\
+\Delta n1 & = & a-b=b+1+\Delta n-b\\
+\Delta n1 & = & \Delta n+1\\
+\Delta p1 & = & n1-s1=b+1-\max (b-\Delta p,b+2-\Delta s)-1\\
+\Delta p1 & = & \min (\Delta p,\Delta s-2)\qquad \Delta p\geq 0,\Delta s\geq 2
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>When
+ <inlineequation>
+ <alt>$c\geq b$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> then the height differences
+ <inlineequation>
+ <alt>$\Delta s1$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>,
+ <inlineequation>
+ <alt>$\Delta n1$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> and
+ <inlineequation>
+ <alt>$\Delta p1$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> for nodes
+ <inlineequation>
+ <alt>$\textrm{S}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation>,
+ <inlineequation>
+ <alt>$\textrm{N}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> and
+ <inlineequation>
+ <alt>$\textrm{P}$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> of the balanced tree can be computed from next equations.
+ <equation>
+ <alt>\begin{eqnarray*}
+c\geq b & , & \Delta p\leq 0\\
+s1 & = & c+1\\
+p1 & = & c+2\\
+n1 & = & \max (a,b)+1=\max (c+1+\Delta n,c+\Delta p)+1\\
+\Delta s1 & = & c-d=c-c-2+\Delta s\\
+\Delta s1 & = & \Delta s-2\\
+\Delta n1 & = & a-b=c+1+\Delta n-c-\Delta p\\
+\Delta n1 & = & \Delta n+1-\Delta p\\
+\Delta p1 & = & n1-s1=\max (c+1+\Delta n,c+\Delta p)+1-c-1\\
+\Delta p1 & = & \max (\Delta n,\Delta s-1)\qquad \Delta n\leq -1,\Delta p\leq 0
+\end{eqnarray*}
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation></para></sect2>
+</sect1>
+<sect1><title>Height of the AVL Tree</title><para>Minimal number of nodes
+ <inlineequation>
+ <alt>$T$
+ </alt>
+ <inlinemediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </inlinemediaobject>
+ </inlineequation> can be computed recursively.
+ <equation>
+ <alt>\[
+T(h)=T(h-1)+T(h-2)+1,\, T(0)=0,\, T(1)=1\]
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986</para><para>
+ <equation>
+ <alt>\[
+T(h)=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{(h+2)}-1\]
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>
+ <equation>
+ <alt>\[
+T(h)=\frac{1}{\sqrt{5}}\, 2^{(h+2)\, log_{2}\left(\frac{1+\sqrt{5}}{2}\right)}-1\]
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>
+ <equation>
+ <alt>\[
+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\]
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </equation>
+ <equation>
+ <alt>\[
+log_{2}^{-1}\left(\frac{1+\sqrt{5}}{2}\right)=1.44042\]
+
+ </alt>
+ <mediaobject>
+ <imageobject>
+ <imagedata fileref="img/gavl_eq1.gif" format="GIF">
+ </imageobject>
+ </mediaobject>
+ </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>
+
+<!-- ***************************************************** -->
+
+ </sect1>
+ </chapter>
+</book>
projects / ulut.git / commitdiff