Lab #2: Inductive Definitions, Persistent Data Structures and Recursion

Introduction

In this lab, we'll study inductive definitions and persistent data structures. The primary purpose of this lab is to familarize you

how to write inductive definitions for data types,
how to transform these inductive definitions to persistent data structures,
how to write algorithms on these data structures, and
how to argue the correctness of your algorithms.

To be specific, we'll study four inductive definitions: natural numbers, linked list, binary search tree and red-black tree.

For natural numbers and linked list, we've offered you the code, and your job is to read the code carefully and make sure you fully understand every line, and then be able to answer the questions.

For binary search tree, you should write your code from scratch, based on the interface we offered you.

The last problem red-black tree is optional.

1. Natural Numbers

Read the natural numbers we offered you, and answer the questions in the code.

2. Persistent Linked List

Read the linked list we offered you, and answer the questions below.
Question #1: Skim file linkedList.c, is there any loop statement, such as while or for? Then how the work is done? Take the function


linkedListInsert

at line 68 to explain your concusion.
Question #2: File linkedList.c, line 86, the function linkedListInsertHead call function linkedListInsert to accomplish the work. Modify the function linkedListInsert so as not to call other functions, except for itself (recursion).
Question #3: File main.c, line 20. Can we change this line from

m = linkedListInsertTail (m, natFromInt (i));

to the following one?

linkedListInsertTail (m, natFromInt (i));

Why or why not?
Question #4: Rethink the monoList and polyList in Lab #1, what's the difference between them and the funList in this problem?

3. Binary Search Tree

Read the binary search tree we offered you. Your job is to finish the file bst.c, by substituting every TODO statement with your code. Make sure to test your implementation when finished.

4. (Optional) Red-black Tree

A variant of the binary search tree is the red-black tree, in which every node is accompanied with a color: red or black. For detailed properties on red-black tree, you may want to consult an algorithm textbook (such as the Introduction to Algorithms). And you may want to make use of this data structure:

typedef struct rbtStruct *rbt;
struct rbtStruct
{
  enum rbtKind {EMPTY, RED, BLACK} kind;
  union 
  {
    struct 
    {
      poly data;
      rbt left;
      rbt right;
    } node;
  } u;
};