Tutorial Solutions

A Question of Balance

Explain how we could globally balance a binary search tree using the following partition function:

#define size(tree) (tree)->size

btree_node *btree_partition (btree_node *tree, size_t k)
{
	if (tree == NULL) return NULL;
	size_t lsize = size (tree->left);
	if (lsize > k) {
		tree->left = btree_partition (tree->left, k);
		tree = btree_rotate_right (tree);
	}
	if (lsize < k) {
		tree->right = btree_partition (tree->right, k - 1 - lsize);
		tree = btree_rotate_left (tree);
	}
	return tree;
}

Show the result of globally rebalancing this tree:

After the first call to partition:

After the second call to partition:

      4
     / \
    /   \
   /     \
  2       5
 / \       \
1   3       6
             \
              7

After the third and final call to partition:

      4
     / \
    /   \
   /     \
  2       6
 / \     / \
1   3   5   7

Insert items with the keys $[10, 9, 8, 7, 11]$ into a ‘normal’ binary search tree, into a binary search tree with root insertion, and into a splay tree. Draw the resulting trees. For each resulting tree, decide whether the tree is size balanced, height balanced, or unbalanced.

Into a binary search tree, we get this unbalanced tree:
      10
     /  \
    9    11
   /
  8
 /
7
Into a binary search tree with root insertion, we get this unbalanced tree:
  11
 /
7
 \
  8
   \
    9
     \
     10
Into a splay tree, we get this unbalanced tree:
    11
   /
  8
 / \
7   10
   /
  9

Explain the concept of ‘amortisation’ in the context of binary search trees and splay trees.

Insert the same keys into a randomised binary search tree; get someone to flip a coin each time a decision needs to be made as to whether the node is inserted at the leaf or root of the given subtree. Heads can mean root, tails can mean leaf. (Note: in the actual implementation from lectures, the probability that it is inserted at the root is approx $P(n)=1/n$ , not a half.)

Hashing and Hash Tables

Draw a hash table of size 13. Use the hash function $h(k)=k\%13$ , and insert the keys $[5,29,32,0,31,20,23,18]$ into your table (in that order) using the following strategies for handling collisions:

chaining
linear probing
double hashing, with a second hash function $h_2(k)=7-(k\%7)$ . (Why would a second hash function like $h_2(k)=k\%7$ not be very useful?)

chaining:

0 1 2 3 4 5 6 7 8 9 10 11 12

0 29 5 32 20 23

31

18

linear probing:

0 1 2 3 4 5 6 7 8 9 10 11 12

0 29 5 32 31 20 18 23

double-hashing:

0 1 2 3 4 5 6 7 8 9 10 11 12

0 29 5 32 20 18 31 23

A hash function like $h_2(k)=k\%7$ would produce values in the range 0…6. Values of 0 would not be very useful, as you would just checking an index 0 away – i.e., in the same spot the original collision was in.

For a hash table that uses chaining for collision resolution, with the chains sorted in ascending order on key value, what are the best case and worst case costs for inserting $k$ items into the table? Assume that the size of the table $N=k/2$ , and that the insertion cost is measured in terms of the number of key comparisons, and that the chains are sorted in key order. What will be average search cost after all the insertions are done?

The worst case occurs when the hash function returns a constant value, and the keys arrive in ascending order. In this case, there will be a single chain from the one entry in the hash table that is “hit” by the hash function. Each search of that chain will require us to go right to the end. The cost for the first insertion is 0, since we do no key comparisons, but discover that the chain is empty. On the second insertion, we do one key comparison; on the third insertion we do two key comparisons; and so on. This will give $0+1+2+\cdots+(k-1)$ comparisons, which is $(k-1)\times(k-2)/2$ total comparisons.

After insertion, each search requires a scan of the single chain of length $k$ , so the average search cost will be $k/2$ .

The best case occurs when we have a hash function that distributes the items uniformly across the table. In this case, we end up with a chain of length 2 (from $k/N$ ) attached to each hash table entry. In building these chains, the first entry requires no key comparisons (just a check for an empty chain). When adding the second item to each chain, only one comparison is needed, giving a total of $k/2$ comparisons.

After insertion, each search requires a scan of a chain of length 2 and, on average, half the chain will be checked. Thus, the average search cost will be 1.

Digest This!

Consider the following scheme for implementing a hash function by treating the characters in a string as bit patterns that form a long integer value.

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLESIZE 8191
#define U64SIZE (sizeof (uint64_t))

static uint64_t hash_short_string (char v[], int N);

int main(int argc, char *argv[])
{
	if (argc < 2) {
		printf ("Usage: %s <string>\n", argv[0]);
		printf ("(<string> truncated after %zu characters)\n", U64SIZE);
		return EXIT_FAILURE;
	}

	char key[U64SIZE] = {0};
	strncpy (key, argv[1], U64SIZE);
	printf ("Hash: %" PRIu64 "\n", hash_short_string (key, TABLESIZE));
	return EXIT_SUCCESS;
}

static uint64_t hash_short_string(char v[], int N)
{
	union IntStr {
		uint64_t ikey;
		uint8_t  skey[U64SIZE];
	} *is = (union IntStr *)v;

	return (is->ikey % N);
}

Discuss how the hash_short_string() function works. What is the difference between a struct and a union? How is the conversion achieved?

What happens if strings are provided whose length is smaller or larger than U64SIZE?

A struct defines an object containing multiple values, where each value can have a different type, is referenced by a field name, and has its own memory.

A union defines an object which refers to a single piece of memory that can be referenced by different names and be interpreted differently, depending on the type associated with the name.

Consider the following similar-looking definitions:
struct s { int x; float y; } obj1;
union  u { int x; float y; } obj2;
The struct definition gives an $$|\texttt{int}|+|\texttt{float}|=4+4=8$ byte object (called obj1) where the first 4 bytes store an integer value by the name x, and where the second 4 bytes store a floating-point value by the name y.

The union definition gives an $\max\{|\texttt{int}|,|\texttt{float}|\}=4$ byte object (called obj2) where those bytes can be referenced by two different names, and the bit pattern in those bytes will be interpreted as an int if the name x is used, and as a float if the name y is used.

The hash_short_string() function exploits this ability to reinterpret the contents of a piece of memory in different ways. We know that a single uint8_t value will occupy 8 bits, or one byte; an array of eight uint8_t values will occupy 8 bytes; and a uint64_t value occupies 64 bits, or 8 bytes.

If we cast a pointer to a string into this type, it allows us to view the first eight bytes via the array is->skey. If the same eight bytes are referenced via is->ikey, they will be interpreted as a single value of type uint64_t.

By taking the first eight characters of the string, and treating it as a 64-bit unsigned integer value, we can take a value and produce a hash of (roughly) the string’s contents.

When we “fit” it into the table size using the mod operator, since the table size is relatively small compared to the space of values for the large integer, most of the bits will not be included in the hash value. For small hash table sizes – less than 65,000 or so – only the first two bytes of the string will actually contribute to the hash value.

Also, any characters beyond the 8th character will be completely ignored, regardless of the hash table size.

More problematic is the question of what happens with short strings (less than 8 characters); the first few bytes have defined values, but the bytes after that are filled with zeroes, and the order of the bytes is such that the zero bytes contribute to the hash.

In summary, this is not a great way to do hashing.

(For more on unions, structs, endianness, and all sorts of other bit-reinterpretation evils, check out COMP1521.)

If there is any remaining time, use it to finish any questions you did not cover in previous weeks.