<h4>8.1 <span class="Heading">The idea of AVL trees</span></h4>
<p>AVL trees are balanced binary trees called <q>AVL trees</q> in honour of their inventors G.M. Adelson-Velskii and E.M. Landis (see <a href="chapBib.html#biBAVL">[AM62]</a>). A description in English can be found in <a href="chapBib.html#biBACP3">[Knu97]</a> in Section 6.2.3 about balanced trees.</p>
<p>The general idea is to store data in a binary tree such that all entries in the left subtree of a node are smaller than the entry at the node and all entries in the right subtree are bigger. The tree is kept <q>balanced</q> which means that for each node the depth of the left and right subtrees differs by at most 1. In this way, finding something in the tree, adding a new entry, deleting an entry all have complexity <span class="SimpleMath">log(n)</span> where <span class="SimpleMath">n</span> is the number of entries in the tree. If one additionally stores the number of entries in the left subtree of each node, then finding the <span class="SimpleMath">k</span>-th entry, removing the <spanclass="SimpleMath">k</span>-th entry and inserting an entry in position <span class="SimpleMath">k</span> also have complexity <span class="SimpleMath">log(n)</span>. The <strong class="pkg">orb</strong> contains an implementation of such tree objects providing all these operations.</p>
<p><q>Entries</q> in AVL tree objects are key-value pairs and the sorting is done by the key. If all values as <code class="keyw">true</code> then no memory is needed to store the values (see the corresponding behaviour for hash tables). The only requirement on the type of the keys is that two arbitrary keys must be comparable in the sense that one can decide which of them is smaller. If <strong class="pkg">GAP</strong>s standard comparison operations <span class="SimpleMath"><</span> and <span class="SimpleMath">=</span> work for your keys, no further action is required, if not, then you must provide your own three-way comparison function (see below).</p>
<p>Note that the AVL trees implemented here can be used in basically two different ways, which can sometimes be mixed: The usual way is by accessing entries by their key, the tree is then automatically kept sorted. The alternative way is by accessing entries by their index in the tree! Since the nodes of the trees remember how many elements are stored in their left subtree, it is in fact possible to access the <span class="SimpleMath">k</span>-th entry in the tree or delete it. It is even possible to insert something in position <span class="SimpleMath">k</span>. However, note that if you do this latter operation, you are yourself responsible to keep the entries in the tree sorted. You can ignore this responsibility, but then you can no longer access the entries in the tree by their key and the corresponding functions might fail or even run into errors.</p>
<p>This usage can be useful, since in this way AVL trees provide an implementation of a list data structure where the operation list access (by index), adding an element (in an arbitrary position) and deleting an element (by its index) all have complexity <span class="SimpleMath">log(n)</span> where <span class="SimpleMath">n</span> is the number of entries in the list.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLTree</code>( [<var class="Arg">opt</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A new AVL tree object</p>
<p>This function creates a new AVL tree object. The optional argument <var class="Arg">opt</var> is an options record, in which you can bind the following components:</p>
<p><code class="code">cmpfunc</code> is a three-way comparison function taking two arguments <varclass="Arg">a</var> and <var class="Arg">b</var> and returning <span class="SimpleMath">-1</span> if <span class="SimpleMath"><var class="Arg">a</var> < <var class="Arg">b</var></span>, <span class="SimpleMath">+1</span> if <span class="SimpleMath"><var class="Arg">a</var> > <var class="Arg">b</var></span> and <span class="SimpleMath">0</span> if <span class="SimpleMath"><var class="Arg">a</var> = <var class="Arg">b</var></span>. If no function is given then the generic function <code class="func">AVLCmp</code> (<a href="chap8.html#X83EC43DA871C7F60"><span class="RefLink">8.2-2</span></a>) is taken. This three-way comparison function is stored with the tree and is used for all comparisons in tree operations. <code class="code">allocsize</code> is the number of nodes which are allocated for the tree initially. It can be useful to specify this if you know that your tree will eventually contain a lot of entries, since then the tree object does not have to grow that many times.</p>
<p>For every AVL tree a three-way comparison function is needed, usually you can get away with using the following default one:</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLCmp</code>( <var class="Arg">a</var>, <var class="Arg">b</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: -1, 0 or 1</p>
<p>This function calls the <code class="keyw"><</code> operation and the <code class="keyw">=</code> operation to provide a generic three-way comparison function to be used in AVL tree operations. See <code class="func">AVLTree</code> (<a href="chap8.html#X791E346F84F0430C"><span class="RefLink">8.2-1</span></a>) for a description of the return value. This function is implemented in the kernel and should be particularly fast.</p>
<p>The following functions are used to access entries by key:</p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function stores the key <var class="Arg">key</var> with value <var class="Arg">value</var> in the tree assuming that the keys in it are sorted according to the three-way comparison function stored with the tree. If <var class="Arg">value</var> is <code class="keyw">true</code> then no additional memory is needed. It is an error if there is already a key equal to <var class="Arg">key</var> in the tree, in this case the function returns <code class="keyw">fail</code>. Otherwise it returns <code class="keyw">true</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLLookup</code>( <var class="Arg">t</var>, <var class="Arg">key</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an value or <code class="keyw">fail</code></p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function looks up the key <varclass="Arg">key</var> in the tree and returns the value which is associated to it. If the key is not in the tree, the value <code class="keyw">fail</code> is returned. This function assumes that the keys in the tree are sorted according to the three-way comparison function stored with the tree.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLDelete</code>( <var class="Arg">t</var>, <var class="Arg">key</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an value or <code class="keyw">fail</code></p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function looks up the key <varclass="Arg">key</var> in the tree, deletes it and returns the value which was associated with it. If <var class="Arg">key</var> is not contained in the tree then <code class="keyw">fail</code> is returned. This function assumes that the keys in the tree are sorted according to the three-way comparison function stored with the tree.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLFindIndex</code>( <var class="Arg">t</var>, <var class="Arg">key</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an integer or <code class="keyw">fail</code></p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function looks up the key <varclass="Arg">key</var> in the tree and returns the index, under which it is stored in the tree. This index is one-based, that is, it takes values from 1 to the number of entries in the tree. If <var class="Arg">key</var> is not contained in the tree then <code class="keyw">fail</code> is returned. This function assumes that the keys in the tree are sorted according to the three-way comparison function stored with the tree.</p>
<p>The following functions are used to access entries in trees by their index:</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLIndex</code>( <var class="Arg">t</var>, <var class="Arg">index</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a key or <code class="keyw">fail</code></p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function returns the key at index <var class="Arg">index</var> in the tree, so <var class="Arg">index</var> must be an integer in the range 1 to the number of elements in the tree. If the value is out of these bounds, <code class="keyw">fail</code> is returned. Note that to use this function it is not necessary that the keys in the tree are sorted according to the three-way comparison function stored with the tree.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLIndexLookup</code>( <var class="Arg">t</var>, <var class="Arg">index</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a value or <code class="keyw">fail</code></p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function returns the value associated to the key at index <var class="Arg">index</var> in the tree, so <var class="Arg">index</var> must be an integer in the range 1 to the number of elements in the tree. If the value is out of these bounds, <code class="keyw">fail</code> is returned. Note that to use this function it is not necessary that the keys in the tree are sorted according to the three-way comparison function stored with the tree.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLIndexAdd</code>( <var class="Arg">t</var>, <var class="Arg">key</var>, <var class="Arg">value</var>, <var class="Arg">index</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a key or <code class="keyw">fail</code></p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function inserts the key <varclass="Arg">key</var> at index <var class="Arg">index</var> in the tree and associates the value <varclass="Arg">value</var> with it. If <var class="Arg">value</var> is <code class="keyw">true</code> then no additional memory is needed to store the value. The index <var class="Arg">index</var> must be an integer in the range 1 to <span class="SimpleMath">n+1</span> where <span class="SimpleMath">n</span> is the number of entries in the tree. The new key is inserted before the key which currently is stored at index <var class="Arg">index</var>, so calling with <var class="Arg">index</var> equal to <span class="SimpleMath">n+1</span> puts the new key at the end. If <var class="Arg">index</var> is not in the corrent range, this function returns <code class="keyw">fail</code> and the tree remains unchanged.</p>
<p><strong class="button">Caution:</strong> With this function it is possible to put a key into the tree at a position such that the keys in the tree are no longer sorted according to the three-way comparison function stored with the tree! If you do this, the functions <code class="func">AVLAdd</code> (<a href="chap8.html#X7F65886F84E991C7"><span class="RefLink">8.2-3</span></a>), <code class="func">AVLLookup</code> (<a href="chap8.html#X7E6EF8297C68F553"><span class="RefLink">8.2-4</span></a>), <code class="func">AVLDelete</code> (<a href="chap8.html#X82CE14F17B5DD6B2"><span class="RefLink">8.2-5</span></a>) and <code class="func">AVLFindIndex</code> (<a href="chap8.html#X7D1B85DA814DA26C"><span class="RefLink">8.2-6</span></a>) will no longer work since they assume that the keys are sorted!</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLIndexDelete</code>( <var class="Arg">t</var>, <var class="Arg">index</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a key or <code class="keyw">fail</code></p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function deletes the key at index <var class="Arg">index</var> in the tree and returns the value which was associated with it.</p>
<p>The following functions allow low level access to the AVL tree object:</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLFind</code>( <var class="Arg">t</var>, <var class="Arg">key</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an integer or <code class="keyw">fail</code></p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function locates the key <varclass="Arg">key</var> in the tree and returns the position in the positional object, at which the node which contains the key is stored. This position will always be divisible by 4. Use the functions <code class="func">AVLData</code> (<a href="chap8.html#X78B2EEB4804987F2"><span class="RefLink">8.2-13</span></a>) and <code class="func">AVLValue</code> (<a href="chap8.html#X78DE1F2C80B0D55C"><span class="RefLink">8.2-14</span></a>) to access the key and value of the node respectively. The function returns <code class="keyw">fail</code> if the key is not found in the tree. This function assumes that the keys in the tree are sorted according to the three-way comparison function stored with the tree.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLIndexFind</code>( <var class="Arg">t</var>, <var class="Arg">index</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an integer or <code class="keyw">fail</code></p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree. This function locates the index <var class="Arg">index</var> in the tree and returns the position in the positional object, at which the node which hash this index is stored. This position will always be divisible by 4. Use the functions <code class="func">AVLData</code> (<a href="chap8.html#X78B2EEB4804987F2"><span class="RefLink">8.2-13</span></a>) and <code class="func">AVLValue</code> (<a href="chap8.html#X78DE1F2C80B0D55C"><span class="RefLink">8.2-14</span></a>) to access the key and value of the node respectively. The function returns <code class="keyw">fail</code> if the key is not found in the tree. This function does not assume that the keys in the tree are sorted according to the three-way comparison function stored with the tree.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLData</code>( <var class="Arg">t</var>, <var class="Arg">pos</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: an key</p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree and the second a position in the positional object corresponding to a node as returned by <code class="func">AVLFind</code> (<a href="chap8.html#X7EF737C286E94F23"><span class="RefLink">8.2-11</span></a>). The function returns the key associated with this node.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AVLValue</code>( <var class="Arg">t</var>, <var class="Arg">pos</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a value</p>
<p>The first argument <var class="Arg">t</var> must be an AVL tree and the second a position in the positional object corresponding to a node as returned by <code class="func">AVLFind</code> (<a href="chap8.html#X7EF737C286E94F23"><span class="RefLink">8.2-11</span></a>). The function returns the value associated with this node.</p>
<p>The following convenience methods for standard list methods are implemented for AVL tree objects:</p>
<p>This method allows for easy access to the key at index <var class="Arg">index</var> in the tree using the square bracket notation <code class="code"><var class="Arg">t</var>[<var class="Arg">index</var>]</code>. It does exactly the same as <code class="func">AVLIndex</code> (<a href="chap8.html#X810E5CDF7ED14BF8"><span class="RefLink">8.2-7</span></a>). This is to make AVL trees behave more like lists.</p>
<p>This method allows to use the <code class="code">Position</code> operation to locate the index at which the key <var class="Arg">key</var> is stored in the tree. It does exactly the same as <code class="func">AVLFindIndex</code> (<a href="chap8.html#X7D1B85DA814DA26C"><span class="RefLink">8.2-6</span></a>). This is to make AVL trees behave more like lists.</p>
<p>This method allows to use the <code class="code">Add</code> operation to add a key (with associated value <code class="keyw">true</code>) to the tree at index <var class="Arg">index</var>. It does exactly the same as <code class="func">AVLIndexAdd</code> (<a href="chap8.html#X817B8377799DE5E1"><span class="RefLink">8.2-9</span></a>), so the same warning about sortedness as there applies! If <var class="Arg">index</var> is omitted, the key is added at the end. This is to make AVL trees behave more like lists.</p>
<p>This method allows to use the <code class="code">Remove</code> operation to remove a key from the tree at index <var class="Arg">index</var>. If <var class="Arg">index</var> is omitted, the last key in the tree is remove. This method returns the deleted key or <code class="keyw">fail</code> if the tree was empty. This is to make AVL trees behave more like lists.</p>
<p>This method tests whether or not the key <var class="Arg">key</var> is stored in the AVL tree <var class="Arg">t</var>. This is to make AVL trees behave more like lists.</p>
<h4>8.3 <span class="Heading">The internal data structures</span></h4>
<p>An AVL tree is a positional object in which the first 7 positions are used for administrative data (see table below) and then from position 8 on follow the nodes of the tree. Each node uses 4 positions such that all nodes begin at positions divisible by 4. The system allocates the positional object larger than actually needed such that not every new node leads to the object being copied. Nodes which become free are collected in a free list. The following table contains the information what is stored in each of the first 7 entries:</p>
<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdleft">1</td>
<td class="tdleft">last actually used position, is always congruent 3 mod 4</td>
</tr>
<tr>
<td class="tdleft">2</td>
<td class="tdleft">position of first node in free list</td>
</tr>
<tr>
<td class="tdleft">3</td>
<td class="tdleft">number of currently used nodes in the tree</td>
</tr>
<tr>
<td class="tdleft">4</td>
<td class="tdleft">position of largest allocated position is always congruent 3 mod 4</td>
</tr>
<tr>
<td class="tdleft">5</td>
<td class="tdleft">three-way comparison function</td>
</tr>
<tr>
<td class="tdleft">6</td>
<td class="tdleft">position of the top node</td>
</tr>
<tr>
<td class="tdleft">7</td>
<td class="tdleft">a plain list holding the values stored under the keys</td>
</tr>
</table><br />
</div>
<p>The four positions used for a node contain the following information, recall that each node starts at a position divisible by 4:</p>
<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdleft">0 mod 4</td>
<td class="tdleft">reference to the key</td>
</tr>
<tr>
<td class="tdleft">1 mod 4</td>
<td class="tdleft">position of left node or 0 if empty, balance factor (see below)</td>
</tr>
<tr>
<td class="tdleft">2 mod 4</td>
<td class="tdleft">position of right node or 0 if empty</td>
</tr>
<tr>
<td class="tdleft">3 mod 4</td>
<td class="tdleft">index: number of nodes in left subtree plus one</td>
</tr>
</table><br />
</div>
<p>Since all positions of nodes are divisible by 4, we can use the least significant two bits of the left node reference for the so called balance factor. Balance factor 0 (both bits 0) indicates that the depth of the left subtree is equal to the depth of the right subtree. Balance factor 1 (bits 01) indicates that the depth of the right subtree is one greater than the depth of the left subtree. Balance factor 2 (or -1 in <a href="chapBib.html#biBACP3">[Knu97]</a>, here bits 10) indicates that the depth of the left subtree is one greater than the depth of the right subtree.</p>
<p>For freed nodes the position of the next free node in the free list is held in the 0 mod 4 position and 0 means the end of the free list.</p>
<p>Position 7 in the positional object can contain the value <code class="keyw">fail</code>, in this case all stored values are <code class="keyw">true</code>. This is a measure to limit the memory usage in the case that the only relevant information in the tree is the key and no values are stored there. This is in particular interesting if the tree structure is just used as a list implementation.</p>
<p>Note that all functions dealing with AVL trees are both implemented on the <strong class="pkg">GAP</strong> level and on the kernel level. Both implementations do exactly the same thing, the kernel version is only much faster and tuned for efficiency whereas the <strong class="pkg">GAP</strong> version documents the functionality better and is used as a fallback if the C-part of the <strong class="pkg">orb</strong> is not compiled.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
