Page 181 - ARM 64 Bit Assembly Language

168 Chapter 6

Figure 6.1: Binary tree of word frequencies.

storing word frequency counts. The time required to insert into a linked list is O(N),but the
time required to insert into a binary tree is O(log N). To give some perspective, the author’s
2
manuscript for this textbook contains about 125,000 words. Since log (125,000)< 17, we
2
would expect the linked list implementation to require about 125000 ≈ 7353 times as long as
17
a binary tree implementation to process the author’s manuscript for this textbook. In reality,
there is some overhead to the binary tree implementation. Even with the extra overhead, we
should see a significant speedup. Listing 6.10 shows the C implementation using a balanced
binary tree instead of a linked list.

Listing 6.10 C implementation of the wordlist ADT using a tree.

1 #include <stdlib.h>
2 #include <string.h>
3 #include <stdio.h>
4 #include <list.h>
5
6 #define MAX(x,y) (x<y?y:x)
7