1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
#include <stdlib.h>
#include <string.h>
#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
*/
int max(int a, int b) {
return ( (a < b) ? a : b);
}
typedef char height;
strbst* newbst(void) {
return calloc(1,sizeof(strbst));
}
static strbstnode* newbstnode(char* ind, void* data) {
// Doesn't insert, just allocates
strbstnode* out = malloc(sizeof(strbstnode));
out->ind = ind;
out->data = data;
out->left = out->right = NULL;
out->ht = 0;
return out;
}
// 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 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;
}
// NOTE: These functions are valid because `b` is guaranteed in the
// conditions where the rotations are called.
static 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) // bst < ind?
// the address of the new node has to be taken so that node's
// addr is not returned
node = &((*bst)->left);
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) { // 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); // 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) );
}
void insbst(strbst* bst, char* ind, void* data) {
insnode(&(bst->head), newbstnode(ind, data)); // allows recursion
}
static 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) // ind > node->ind
return querynode(node->right, ind);
else if (cmp < 0) // ind < node->ind
return querynode(node->left, ind);
else
return node->data; // void* data is passed back up the chain
}
void* query(strbst* bst, char* ind) {
return querynode(bst->head, ind);
}
static void printbstnode(strbstnode* node) {
if (!node) return;
// Recursive printing
if (node->right)
printbstnode(node->right);
if (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);
if (node->left)
printf(" (left) %s", node->left->ind);
printf("\n");
}
void printbst(strbst* bst) {
printbstnode(bst->head);
}
|
