Data Structures and Basic Operations
We assume that we are interested in storing some subset of a large universe of possible values (say a subset of the integers between 1 and U) in the data structure, and we want to change or access this subset quickly. The table describes several possible operations on the data structure and the associated worst-case running times. We assume that when the operation starts, the data structure stores n values/integers.
Tap or hover the mouse pointer over any entry, operation, or data structure in the table for a brief explanation. But think about it first!
| A sequence of elements, where each element consists of a value and a pointer to the next element in the sequence.Linked List | A sequence of elements, where each element consists of a value and a pointer to both the previous and the next element in the sequence.Doubly-linked List | A sequence of elements. There are no empty spaces between the elements.Array | A sequence of sorted elements. There are no empty spaces between the elements.Sorted Array | An array that contains a bit for each possible value to indicate whether it is present (1) or not (0).Map | A rooted binary tree of which each node stores a value and has 0, 1, or 2 children. If a node has children, each child is labeled either as the left or the right child. A node with 2 children has both a left and a right child. Crucial: For each node N, the values stored in the nodes in the subtree rooted at the left child of N are less than the value stored in N; the values stored in the nodes in the subtree rooted at the right child of N are all bigger than the value stored in N. Based on the idea of the binary search algorithm. Binary Search Tree |
A rooted binary tree of which each node stores a value and has 0, 1, or 2 children. If a node has children, each child is labeled either as the left or the right child. A node with 2 children has both a left and a right child. Crucial: For each node N, the values stored in the nodes in the subtree rooted at the left child of N are less than the value stored in N; the values stored in the nodes in the subtree rooted at the right child of N are all bigger than the value stored in N. Based on the idea of the binary search algorithm. Invariant: The depth of any two leaves differs by at most 1 (as in a complete binary tree). The crucial trick is to maintain this invariant during insertion or deletion operations. For example: AVL trees or red-black trees.Balanced Binary Search Tree |
|
|---|---|---|---|---|---|---|---|
| Initialize the data structure.Init | O(1) | O(1) | O(1) | O(1) | The data structure is represented by an array D of size U, of which each element needs to be set to zero.O(U) | O(1) | O(1) |
| Decide whether a given value V is stored in the data structure.Find | We need to inspect every element in the sequence.O(n) | We need to inspect every element in the sequence.O(n) | We need to inspect every element in the sequence.O(n) | Use binary search.O(log n) | Inspect the array at the corresponding index.O(1) | Recall that the ordering on the children of the tree helps guide our search. If V is less than the value stored in the current node N of the tree, then move to the left child of N (if it exists). If V is less than the value stored in the current node N of the tree, then move to the right child of N (if it exists). If V is equal to the value stored in N, then answer Yes. Otherwise (particularly if N is a leaf), answer No. Note that leaves in a binary search tree might have depth O(n). Hence, we might spend O(n) time to reach a leaf and find V (or not).O(n) |
Recall that the ordering on the children of the tree helps guide our search. If V is less than the value stored in the current node N of the tree, then move to the left child of N (if it exists). If V is less than the value stored in the current node N of the tree, then move to the right child of N (if it exists). If V is equal to the value stored in N, then answer Yes. Otherwise (particularly if N is a leaf), answer No. Note that all leaves in a balanced binary search tree have depth O(log n). Hence, we spend O(log n) time to find V (or not).O(log n) |
| Insert a new value in the data structure. We do not check for duplicates (this requires an additional find operation).Insert | O(1) | O(1) | Normally, we spend O(1) time to append the new value at the end of the array. We only spend O(n) time if we need to reallocate the array to insert the new value; then we need to copy the entire array into the new space.O(1) / O(n) | To insert the value at the right position, we need to move all larger values one position to the right in the array. We also might need to spend O(n) time if we need to reallocate the array to insert the new value; then we need to copy the entire array into the new space.O(n) | O(1) | We need to search the tree to find the appropriate place where to insert the value. Similar to the find operation, the ordering on the children of the tree helps guide our search. However, as with a normal find, this might take O(n) time. If, however, we happen to already know the correct place in the tree structure where to insert the value, then we only require O(1) time.O(n) / O(1) | We need to search the tree to find the appropriate place where to insert the value. Similar to the find operation, the ordering on the children of the tree helps guide our search. As with a normal find, this takes O(log n) time. If, however, we happen to already know the correct node in the tree structure under which to insert the value, then we only require O(1) time. Crucial: After insertion, we need to re-balance the tree in O(log n) time: this is the beauty of AVL trees or red-black trees at work.O(log n) |
| Remove a value in the data structure. We assume that the value is stored in the data structure (verifying this requires an additional find operation).Delete | We need to spend O(n) time to locate the value in the list, remove it, and change the pointer of its predecessor (which we found during the find operation) in the list. If we already know where the predecessor is stored in the list, then only O(1) time is required.O(n) / O(1) | We need to spend O(n) time to locate the value in the list, remove it, and change the pointer of its predecessor in the list. If we already know where the value is stored in the list, then only O(1) time is required.O(n) / O(1) | We need to spend O(n) time to locate the value in the array. After that, or if we already know where the value is stored in the array, then we spend only O(1) time to remove it and move the last element of the array to the element we just removed (to ensure no empty spaces remain).O(n) / O(1) | We need to spend O(n) time to locate the value in the array. If we already know where the value is stored in the array, this takes O(1) time. After that, however, we spend O(n) time to move all larger values one element to the left (to ensure no empty spaces remain).O(n) | O(1) | We need to spend O(n) time to find the value in the tree. After that, or if we already know in which node of the tree the value is stored and its parent node, then we spend only O(1) time to remove it.O(n) / O(1) | We need to spend O(n) time to find the value in the tree. After that, or if we already know in which node of the tree the value is stored and its parent node, then we spend only O(1) time to remove it. Crucial: After removal, we need to re-balance the tree in O(log n) time: this is the beauty of AVL trees or red-black trees at work.O(log n) |
| Find some value that is stored in the data structure (if any).Some | O(1) | O(1) | O(1) | O(1) | We need to look in the array from the start.O(U-n) | O(1) | O(1) |
| Enumerate all values that are stored in the data structure. This takes Ω(n) time.Enum | O(n) | O(n) | O(n) | O(n) | O(U) | O(n) | O(n) |
| Enumerate all values that are stored in the data structure in order. This takes Ω(n) time.Order | This data structure is not ordered by default. Hence, we would need to sort the data structure first.O(n log n) | This data structure is not ordered by default. Hence, we would need to sort the data structure first.O(n log n) | This data structure is not ordered by default. Hence, we would need to sort the data structure first.O(n log n) | O(n) | O(U) | O(n) | O(n) |
| Given a value V, find the smallest value in the data structure that is larger than V.Succ | O(n) | O(n) | O(n) | If we already know where the current value V is stored in the array, then this needs O(1) time. Otherwise, we first need to execture a find in O(log n) time. If V is not stored in the array, a minor modification of the find operation suffices.O(log n) / O(1) | We need to look through the entire array after V.O(U) | A minor modification of the find operation suffices. We execute a find operation and consider the path from the root to the node N where the find operation stops. If N has no right child, then we look for the lowest ancestor A of N that has two children and the path used the left child. Otherwise, A is defined to be N. Then return the value stored in the leftmost leaf in the subtree rooted at the left child of A. Note that leaves in a binary search tree might have depth O(n). Hence, we might spend O(n) time to reach the sought leaf.O(n) |
A minor modification of the find operation suffices. We execute a find operation and consider the path from the root to the node N where the find operation stops. If N has no right child, then we look for the lowest ancestor A of N that has two children and the path used the left child. Otherwise, A is defined to be N. Then return the value stored in the leftmost leaf in the subtree rooted at the left child of A. Note that all leaves in a balanced binary search tree have depth O(log n). Hence, we spend O(log n) time to find the sought leaf.O(log n) |
| Given a value V, find the largest value in the data structure that is smaller than V.Pred | O(n) | O(n) | O(n) | If we already know where the current value V is stored in the array, then this needs O(1) time. Otherwise, we first need to execture a find in O(log n) time. If V is not stored in the array, a minor modification of the find operation suffices.O(log n) / O(1) | We need to look through the entire array before V.O(U) | A minor modification of the find operation suffices. We execute a find operation and consider the path from the root to the node N where the find operation stops. If N has no left child, then we look for the lowest ancestor A of N that has two children and the path used the right child. Otherwise, A is defined to be N. Then return the value stored in the rightmost leaf in the subtree rooted at the left child of A. Note that leaves in a binary search tree might have depth O(n). Hence, we might spend O(n) time to reach the sought leaf.O(n) |
A minor modification of the find operation suffices. We execute a find operation and consider the path from the root to the node N where the find operation stops. If N has no left child, then we look for the lowest ancestor A of N that has two children and the path used the right child. Otherwise, A is defined to be N. Then return the value stored in the rightmost leaf in the subtree rooted at the left child of A. Note that all leaves in a balanced binary search tree have depth O(log n). Hence, we spend O(log n) time to find the sought leaf.O(log n) |
| The amount of space that it takes to store the data structure.Space | O(n) | O(n) | The array might be made to occupy the first n entries of a much larger memory space of size N to avoid reallocations when inserting values, or to account for the space left over by removed values.N / O(n) | The array might be made to occupy the first n entries of a much larger memory space of size N to avoid reallocations when inserting values, or to account for the space left over by removed values.N / O(n) | The array contains a bit for each of the U possible values to indicate whether it is present or not.O(U) | O(n) | O(n) |
Created by Erik Jan van Leeuwen. It adds interactivity and explanations to a version of this table used by Raimund Seidel in his lectures.