1 /* $NetBSD: avl.c,v 1.1.1.1 1997/09/26 17:54:09 phil Exp $ */ 2 3 /* 4 * Copyright (c) 1997 Philip A. Nelson. 5 * All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by Philip A. Nelson. 18 * 4. The name of Philip A. Nelson may not be used to endorse or promote 19 * products derived from this software without specific prior written 20 * permission. 21 * 22 * THIS SOFTWARE IS PROVIDED BY PHILIP NELSON ``AS IS'' AND ANY EXPRESS OR 23 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 25 * IN NO EVENT SHALL PHILIP NELSON BE LIABLE FOR ANY DIRECT, INDIRECT, 26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 27 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 31 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 */ 33 34 /* avl.c: Routines for manipulation an avl tree. 35 * 36 * an include file should define the following minimum struct.: 37 * (Comments must be made into real comments.) 38 * 39 * typedef struct id_rec { 40 * / * The balanced binary tree fields. * / 41 * char *id; / * The name. * / 42 * short balance; / * For the balanced tree. * / 43 * struct id_rec *left, *right; / * Tree pointers. * / 44 * 45 * / * Other information fields. * / 46 * } id_rec; 47 */ 48 49 #include "defs.h" 50 51 /* find_id returns a pointer to node in TREE that has the correct 52 ID. If there is no node in TREE with ID, NULL is returned. */ 53 54 id_rec * 55 find_id (id_rec *tree, char *id) 56 { 57 int cmp_result; 58 59 /* Check for an empty tree. */ 60 if (tree == NULL) 61 return NULL; 62 63 /* Recursively search the tree. */ 64 cmp_result = strcmp (id, tree->id); 65 if (cmp_result == 0) 66 return tree; /* This is the item. */ 67 else if (cmp_result < 0) 68 return find_id (tree->left, id); 69 else 70 return find_id (tree->right, id); 71 } 72 73 74 /* insert_id inserts a NEW_ID rec into the tree whose ROOT is 75 provided. insert_id returns TRUE if the tree height from 76 ROOT down is increased otherwise it returns FALSE. This is a 77 recursive balanced binary tree insertion algorithm. */ 78 79 int insert_id (id_rec **root, id_rec *new_id) 80 { 81 id_rec *A, *B; 82 83 /* If root is NULL, this where it is to be inserted. */ 84 if (*root == NULL) 85 { 86 *root = new_id; 87 new_id->left = NULL; 88 new_id->right = NULL; 89 new_id->balance = 0; 90 return (TRUE); 91 } 92 93 /* We need to search for a leaf. */ 94 if (strcmp (new_id->id, (*root)->id) < 0) 95 { 96 /* Insert it on the left. */ 97 if (insert_id (&((*root)->left), new_id)) 98 { 99 /* The height increased. */ 100 (*root)->balance --; 101 102 switch ((*root)->balance) 103 { 104 case 0: /* no height increase. */ 105 return (FALSE); 106 case -1: /* height increase. */ 107 return (FALSE); 108 case -2: /* we need to do a rebalancing act. */ 109 A = *root; 110 B = (*root)->left; 111 if (B->balance <= 0) 112 { 113 /* Single Rotate. */ 114 A->left = B->right; 115 B->right = A; 116 *root = B; 117 A->balance = 0; 118 B->balance = 0; 119 } 120 else 121 { 122 /* Double Rotate. */ 123 *root = B->right; 124 B->right = (*root)->left; 125 A->left = (*root)->right; 126 (*root)->left = B; 127 (*root)->right = A; 128 switch ((*root)->balance) 129 { 130 case -1: 131 A->balance = 1; 132 B->balance = 0; 133 break; 134 case 0: 135 A->balance = 0; 136 B->balance = 0; 137 break; 138 case 1: 139 A->balance = 0; 140 B->balance = -1; 141 break; 142 } 143 (*root)->balance = 0; 144 } 145 } 146 } 147 } 148 else 149 { 150 /* Insert it on the right. */ 151 if (insert_id (&((*root)->right), new_id)) 152 { 153 /* The height increased. */ 154 (*root)->balance ++; 155 switch ((*root)->balance) 156 { 157 case 0: /* no height increase. */ 158 return (FALSE); 159 case 1: /* height increase. */ 160 return (FALSE); 161 case 2: /* we need to do a rebalancing act. */ 162 A = *root; 163 B = (*root)->right; 164 if (B->balance >= 0) 165 { 166 /* Single Rotate. */ 167 A->right = B->left; 168 B->left = A; 169 *root = B; 170 A->balance = 0; 171 B->balance = 0; 172 } 173 else 174 { 175 /* Double Rotate. */ 176 *root = B->left; 177 B->left = (*root)->right; 178 A->right = (*root)->left; 179 (*root)->left = A; 180 (*root)->right = B; 181 switch ((*root)->balance) 182 { 183 case -1: 184 A->balance = 0; 185 B->balance = 1; 186 break; 187 case 0: 188 A->balance = 0; 189 B->balance = 0; 190 break; 191 case 1: 192 A->balance = -1; 193 B->balance = 0; 194 break; 195 } 196 (*root)->balance = 0; 197 } 198 } 199 } 200 } 201 202 /* If we fall through to here, the tree did not grow in height. */ 203 return (FALSE); 204 } 205