Extra Lab Solution

Binary Search Trees and Student Records

Possible Solution

Task 1
1
2
3
4
5
6
7
8
9
int compareByName(Record r1, Record r2) {
    int cmp1 = strcmp(RecordGetFamilyName(r1), RecordGetFamilyName(r2));
    if (cmp1 != 0) return cmp1;

    int cmp2 = strcmp(RecordGetGivenName(r1), RecordGetGivenName(r2));
    if (cmp2 != 0) return cmp2;

    return RecordGetZid(r1) - RecordGetZid(r2);
}
Task 2

Here is the simple but inefficient solution that was suggested in the lab:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
List TreeSearchBetween(Tree t, Record lower, Record upper) {
    List l = ListNew();
    doTreeSearchBetween(t, t->root, lower, upper, l);
    return l;
}

static void doTreeSearchBetween(Tree t, Node n, Record lower,
                                Record upper, List l) {
    if (n == NULL) {
        return;
    }

    doTreeSearchBetween(t, n->left, lower, upper, l);
    if (t->compare(n->rec, lower) >= 0 && t->compare(n->rec, upper) <= 0) {
        ListAppend(l, n->rec);
    }
    doTreeSearchBetween(t, n->right, lower, upper, l);
}

Here is an efficient solution:

 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
List TreeSearchBetween(Tree t, Record lower, Record upper) {
    List l = ListNew();
    doTreeSearchBetween(t, t->root, lower, upper, l);
    return l;
}

static void doTreeSearchBetween(Tree t, Node n, Record lower,
                                Record upper, List l) {
    if (n == NULL) {
        return;
    }

    int cmp1 = t->compare(n->rec, lower);
    int cmp2 = t->compare(n->rec, upper);

    if (cmp1 > 0) {
        doTreeSearchBetween(t, n->left, lower, upper, l);
    }
    if (cmp1 >= 0 && cmp2 <= 0) {
        ListAppend(l, n->rec);
    }
    if (cmp2 < 0) {
        doTreeSearchBetween(t, n->right, lower, upper, l);
    }
}

Here is another solution that works (but is slightly less efficient):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
List TreeSearchBetween(Tree t, Record lower, Record upper) {
    List l = ListNew();
    doTreeSearchBetween(t, t->root, lower, upper, l);
    return l;
}

static void doTreeSearchBetween(Tree t, Node n, Record lower,
                                Record upper, List l) {
    if (n == NULL) {
        return;
    }

    if (t->compare(n->rec, lower) < 0) {
        doTreeSearchBetween(t, n->right, lower, upper, l);
    } else if (t->compare(n->rec, upper) > 0) {
        doTreeSearchBetween(t, n->left, lower, upper, l);
    } else {
        doTreeSearchBetween(t, n->left, lower, upper, l);
        ListAppend(l, n->rec);
        doTreeSearchBetween(t, n->right, lower, upper, l);
    }
}

The above solution can be improved to visit fewer nodes by considering equality.

Task 3
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
List DbFindByName(StudentDb db, char *familyName, char *givenName) {
    // two dummy records
    Record lower = RecordNew(MIN_ZID, familyName, givenName);
    Record upper = RecordNew(MAX_ZID, familyName, givenName);
    
    List l = TreeSearchBetween(db->byName, lower, upper);
    RecordFree(lower);
    RecordFree(upper);
    return l;
}

void DbListByName(StudentDb db) {
    TreeListInOrder(db->byName);
}