Here's a complete program that uses a scapegoat tree to sort lines of text. The whole program is 85 lines. The basic scapegoat tree code including find(), insert() and rebalancing is 43 lines of code, 31 of which are not blank or just "}".
Fifty entries in the global minNodesForDepth table is good for over half a billion nodes in the tree. You might want to replace the init_table() function with a static array initializer.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node {char *key; node *left; node *right;};
int node_cnt;
#define BAL_OK 0
#define ALPHA 0.666667
#define TABSZ 50
int minNodesForDepth[TABSZ];
void init_table(){
double A = 1.0/ALPHA;
for (int n=0; n<TABSZ; ++n, A*=1.0/ALPHA){
minNodesForDepth[n] = A;
}
}
void printtree(node *root, int depth=0){
if (!root) return;
printtree(root->left, depth+1);
for (int i=0; i<depth; ++i) printf(" ");
printf("%s", root->key);
printtree(root->right, depth+1);
}
node *find(node *root, char *key){
int cmp = strcmp(key, root->key);
if (cmp == 0) return root;
return find(cmp<0 ? root->left : root->right, key);
}
node *makelinear(node *root, node *lst){
if (!root) return lst;
root->right = makelinear(root->right, lst);
node *left = root->left;
root->left = 0;
return makelinear(left, root);
}
node *maketree(node *&lst, int n){
if (n == 0) return 0;
node *left = maketree(lst, (n-1)/2);
node *root = lst; lst = lst->right;
root->left = left;
root->right = maketree(lst, n/2);
return root;
}
int cntSz(node *root){
return !root ? 0 : 1 + cntSz(root->left) + cntSz(root->right);
}
int insert(node *&root, node *n, int depth=0){
if (root == 0){
root = n;
return ++node_cnt < minNodesForDepth[depth] ? 1 : BAL_OK;
}
int cmp = strcmp(n->key, root->key);
int sz = insert(cmp<0 ? root->left : root->right, n, depth+1);
if (sz == BAL_OK) return sz;
int tot = sz + 1 + cntSz(cmp<0 ? root->right : root->left);
if (sz <= tot*ALPHA) return tot;
node *lst = makelinear(root, 0);
root = maketree(lst, tot);
return BAL_OK;
}
int main(){
char buf[1000];
init_table();
node *tree = 0;
while (fgets(buf, 1000, stdin)){
node *n = (node*)malloc(sizeof(node));
n->key = strdup(buf);
n->left = n->right = 0;
insert(tree, n);
}
printtree(tree);
return 0;
}
Home
Help
Search
Login
Register
