[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Basic implementation of an AVL tree storing ints. This is not particularly optimized, and effectively implements a set data type with the ability to delete the minimum value as in a heap.

1. Header file

   1 /* implementation of an AVL tree with explicit heights */
   2 
   3 typedef struct avlNode *AvlTree;
   4 
   5 /* empty avl tree is just a null pointer */
   6 
   7 #define AVL_EMPTY (0)
   8 
   9 /* free a tree */
  10 void avlDestroy(AvlTree t);
  11 
  12 /* return the height of a tree */
  13 int avlGetHeight(AvlTree t);
  14 
  15 /* return nonzero if key is present in tree */
  16 int avlSearch(AvlTree t, int key);
  17 
  18 /* insert a new element into a tree */
  19 /* note *t is actual tree */
  20 void avlInsert(AvlTree *t, int key);
  21 
  22 /* run sanity checks on tree (for debugging) */
  23 /* assert will fail if heights are wrong */
  24 void avlSanityCheck(AvlTree t);
  25 
  26 /* print all keys of the tree in order */
  27 void avlPrintKeys(AvlTree t);
  28 
  29 /* delete and return minimum value in a tree */
  30 int avlDeleteMin(AvlTree *t);
avlTree.h

2. Implementation

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 
   5 #include "avlTree.h"
   6 
   7 /* implementation of an AVL tree with explicit heights */
   8 
   9 struct avlNode {
  10     struct avlNode *child[2];    /* left and right */
  11     int key;
  12     int height;
  13 };
  14 
  15 /* free a tree */
  16 void 
  17 avlDestroy(AvlTree t)
  18 {
  19     if(t != AVL_EMPTY) {
  20         avlDestroy(t->child[0]);
  21         avlDestroy(t->child[1]);
  22         free(t);
  23     }
  24 }
  25 
  26 /* return height of an AVL tree */
  27 int
  28 avlGetHeight(AvlTree t)
  29 {
  30     if(t != AVL_EMPTY) {
  31         return t->height;
  32     } else {
  33         return 0;
  34     }
  35 }
  36 
  37 /* return nonzero if key is present in tree */
  38 int
  39 avlSearch(AvlTree t, int key)
  40 {
  41     if(t == AVL_EMPTY) {
  42         return 0;
  43     } else if(t->key == key) {
  44         return 1;
  45     } else {
  46         return avlSearch(t->child[key > t->key], key);
  47     }
  48 }
  49 
  50 #define Max(x,y) ((x)>(y) ? (x) : (y))
  51 
  52 /* assert height fields are correct throughout tree */
  53 void
  54 avlSanityCheck(AvlTree root)
  55 {
  56     int i;
  57 
  58     if(root != AVL_EMPTY) {
  59         for(i = 0; i < 2; i++) {
  60             avlSanityCheck(root->child[i]);
  61         }
  62 
  63         assert(root->height == 1 + Max(avlGetHeight(root->child[0]), avlGetHeight(root->child[1])));
  64     }
  65 }
  66 
  67 /* recompute height of a node */
  68 static void
  69 avlFixHeight(AvlTree t)
  70 {
  71     assert(t != AVL_EMPTY);
  72 
  73     t->height = 1 + Max(avlGetHeight(t->child[0]), avlGetHeight(t->child[1]));
  74 }
  75 
  76 /* rotate child[d] to root */
  77 /* assumes child[d] exists */
  78 /* Picture:
  79  *
  80  *     y            x
  81  *    / \   <==>   / \
  82  *   x   C        A   y
  83  *  / \              / \
  84  * A   B            B   C
  85  *
  86  */
  87 static void
  88 avlRotate(AvlTree *root, int d)
  89 {
  90     AvlTree oldRoot;
  91     AvlTree newRoot;
  92     AvlTree oldMiddle;
  93 
  94     oldRoot = *root;
  95     newRoot = oldRoot->child[d];
  96     oldMiddle = newRoot->child[!d];
  97 
  98     oldRoot->child[d] = oldMiddle;
  99     newRoot->child[!d] = oldRoot;
 100     *root = newRoot;
 101 
 102     /* update heights */
 103     avlFixHeight((*root)->child[!d]);   /* old root */
 104     avlFixHeight(*root);                /* new root */
 105 }
 106 
 107 
 108 /* rebalance at node if necessary */
 109 /* also fixes height */
 110 static void
 111 avlRebalance(AvlTree *t)
 112 {
 113     int d;
 114 
 115     if(*t != AVL_EMPTY) {
 116         for(d = 0; d < 2; d++) {
 117             /* maybe child[d] is now too tall */
 118             if(avlGetHeight((*t)->child[d]) > avlGetHeight((*t)->child[!d]) + 1) {
 119                 /* imbalanced! */
 120                 /* how to fix it? */
 121                 /* need to look for taller grandchild of child[d] */
 122                 if(avlGetHeight((*t)->child[d]->child[d]) > avlGetHeight((*t)->child[d]->child[!d])) {
 123                     /* same direction grandchild wins, do single rotation */
 124                     avlRotate(t, d);
 125                 } else {
 126                     /* opposite direction grandchild moves up, do double rotation */
 127                     avlRotate(&(*t)->child[d], !d);
 128                     avlRotate(t, d);
 129                 }
 130 
 131                 return;   /* avlRotate called avlFixHeight */
 132             }
 133         }
 134                   
 135         /* update height */
 136         avlFixHeight(*t);
 137     }
 138 }
 139 
 140 /* insert into tree */
 141 /* this may replace root, which is why we pass
 142  * in a AvlTree * */
 143 void
 144 avlInsert(AvlTree *t, int key)
 145 {
 146     /* insertion procedure */
 147     if(*t == AVL_EMPTY) {
 148         /* new t */
 149         *t = malloc(sizeof(struct avlNode));
 150         assert(*t);
 151 
 152         (*t)->child[0] = AVL_EMPTY;
 153         (*t)->child[1] = AVL_EMPTY;
 154 
 155         (*t)->key = key;
 156 
 157         (*t)->height = 1;
 158 
 159         /* done */
 160         return;
 161     } else if(key == (*t)->key) {
 162         /* nothing to do */
 163         return;
 164     } else {
 165         /* do the insert in subtree */
 166         avlInsert(&(*t)->child[key > (*t)->key], key);
 167 
 168         avlRebalance(t);
 169 
 170         return;
 171     }
 172 }
 173 
 174 
 175 /* print all elements of the tree in order */
 176 void
 177 avlPrintKeys(AvlTree t)
 178 {
 179     if(t != AVL_EMPTY) {
 180         avlPrintKeys(t->child[0]);
 181         printf("%d\n", t->key);
 182         avlPrintKeys(t->child[1]);
 183     }
 184 }
 185 
 186 
 187 /* delete and return minimum value in a tree */
 188 int
 189 avlDeleteMin(AvlTree *t)
 190 {
 191     AvlTree oldroot;
 192     int minValue;
 193 
 194     assert(t != AVL_EMPTY);
 195 
 196     if((*t)->child[0] == AVL_EMPTY) {
 197         /* root is min value */
 198         oldroot = *t;
 199         minValue = oldroot->key;
 200         *t = oldroot->child[1];
 201         free(oldroot);
 202     } else {
 203         /* min value is in left subtree */
 204         minValue = avlDeleteMin(&(*t)->child[0]);
 205     }
 206 
 207     avlRebalance(t);
 208     return minValue;
 209 }
 210 
 211 /* delete the given value */
 212 void
 213 avlDelete(AvlTree *t, int key)
 214 {
 215     AvlTree oldroot;
 216 
 217     if(*t != AVL_EMPTY) {
 218         return;
 219     } else if((*t)->key == key) {
 220         /* do we have a right child? */
 221         if((*t)->child[1] != AVL_EMPTY) {
 222             /* give root min value in right subtree */
 223             (*t)->key = avlDeleteMin(&(*t)->child[1]);
 224         } else {
 225             /* splice out root */
 226             oldroot = (*t);
 227             *t = (*t)->child[0];
 228             free(oldroot);
 229         }
 230     } else {
 231         avlDelete(&(*t)->child[key > (*t)->key], key);
 232     }
 233 
 234     /* rebalance */
 235     avlRebalance(t);
 236 }
avlTree.c

3. Test code and Makefile

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4 
   5 #include "avlTree.h"
   6 
   7 #define N (1024)
   8 #define MULTIPLIER (97)
   9 
  10 int
  11 main(int argc, char **argv)
  12 {
  13     AvlTree t = AVL_EMPTY;
  14     int i;
  15 
  16     if(argc != 1) {
  17         fprintf(stderr, "Usage: %s\n", argv[0]);
  18         return 1;
  19     }
  20 
  21     for(i = 0; i < N; i++) {
  22         avlInsert(&t, (i*MULTIPLIER) % N);
  23     }
  24 
  25     printf("height %d\n", avlGetHeight(t));
  26 
  27     assert(avlSearch(t, N-1) == 1);
  28     assert(avlSearch(t, N) == 0);
  29 
  30     avlSanityCheck(t);
  31 
  32     for(i = 0; i < N-1; i++) {
  33         avlDeleteMin(&t);
  34     }
  35 
  36     avlSanityCheck(t);
  37 
  38     avlPrintKeys(t);
  39 
  40     avlDestroy(t);
  41 
  42     return 0;
  43 }
test_avlTree.c

Makefile


CategoryProgrammingNotes


2014-06-17 11:57