Data Structures and Algorithms, Part II
In this tutorial we introduce more complex data structures (containers) and algorithms which operate on these containers. This tutorial is based on the former data structure tutorial.
Linear Container (doubly linked list)
Create a new data type containing a doubly linked list of 
. Then write the following functions to provide some basic functionality to the container:
- L1: An initialization for a given range of the container with default values.
- L1: A function to edit a single entry of the container at a certain position.
- L1: A function to delete an entry. A deletion of an entry can be modeled by, e.g. setting the string to an empty string.
- L2: A function to sort the entries of the container.
- L2: A function to search for a string. This function should return the position within the container.
- L2: A modified search method which does not require a linear search (which means, that all entries have to be searched).
Associative Container (Tree)
Create a tree data structure, where the entries (nodes) contain a 
and a 
. An example implementation can use an integer for the key and a user defined data type for the value, e.g., three-dimensional point. Create a container based on this tree. Write the following functions to enhance the functionality of the container:
- L1: A function which calculates the key based on the value , e.g. the sum of the digits of the coordinates modulo 100.
- L1: A function to search for a key. This function should return the entry.
- L1: A function to insert an entry. The tree should take care of the correct inseration at a position based on a compare, e.g.,
mechanism. - L1: A function to delete an entry.
- L3: A function to rebalance the tree if elements were inserted or deleted.