aboutsummaryrefslogtreecommitdiff
path: root/strbst.c
diff options
context:
space:
mode:
Diffstat (limited to 'strbst.c')
-rw-r--r--strbst.c130
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);
}