?? avltree_8h.html
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"><title>C Algorithms: avltree.h File Reference</title><link href="doxygen.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.4.4 --><div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="annotated.html">Data Structures</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="functions.html">Data Fields</a> | <a class="qindex" href="globals.html">Globals</a></div><h1>avltree.h File Reference</h1>Balanced binary tree. <a href="#_details">More...</a><p><table border="0" cellpadding="0" cellspacing="0"><tr><td></td></tr><tr><td colspan="2"><br><h2>Typedefs</h2></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">typedef _AVLTree </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a0">AVLTree</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">An AVL tree balanced binary tree. <a href="#a0"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">typedef _AVLTreeNode </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a1">AVLTreeNode</a></td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">A node in an AVL tree. <a href="#a1"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">typedef int(* </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a2">AVLTreeCompareFunc</a> )(void *data1, void *data2)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Type of function used to compare keys in an AVL tree. <a href="#a2"></a><br></td></tr><tr><td colspan="2"><br><h2>Functions</h2></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="avltree_8h.html#a0">AVLTree</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a3">avltree_new</a> (<a class="el" href="avltree_8h.html#a2">AVLTreeCompareFunc</a> compare_func)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Create a new AVL tree. <a href="#a3"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a4">avltree_free</a> (<a class="el" href="avltree_8h.html#a0">AVLTree</a> *tree)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Destroy an AVL tree. <a href="#a4"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a5">avltree_insert</a> (<a class="el" href="avltree_8h.html#a0">AVLTree</a> *tree, void *key, void *value)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Insert a new key-value pair into an AVL tree. <a href="#a5"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a6">avltree_remove_node</a> (<a class="el" href="avltree_8h.html#a0">AVLTree</a> *tree, <a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> *node)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Remove a node from a tree. <a href="#a6"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a7">avltree_remove</a> (<a class="el" href="avltree_8h.html#a0">AVLTree</a> *tree, void *key)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Remove an entry from a tree, specifying the key of the node to remove. <a href="#a7"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a8">avltree_lookup_node</a> (<a class="el" href="avltree_8h.html#a0">AVLTree</a> *tree, void *key)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Search an AVL tree for a node with a particular key. <a href="#a8"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">void * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a9">avltree_lookup</a> (<a class="el" href="avltree_8h.html#a0">AVLTree</a> *tree, void *key)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Search an AVL tree for a value corresponding to a particular key. <a href="#a9"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a10">avltree_root_node</a> (<a class="el" href="avltree_8h.html#a0">AVLTree</a> *tree)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Find the root node of a tree. <a href="#a10"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">void * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a11">avltree_node_key</a> (<a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> *node)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Retrieve the key for a given tree node. <a href="#a11"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">void * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a12">avltree_node_value</a> (<a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> *node)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Retrieve the value at a given tree node. <a href="#a12"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a13">avltree_node_left_child</a> (<a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> *node)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Find the left child of a given tree node. <a href="#a13"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a14">avltree_node_right_child</a> (<a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> *node)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Find the right child of a given tree node. <a href="#a14"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top"><a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a15">avltree_node_parent</a> (<a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> *node)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Find the parent node of a given tree node. <a href="#a15"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a16">avltree_subtree_height</a> (<a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> *node)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Find the height of a subtree. <a href="#a16"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">void ** </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a17">avltree_to_array</a> (<a class="el" href="avltree_8h.html#a0">AVLTree</a> *tree)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Convert the keys in an AVL tree into a C array. <a href="#a17"></a><br></td></tr><tr><td class="memItemLeft" nowrap align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="avltree_8h.html#a18">avltree_num_entries</a> (<a class="el" href="avltree_8h.html#a0">AVLTree</a> *tree)</td></tr><tr><td class="mdescLeft"> </td><td class="mdescRight">Retrieve the number of entries in the tree. <a href="#a18"></a><br></td></tr></table><hr><a name="_details"></a><h2>Detailed Description</h2>Balanced binary tree. <p>The AVL tree structure is a balanced binary tree which stores a collection of nodes (see <a class="el" href="avltree_8h.html#a1">AVLTreeNode</a>). Each node has a key and a value associated with it. The nodes are sorted within the tree based on the order of their keys. Modifications to the tree are constructed such that the tree remains balanced at all times (there are always roughly equal numbers of nodes on either side of the tree).<p>Balanced binary trees have several uses. They can be used as a mapping (searching for a value based on its key), or as a set of keys which is always ordered.<p>To create a new AVL tree, use <a class="el" href="avltree_8h.html#a3">avltree_new</a>. To destroy an AVL tree, use <a class="el" href="avltree_8h.html#a4">avltree_free</a>.<p>To insert a new key-value pair into an AVL tree, use <a class="el" href="avltree_8h.html#a5">avltree_insert</a>. To remove an entry from an AVL tree, use <a class="el" href="avltree_8h.html#a7">avltree_remove</a> or <a class="el" href="avltree_8h.html#a6">avltree_remove_node</a>.<p>To search an AVL tree, use <a class="el" href="avltree_8h.html#a9">avltree_lookup</a> or <a class="el" href="avltree_8h.html#a8">avltree_lookup_node</a>.<p>Tree nodes can be queried using the <a class="el" href="avltree_8h.html#a13">avltree_node_left_child</a>, <a class="el" href="avltree_8h.html#a14">avltree_node_right_child</a>, <a class="el" href="avltree_8h.html#a15">avltree_node_parent</a>, <a class="el" href="avltree_8h.html#a11">avltree_node_key</a> and <a class="el" href="avltree_8h.html#a12">avltree_node_value</a> functions.<hr><h2>Typedef Documentation</h2><a class="anchor" name="a0"></a><!-- doxytag: member="avltree.h::AVLTree" ref="a0" args="" --><p><table class="mdTable" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top">typedef struct _AVLTree <a class="el" href="avltree_8h.html#a0">AVLTree</a> </td> </tr> </table> </td> </tr></table><table cellspacing="5" cellpadding="0" border="0"> <tr> <td> </td> <td><p>An AVL tree balanced binary tree. <p><dl compact><dt><b>See also:</b></dt><dd><a class="el" href="avltree_8h.html#a3">avltree_new</a></dd></dl> </td> </tr></table><a class="anchor" name="a2"></a><!-- doxytag: member="avltree.h::AVLTreeCompareFunc" ref="a2" args=")(void *data1, void *data2)" --><p><table class="mdTable" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top">typedef int(* <a class="el" href="avltree_8h.html#a2">AVLTreeCompareFunc</a>)(void *data1, void *data2) </td> </tr> </table> </td> </tr></table><table cellspacing="5" cellpadding="0" border="0"> <tr> <td> </td> <td><p>Type of function used to compare keys in an AVL tree. <p><dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign="top"></td><td valign="top"><em>data1</em> </td><td>The first key. </td></tr> <tr><td valign="top"></td><td valign="top"><em>data2</em> </td><td>The second key. </td></tr> </table></dl><dl compact><dt><b>Returns:</b></dt><dd>A negative number if data1 should be sorted before data2, a positive number if data2 should be sorted before data1, zero if the two keys are equal.</dd></dl> </td> </tr></table><a class="anchor" name="a1"></a><!-- doxytag: member="avltree.h::AVLTreeNode" ref="a1" args="" --><p><table class="mdTable" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top">typedef struct _AVLTreeNode <a class="el" href="avltree_8h.html#a1">AVLTreeNode</a> </td> </tr> </table> </td> </tr></table><table cellspacing="5" cellpadding="0" border="0"> <tr> <td> </td> <td><p>A node in an AVL tree. <p><dl compact><dt><b>See also:</b></dt><dd><a class="el" href="avltree_8h.html#a13">avltree_node_left_child</a> <p><a class="el" href="avltree_8h.html#a14">avltree_node_right_child</a> <p><a class="el" href="avltree_8h.html#a15">avltree_node_parent</a> <p><a class="el" href="avltree_8h.html#a11">avltree_node_key</a> <p><a class="el" href="avltree_8h.html#a12">avltree_node_value</a></dd></dl> </td> </tr></table><hr><h2>Function Documentation</h2><a class="anchor" name="a4"></a><!-- doxytag: member="avltree.h::avltree_free" ref="a4" args="(AVLTree *tree)" --><p><table class="mdTable" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top">void avltree_free </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top"><a class="el" href="avltree_8h.html#a0">AVLTree</a> * </td> <td class="mdname1" valign="top" nowrap> <em>tree</em> </td> <td class="md" valign="top"> ) </td> <td class="md" nowrap></td> </tr> </table> </td> </tr></table><table cellspacing="5" cellpadding="0" border="0"> <tr> <td> </td> <td><p>Destroy an AVL tree. <p><dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign="top"></td><td valign="top"><em>tree</em> </td><td>The tree to destroy.</td></tr> </table></dl> </td> </tr></table><a class="anchor" name="a5"></a><!-- doxytag: member="avltree.h::avltree_insert" ref="a5" args="(AVLTree *tree, void *key, void *value)" --><p><table class="mdTable" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top"><a class="el" href="avltree_8h.html#a1">AVLTreeNode</a>* avltree_insert </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top"><a class="el" href="avltree_8h.html#a0">AVLTree</a> * </td> <td class="mdname" nowrap> <em>tree</em>, </td> </tr> <tr> <td class="md" nowrap align="right"></td> <td class="md"></td> <td class="md" nowrap>void * </td> <td class="mdname" nowrap> <em>key</em>, </td> </tr> <tr> <td class="md" nowrap align="right"></td> <td class="md"></td> <td class="md" nowrap>void * </td> <td class="mdname" nowrap> <em>value</em></td> </tr> <tr> <td class="md"></td> <td class="md">) </td> <td class="md" colspan="2"></td> </tr> </table> </td> </tr></table><table cellspacing="5" cellpadding="0" border="0"> <tr> <td> </td> <td><p>Insert a new key-value pair into an AVL tree. <p><dl compact><dt><b>Parameters:</b></dt><dd> <table border="0" cellspacing="2" cellpadding="0"> <tr><td valign="top"></td><td valign="top"><em>tree</em> </td><td>The tree. </td></tr> <tr><td valign="top"></td><td valign="top"><em>key</em> </td><td>The key to insert. </td></tr> <tr><td valign="top"></td><td valign="top"><em>value</em> </td><td>The value to insert. </td></tr> </table></dl><dl compact><dt><b>Returns:</b></dt><dd>The newly created tree node containing the key and value.</dd></dl> </td> </tr></table><a class="anchor" name="a9"></a><!-- doxytag: member="avltree.h::avltree_lookup" ref="a9" args="(AVLTree *tree, void *key)" --><p><table class="mdTable" cellpadding="2" cellspacing="0"> <tr> <td class="mdRow"> <table cellpadding="0" cellspacing="0" border="0"> <tr> <td class="md" nowrap valign="top">void* avltree_lookup </td> <td class="md" valign="top">( </td> <td class="md" nowrap valign="top"><a class="el" href="avltree_8h.html#a0">AVLTree</a> * </td> <td class="mdname" nowrap> <em>tree</em>, </td> </tr> <tr> <td class="md" nowrap align="right"></td>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -