Initial working commit

There are still some errors when run through valgrind, but it performs
as expected for the test file.

1 files changed, 71 insertions, 59 deletions

diff --git a/strbst.c b/strbst.c
index 7bb53b1..b8b5dce 100644
--- a/strbst.c
+++ b/strbst.c
@@ -3,18 +3,21 @@
 #include <stdio.h>
 
 #include "strbst.h"
+/*
+strbst defines strbst with one member: strbstnode->head.
+strbstnode has left, right, data, ind, and ht for avl balancing
+*/
 #define max(a,b) ((a > b) ? a : b)
 #define min(a,b) ((a < b) ? a : b)
 
 typedef char height;
 
 strbst* newbst(void) {
-    strbst* out = malloc(sizeof(strbst));
-    out->head = NULL;
-    return out;
+    return calloc(sizeof(strbst),1);
 }
 
-static strbstnode* newbstnode(char* ind, void* data) { // does not ins
+static strbstnode* newbstnode(char* ind, void* data) {
+    // Doesn't insert, just allocates
     strbstnode* out = malloc(sizeof(strbstnode));
     out->ind = ind;
     out->data = data;
@@ -23,35 +26,69 @@ static strbstnode* newbstnode(char* ind, void* data) { // does not ins
     return out;
 }
 
-int getht(strbstnode* node) {
-    return node ? node->ht : -1;
+// A nonexistent node has height of -1 so that childless nodes are ht 0.
+#define getht(node) ( (node) ? node->ht : -1 )
+
+// The basic (and only) balancing operations for AVL: rotations
+// Take address of top node so that the real tree can change.
+static void rightrot(strbstnode** bst) {
+/*
+    a         b
+   / \       / \
+  b   e =>  c   a
+ / \           / \
+c   d         d   e
+*/
+    strbstnode* flip = (*bst)->left->right; // flip = d
+    (*bst)->left->right = *bst; // position of d = a
+    *bst = (*bst)->left; // tip = b
+    (*bst)->right->left = flip;
 }
 
-static void rightrot(strbstnode** bst);
-static void leftrot(strbstnode** bst);
+static void leftrot(strbstnode** bst) {
+/*
+  a            b
+ / \          / \
+e   b   =>   a   c
+   / \      / \
+  d   c    e   d
+*/
+    strbstnode* flip = (*bst)->right->left; // flip = d
+    (*bst)->right->left = *bst; // position of d = a
+    *bst = (*bst)->right; // tip = b
+    (*bst)->left->right = flip;
+}
 
-int insnode(strbstnode** bst, strbstnode* new) { // Find good parent
-    if (!*bst){
-        *bst = new;
-        return 0;
+int insnode(strbstnode** bst, strbstnode* new) {
+    // returns height of right node minus height of left node ("bias")
+    if (!*bst) { // When an empty node is reached,
+        *bst = new; // place the node
+        return 0; // no children, so height difference is zero
     }
     strbstnode** node;
-    if (strcmp(new->ind, (*bst)->ind) < 0)
+    if (strcmp(new->ind, (*bst)->ind) < 0) // bst < ind?
+        // the address of the new node has to be taken so that node's
+        // addr is not returned
         node = &((*bst)->left);
-    else
+    else // assumed that new's index is not contained in tree
         node = &((*bst)->right);
+    // node is the parent of the subtree which will contain new
     int heavy = insnode( node, new );
+        // insert it into the subtree and get its bias
     int diff = getht((*bst)->right) - getht((*bst)->left);
-    if (diff > 1) {
-        if (heavy == -1)
-            rightrot(node);
-        leftrot(bst);
-    } else if (diff < -1){
+    if (diff > 1) { // was originally valid (diff==1), so diff == 2
+        if (heavy == -1) // if node is left heavy,
+            rightrot(node); // make it right heavy. ht shouldn't change.
+        leftrot(bst); // fixes, since heavy side is either right heavy
+                      // or centered
+    } else if (diff < -1){ // diff == -2
         if (heavy == 1)
-            leftrot(node);
-        rightrot(bst);
+            leftrot(node); // make left heavy
+        rightrot(bst); // fix
     }
+    // Calculate the current node's height
     (*bst)->ht = max( getht((*bst)->left), getht((*bst)->right) )+1;
+    // And return calculated bias
     return ( getht((*bst)->right) - getht((*bst)->left) );
 }
 
@@ -60,55 +97,30 @@ void insbst(strbst* bst, char* ind, void* data) {
 }
 
 void* querynode(strbstnode* node, char* ind){
+    // tail-recursive finding algorithm
+    if (!node) return NULL; // NULL => node not found
     int cmp = strcmp(ind, node->ind);
-    if (cmp > 0)
+    if (cmp > 0) // ind > node->ind
         return querynode(node->right, ind);
-    else if (cmp < 0)
+    else if (cmp < 0) // ind < node->ind
         return querynode(node->left, ind);
-    else if (node)
-        return node->data;
     else
-        return NULL;
+        return node->data; // void* data is passed back up the chain
 }
 
-void* querybst(strbst* bst, char* ind) {
+void* query(strbst* bst, char* ind) {
     return querynode(bst->head, ind);
 }
 
-void rightrot(strbstnode** bst) {
-/*
-    a         b
-   / \       / \
-  b   e =>  c   a
- / \           / \
-c   d         d   e
-*/
-    strbstnode* flip = (*bst)->left->right; // flip = d
-    (*bst)->left->right = *bst; // position of d = a
-    *bst = (*bst)->left; // tip = b
-    (*bst)->right->left = flip;
-}
-
-void leftrot(strbstnode** bst) {
-/*
-  a            b
- / \          / \
-e   b   =>   a   c
-   / \      / \
-  d   c    e   d
-*/
-    strbstnode* flip = (*bst)->right->left; // flip = d
-    (*bst)->right->left = *bst; // position of d = a
-    *bst = (*bst)->right; // tip = b
-    (*bst)->left->right = flip;
-}
-
-void printnode(strbstnode* node) {
+static void printbstnode(strbstnode* node) {
     if (!node) return;
+    // Recursive printing
     if (node->right)
-        printnode(node->right);
+        printbstnode(node->right);
     if (node->left)
-        printnode(node->left);
+        printbstnode(node->left);
+    // Print one line.
+    // With all components, "node %s (right) %s (left) %s\n"
     printf("node %s", node->ind);
     if (node->right)
         printf(" (right) %s",node->right->ind);
@@ -118,5 +130,5 @@ void printnode(strbstnode* node) {
 }
 
 void printbst(strbst* bst) {
-    printnode(bst->head);
+    printbstnode(bst->head);
 }