Data Structures/All Chapters

This page shall be included in any copy of the Data Structures book.
Any source code included if not bearing a different statement shall be considered under the public domain.
Images used have their own copyright status, specified in their respective repositories (en.wikibooks.org or at commons.wikimedia.org).

Acknowledgment is given for using some contents from Wikipedia.

Computers can store and process vast amounts of data. Formal data structures enable a programmer to mentally structure large amounts of data into conceptually manageable relationships.

Sometimes we use data structures to allow us to do more: for example, to accomplish fast searching or sorting of data. Other times, we use data structures so that we can do less: for example, the concept of the stack is a limited form of a more general data structure. These limitations provide us with guarantees that allow us to reason about our programs more easily. Data structures also provide guarantees about algorithmic complexity — choosing an appropriate data structure for a job is crucial for writing good software.

Because data structures are higher-level abstractions, they present to us operations on groups of data, such as adding an item to a list, or looking up the highest-priority item in a queue. When a data structure provides operations, we can call the data structure an abstract data type (sometimes abbreviated as ADT). Abstract data types can minimize dependencies in your code, which is important when your code needs to be changed. Because you are abstracted away from lower-level details, some of the higher-level commonalities one data structure shares with a different data structure can be used to replace one with the other.

Our programming languages come equipped with a set of built-in types, such as integers and floating-point numbers, that allow us to work with data objects for which the machine's processor has native support. These built-in types are abstractions of what the processor actually provides because built-in types hide details both about their execution and limitations.

For example, when we use a floating-point number we are primarily concerned with its value and the operations that can be applied to it. Consider computing the length of a hypotenuse:

  let c := sqrt(a * a + b * b)


The machine code generated from the above would use common patterns for computing these values and accumulating the result. In fact, these patterns are so repetitious that high-level languages were created to avoid this redundancy and to allow programmers to think about what value was computed instead of how it was computed.

Two useful and related concepts are at play here:

• Encapsulation is when common patterns are grouped together under a single name and then parameterized, in order to achieve a higher-level understanding of that pattern. For example, the multiplication operation requires two source values and writes the product of those two values to a given destination. The operation is parameterized by both the two sources and the single destination.
• Abstraction is a mechanism to hide the implementation details of an abstraction away from the users of the abstraction. When we multiply numbers, for example, we don't need to know the technique actually used by the processor, we just need to know its properties.

A programming language is both an abstraction of a machine and a tool to encapsulate-away the machine's inner details. For example, a program written in a programming language can be compiled to several different machine architectures when that programming language sufficiently encapsulates the user away from any one machine.

In this book, we take the abstraction and encapsulation that our programming languages provide a step further: When applications get to be more complex, the abstractions of programming languages become too low-level to effectively manage. Thus, we build our own abstractions on top of these lower-level constructs. We can even build further abstractions on top of those abstractions. Each time we build upwards, we lose access to the lower-level implementation details. While losing such access might sound like a bad trade off, it is actually quite a bargain: We are primarily concerned with solving the problem at hand rather than with any trivial decisions that could have just as arbitrarily been replaced with a different decision. When we can think on higher levels, we relieve ourselves of these burdens.

Each data structure that we cover in this book can be thought of as a single unit that has a set of values and a set of operations that can be performed to either access or change these values. The data structure itself can be understood as a set of the data structure's operations together with each operation's properties (i.e., what the operation does and how long we could expect it to take).

Big-oh notation is a common way of expressing a computer code's performance. The notation creates a relationship between the number of items in memory and the average performance for a function. For a set of ${\displaystyle n}$ items, ${\displaystyle O(n)}$ indicates that a particular function will operate on the set ${\displaystyle n}$ times on average. ${\displaystyle O(1)}$ indicates that the function always performs a constant number of operations regardless of the number of items. The notation only represents algorithmic complexity so a function may perform more operations but constant multiples of ${\displaystyle n}$ are dropped by convention.

The Node

The first data structure we look at is the node structure. A node is simply a container for a value, plus a pointer to a "next" node (which may be null).

Node<Element> Operations

make-node(Element v, Node next): Node

Create a new node, with v as its contained value and next as the value of the next pointer

get-value(Node n): Element

Returns the value contained in node n

get-next(Node n): Node

Returns the value of node n's next pointer

set-value(Node n, Element v)

Sets the contained value of n to be v

set-next(Node n, Node new-next): Node

Sets the value of node n's next pointer to be new-next

All operations can be performed in time that is ${\displaystyle O(1)}$.

Examples of the "Element" type can be: numbers, strings, objects, functions, or even other nodes. Essentially, any type that has values at all in the language.

The above is an abstraction of a structure:

  structure node {
element value     // holds the value
node next         // pointer to the next node; possibly null
}


In some languages, structures are called records or classes. Some other languages provide no direct support for structures, but instead allow them to be built from other constructs (such as tuples or lists).

Here, we are only concerned that nodes contain values of some form, so we simply say its type is "element" because the type is not important. In some programming languages no type ever needs to be specified (as in dynamically typed languages, like Scheme, Smalltalk or Python). In other languages the type might need to be restricted to integer or string (as in statically typed languages like C). In still other languages, the decision of the type of the contained element can be delayed until the type is actually used (as in languages that support generic types, like C++ and Java). In any of these cases, translating the pseudocode into your own language should be relatively simple.

Each of the node operations specified can be implemented quite easily:

// Create a new node, with v as its contained value and next as
// the value of the next pointer
function make-node(v, node next): node
let result := new node {v, next}
return result
end

// Returns the value contained in node n
function get-value(node n): element
return n.value
end

// Returns the value of node n's next pointer
function get-next(node n): node
return n.next
end

// Sets the contained value of n to be v
function set-value(node n, v)
n.value := v
end

// Sets the value of node n's next pointer to be new-next
function set-next(node n, new-next)
n.next := new-next
return new-next
end


Principally, we are more concerned with the operations and the implementation strategy than we are with the structure itself and the low-level implementation. For example, we are more concerned about the time requirement specified, which states that all operations take time that is ${\displaystyle O(1)}$. The above implementation meets this criteria, because the length of time each operation takes is constant. Another way to think of constant time operations is to think of them as operations whose analysis is not dependent on any variable. (The notation ${\displaystyle O(1)}$ is mathematically defined in the next chapter. For now, it is safe to assume it just means constant time.)

Because a node is just a container both for a value and container to a pointer to another node, it shouldn't be surprising how trivial the node data structure itself (and its implementation) is.

Building a Chain from Nodes

Although the node structure is simple, it actually allows us to compute things that we couldn't have computed with just fixed-size integers alone.

But first, we'll look at a program that doesn't need to use nodes. The following program will read in (from an input stream; which can either be from the user or a file) a series of numbers until the end-of-file is reached and then output what the largest number is and the average of all numbers:

program(input-stream in, output-stream out)
let total := 0
let count := 0
let largest := ${\displaystyle -\infty }$

while has-next-integer(in):
let i := read-integer(in)
total := total + i
count := count + 1
largest := max(largest, i)
repeat

println out "Maximum: " largest

if count != 0:
println out "Average: " (total / count)
fi
end


But now consider solving a similar task: read in a series of numbers until the end-of-file is reached, and output the largest number and the average of all numbers that evenly divide the largest number. This problem is different because it's possible the largest number will be the last one entered: if we are to compute the average of all numbers that divide that number, we'll need to somehow remember all of them. We could use variables to remember the previous numbers, but variables would only help us solve the problem when there aren't too many numbers entered.

For example, suppose we were to give ourselves 200 variables to hold the state input by the user. And further suppose that each of the 200 variables had 64-bits. Even if we were very clever with our program, it could only compute results for ${\displaystyle 2^{64\cdot 200}}$ different types of input. While this is a very large number of combinations, a list of 300 64-bit numbers would require even more combinations to be properly encoded. (In general, the problem is said to require linear space. All programs that need only a finite number of variables can be solved in constant space.)

Instead of building-in limitations that complicate coding (such as having only a constant number of variables), we can use the properties of the node abstraction to allow us to remember as many numbers as our computer can hold:

program(input-stream in, output-stream out)
let largest := ${\displaystyle -\infty }$
let nodes := null

while has-next-integer(in):
let i := read-integer(in)
nodes := make-node(i, nodes) // contain the value i,
// and remember the previous numbers too
largest := max(largest, i)
repeat
println out "Maximum: " largest

// now compute the averages of all factors of largest
let total := 0
let count := 0
while nodes != null:
let j := get-value(nodes)
if j divides largest:
total := total + j
count := count + 1
fi
nodes := get-next(nodes)
repeat
if count != 0:
println out "Average: " (total / count)
fi
end


Above, if n integers are successfully read there will be n calls made to make-node. This will require n nodes to be made (which require enough space to hold the value and next fields of each node, plus internal memory management overhead), so the memory requirements will be on the order of ${\displaystyle O(n)}$. Similarly, we construct this chain of nodes and then iterate over the chain again, which will require ${\displaystyle O(n)}$ steps to make the chain, and then another ${\displaystyle O(n)}$ steps to iterate over it.

Note that when we iterate the numbers in the chain, we are actually looking at them in reverse order. For example, assume the numbers input to our program are 4, 7, 6, 30, and 15. After EOF is reached, the nodes chain will look like this:

Such chains are more commonly referred to as linked-lists. However, we generally prefer to think in terms of lists or sequences, which aren't as low-level: the linking concept is just an implementation detail. While a list can be made with a chain, in this book we cover several other ways to make a list. For the moment, we care more about the abstraction capabilities of the node than we do about one of the ways it is used.

The above algorithm only uses the make-node, get-value, and get-next functions. If we use set-next we can change the algorithm to generate the chain so that it keeps the original ordering (instead of reversing it).

 To do: pseudocode to do so; also TODO; should probably think of compelling, but not too-advanced, use of set-value.
program (input-stream in, output-stream out)
let largest := ${\displaystyle -\infty }$
let nodes := null
let tail_node := null

while has-next-integer (in):
let i := read-integer (in)
if (nodes == null)
nodes := make-node(i, null) // construct first node in the list
tail_node := nodes //there is one node in the list=> first and last are the same
else
tail_node := set-next (tail_node, make-node (i, null)) // append new node to the end of the list
largest := max(largest, i)
repeat
println out "Maximum: " largest

// now compute the averages of all factors of largest
let total := 0
let count := 0
while nodes != null:
let j := get-value(nodes)
if j divides largest:
total := total + j
count := count + 1
fi
nodes := get-next(nodes)
repeat
if count != 0:
println out "Average: " (total / count)
fi
end


The Principle of Induction

The chains we can build from nodes are a demonstration of the principle of mathematical induction:

 Mathematical Induction Suppose you have some property of numbers ${\displaystyle P(n)}$ If you can prove that when ${\displaystyle P(n)}$ holds that ${\displaystyle P(n+1)}$ must also hold, then All you need to do is prove that ${\displaystyle P(1)}$ holds to show that ${\displaystyle P(n)}$ holds for all natural ${\displaystyle n}$

For example, let the property ${\displaystyle P(n)}$ be the statement that "you can make a chain that holds ${\displaystyle n}$ numbers". This is a property of natural numbers, because the sentence makes sense for specific values of ${\displaystyle n}$:

• you can make a chain that holds 5 numbers
• you can make a chain that holds 100 numbers
• you can make a chain that holds 1,000,000 numbers

Instead of proving that we can make chains of length 5, 100, and one million, we'd rather prove the general statement ${\displaystyle P(n)}$ instead. Step 2 above is called the Inductive Hypothesis; let's show that we can prove it:

• Assume that ${\displaystyle P(n)}$ holds. That is, that we can make a chain of ${\displaystyle n}$ elements. Now we must show that ${\displaystyle P(n+1)}$ holds.
• Assume chain is the first node of the ${\displaystyle n}$-element chain. Assume i is some number that we'd like to add to the chain to make an ${\displaystyle n+1}$ length chain.
• The following code can accomplish this for us:
let bigger-chain := make-node(i, chain)

• Here, we have the new number i that is now the contained value of the first link of the bigger-chain. If chain had ${\displaystyle n}$ elements, then bigger-chain must have ${\displaystyle n+1}$ elements.

Step 3 above is called the Base Case, let's show that we can prove it:

• We must show that ${\displaystyle P(1)}$ holds. That is, that we can make a chain of one element.
• The following code can accomplish this for us:
let chain := make-node(i, null)


The principle of induction says, then, that we have proven that we can make a chain of ${\displaystyle n}$ elements for all value of ${\displaystyle n\geq 1}$. How is this so? Probably the best way to think of induction is that it's actually a way of creating a formula to describe an infinite number of proofs. After we prove that the statement is true for ${\displaystyle P(1)}$, the base case, we can apply the inductive hypothesis to that fact to show that ${\displaystyle P(2)}$ holds. Since we now know that ${\displaystyle P(2)}$ holds, we can apply the inductive hypothesis again to show that ${\displaystyle P(3)}$ must hold. The principle says that there is nothing to stop us from doing this repeatedly, so we should assume it holds for all cases.

Induction may sound like a strange way to prove things, but it's a very useful technique. What makes the technique so useful is that it can take a hard sounding statement like "prove ${\displaystyle P(n)}$ holds for all ${\displaystyle n\geq 1}$" and break it into two smaller, easier to prove statements. Typically base cases are easy to prove because they are not general statements at all. Most of the proof work is usually in the inductive hypothesis, which can often require clever ways of reformulating the statement to "attach on" a proof of the ${\displaystyle n+1}$ case.

You can think of the contained value of a node as a base case, while the next pointer of the node as the inductive hypothesis. Just as in mathematical induction, we can break the hard problem of storing an arbitrary number of elements into an easier problem of just storing one element and then having a mechanism to attach on further elements.

Induction on a Summation

The next example of induction we consider is more algebraic in nature:

Let's say we are given the formula ${\displaystyle {\frac {(n)(n+1)}{2}}}$ and we want to prove that this formula gives us the sum of the first ${\displaystyle n}$ numbers. As a first attempt, we might try to just show that this is true for 1

${\displaystyle {\frac {(1)(1+1)}{2}}=1=1}$,

for 2

${\displaystyle {\frac {(2)(2+1)}{2}}=3=1+2}$,

for 3

${\displaystyle {\frac {(3)(3+1)}{2}}=6=1+2+3}$

and so on, however we'd quickly realize that our so called proof would take infinitely long to write out! Even if you carried out this proof and showed it to be true for the first billion numbers, that doesn't nescessarily mean that it would be true for one billion and one or even a hundred billion. This is a strong hint that maybe induction would be useful here.

Let's say we want to prove that the given formula really does give the sum of the first n numbers using induction. The first step is to prove the base case; i.e. we have to show that it is true when n = 1. This is relatively easy; we just substitute 1 for the variable n and we get (${\displaystyle {\frac {(1)(1+1)}{2}}=1}$), which shows that the formula is correct when n = 1.

Now for the inductive step. We have to show that if the formula is true for j, it is also true for j + 1. To phrase it another way, assuming we've already proven that the sum from 1 to (j) is ${\displaystyle {\frac {((j))((j)+1)}{2}}}$, we want to prove that the sum from 1 to (j+1) is ${\displaystyle {\frac {((j+1))((j+1)+1)}{2}}}$. Note that those two formulas came about just by replacing n with (j) and (j+1) respectively.

To prove this inductive step, first note that to calculate the sum from 1 to j+1, you can just calculate the sum from 1 to j, then add j+1 to it. We already have a formula for the sum from 1 to j, and when we add j+1 to that formula, we get this new formula: ${\displaystyle {\frac {((j))((j)+1)}{2}}+(j+1)}$. So to actually complete the proof, all we'd need to do is show that ${\displaystyle {\frac {((j))((j)+1)}{2}}+(j+1)={\frac {((j+1))((j+1)+1)}{2}}}$.

We can show the above equation is true via a few simplification steps:

${\displaystyle {\frac {((j))((j)+1)}{2}}+(j+1)={\frac {((j+1))((j+1)+1)}{2}}}$

${\displaystyle {\frac {(j)(j+1)}{2}}+j+1={\frac {(j+1)(j+1+1)}{2}}}$

${\displaystyle {\frac {(j)(j+1)}{2}}+{\frac {2(j+1)}{2}}={\frac {(j+1)(j+2)}{2}}}$

${\displaystyle {\frac {(j)(j+1)+2(j+1)}{2}}={\frac {(j+1)(j+2)}{2}}}$

${\displaystyle {\frac {j^{2}+j+2j+2}{2}}={\frac {(j+1)(j+2)}{2}}}$

${\displaystyle {\frac {j^{2}+3j+2}{2}}={\frac {(j+1)(j+2)}{2}}}$

${\displaystyle {\frac {(j+1)(j+2)}{2}}={\frac {(j+1)(j+2)}{2}}}$

Asymptotic Notation

Introduction

There is no single data structure that offers optimal performance in every case. In order to choose the best structure for a particular task, we need to be able to judge how long a particular solution will take to run. Or, more accurately, you need to be able to judge how long two solutions will take to run, and choose the better of the two. We don't need to know how many minutes and seconds they will take, but we do need some way to compare algorithms against one another.

Asymptotic complexity is a way of expressing the main component of the cost of an algorithm, using idealized (not comparable) units of computational work. Consider, for example, the algorithm for sorting a deck of cards, which proceeds by repeatedly searching through the deck for the lowest card. The asymptotic complexity of this algorithm is the square of the number of cards in the deck. This quadratic behavior is the main term in the complexity formula, it says, e.g., if you double the size of the deck, then the work is roughly quadrupled.

The exact formula for the cost is more complex, and it contains more details than we need to understand the essential complexity of the algorithm. With our deck of cards, in the worst case, the deck would start out reverse-sorted, so our scans would have to go all the way to the end. The first scan would involve scanning 52 cards, the next would take 51, etc. So the cost formula is 52 + 51 + ..... + 2. Generally, letting N be the number of cards, the formula is 2 + ... + N, which equals ${\displaystyle ((N)\times (N+1)/2)-1=((N^{2}+N)/2)-1=(1/2)N^{2}+(1/2)N-1}$. But the ${\displaystyle N^{2}}$ term dominates the expression, and this is what is key for comparing algorithm costs. (This is in fact an expensive algorithm; the best sorting algorithms run in sub-quadratic time.)

Asymptotically speaking, in the limit as N tends towards infinity, 2 + 3 + .,,,.. + N gets closer and closer to the pure quadratic function (1/2)N^2. And what difference does the constant factor of 1/2 make, at this level of abstraction? So the behavior is said to be ${\displaystyle O(n^{2})}$.

Now let us consider how we would go about comparing the complexity of two algorithms. Let f(n) be the cost, in the worst case, of one algorithm, expressed as a function of the input size n, and g(n) be the cost function for the other algorithm. E.g., for sorting algorithms, f(10) and g(10) would be the maximum number of steps that the algorithms would take on a list of 10 items. If, for all values of n >= 0, f(n) is less than or equal to g(n), then the algorithm with complexity function f is strictly faster. But, generally speaking, our concern for computational cost is for the cases with large inputs; so the comparison of f(n) and g(n) for small values of n is less significant than the "long term" comparison of f(n) and g(n), for n larger than some threshold.

Note that we have been speaking about bounds on the performance of algorithms, rather than giving exact speeds. The actual number of steps required to sort our deck of cards (with our naive quadratic algorithm) will depend upon the order in which the cards begin. The actual time to perform each of our steps will depend upon our processor speed, the condition of our processor cache, etc., etc. It's all very complicated in the concrete details, and moreover not relevant to the essence of the algorithm.

The O Notation

Definition

The O (pronounced big-oh) is the formal method of expressing the upper bound of an algorithm's running time. It's a measure of the longest amount of time it could possibly take for the algorithm to complete. We can assume that it represents the "worst case scenario" of a program.

More formally, for non-negative functions, f(n) and g(n), if there exists an integer ${\displaystyle n_{0}}$ and a constant c > 0 such that for all integers ${\displaystyle n>n_{0}}$, f(n) ≤ cg(n), then f(n) is Big O of g(n). This is denoted as "f(n) = O(g(n))". If graphed, g(n) serves as an upper bound to the curve you are analyzing, f(n).

Note that if f can take on finite values only (as it should happen normally) then this definition implies that there exists some constant C (potentially larger than c) such that for all values of n, f(n) ≤ Cg(n). An appropriate value for C is the maximum of c and ${\displaystyle \max _{1\leq n\leq n_{0}}f(n)/g(n)}$.

Theory Examples

So, let's take an example of Big-O. Say that f(n) = 2n + 8, and g(n) = ${\displaystyle n^{2}}$. Can we find a constant ${\displaystyle n_{0}}$, so that 2n + 8 <= ${\displaystyle n^{2}}$? The number 4 works here, giving us 16 <= 16. For any number n greater than 4, this will still work. Since we're trying to generalize this for large values of n, and small values (1, 2, 3) aren't that important, we can say that f(n) is generally faster than g(n); that is, f(n) is bound by g(n), and will always be less than it.

It could then be said that f(n) runs in O(${\displaystyle n^{2}}$) time: "f-of-n runs in Big-O of n-squared time".

To find the upper bound - the Big-O time - assuming we know that f(n) is equal to (exactly) 2n + 8, we can take a few shortcuts. For example, we can remove all constants from the runtime; eventually, at some value of c, they become irrelevant. This makes f(n) = 2n. Also, for convenience of comparison, we remove constant multipliers; in this case, the 2. This makes f(n) = n. It could also be said that f(n) runs in O(n) time; that lets us put a tighter (closer) upper bound onto the estimate.

Practical Examples

O(n): printing a list of n items to the screen, looking at each item once.

O(ln n): also "log n", taking a list of items, cutting it in half repeatedly until there's only one item left.

O(${\displaystyle n^{2}}$): taking a list of n items, and comparing every item to every other item.

Big-Omega Notation

For non-negative functions, f(n) and g(n), if there exists an integer ${\displaystyle n_{0}}$ and a constant c > 0 such that for all integers ${\displaystyle n>n_{0}}$, f(n) ≥ cg(n), then f(n) is omega of g(n). This is denoted as "f(n) = Ω(g(n))".

This is almost the same definition as Big Oh, except that "f(n) ≥ cg(n)", this makes g(n) a lower bound function, instead of an upper bound function. It describes the best that can happen for a given data size.

Theta Notation

For non-negative functions, f(n) and g(n), f(n) is theta of g(n) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). This is denoted as "f(n) = Θ(g(n))".

This is basically saying that the function, f(n) is bounded both from the top and bottom by the same function, g(n).

The theta notation is denoted by Q.

Little-O Notation

For non-negative functions, f(n) and g(n), f(n) is little o of g(n) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n)). This is denoted as "f(n) = o(g(n))".

This represents a loose bounding version of Big O. g(n) bounds from the top, but it does not bound the bottom.

Little Omega Notation

For non-negative functions, f(n) and g(n), f(n) is little omega of g(n) if and only if f(n) = Ω(g(n)), but f(n) ≠ Θ(g(n)). This is denoted as "f(n) = ω(g(n))".

Much like Little Oh, this is the equivalent for Big Omega. g(n) is a loose lower boundary of the function f(n); it bounds from the bottom, but not from the top.

How asymptotic notation relates to analyzing complexity

Temporal comparison is not the only issue in algorithms. There are space issues as well. Generally, a trade off between time and space is noticed in algorithms. Asymptotic notation empowers you to make that trade off. If you think of the amount of time and space your algorithm uses as a function of your data over time or space (time and space are usually analyzed separately), you can analyze how the time and space is handled when you introduce more data to your program.

This is important in data structures because you want a structure that behaves efficiently as you increase the amount of data it handles. Keep in mind though that algorithms that are efficient with large amounts of data are not always simple and efficient for small amounts of data. So if you know you are working with only a small amount of data and you have concerns for speed and code space, a trade off can be made for a function that does not behave well for large amounts of data.

A few examples of asymptotic notation

Generally, we use asymptotic notation as a convenient way to examine what can happen in a function in the worst case or in the best case. For example, if you want to write a function that searches through an array of numbers and returns the smallest one:

function find-min(array a[1..n])
let j := ${\displaystyle \infty }$
for i := 1 to n:
j := min(j, a[i])
repeat
return j
end


Regardless of how big or small the array is, every time we run find-min, we have to initialize the i and j integer variables and return j at the end. Therefore, we can just think of those parts of the function as constant and ignore them.

So, how can we use asymptotic notation to discuss the find-min function? If we search through an array with 87 elements, then the for loop iterates 87 times, even if the very first element we hit turns out to be the minimum. Likewise, for ${\displaystyle n}$ elements, the for loop iterates ${\displaystyle n}$ times. Therefore we say the function runs in time ${\displaystyle O(n)}$.

function find-min-plus-max(array a[1..n])
// First, find the smallest element in the array
let j := ${\displaystyle \infty }$;
for i := 1 to n:
j := min(j, a[i])
repeat
let minim := j

// Now, find the biggest element, add it to the smallest and
j := ${\displaystyle -\infty }$;
for i := 1 to n:
j := max(j, a[i])
repeat
let maxim := j

// return the sum of the two
return minim + maxim;
end


What's the running time for find-min-plus-max? There are two for loops, that each iterate ${\displaystyle n}$ times, so the running time is clearly ${\displaystyle O(2n)}$. Because 2 is a constant, we throw it away and write the running time as ${\displaystyle O(n)}$. Why can you do this? If you recall the definition of Big-O notation, the function whose bound you're testing can be multiplied by some constant. If f(x) = 2x, we can see that if g(x) = x, then the Big-O condition holds. Thus ${\displaystyle O(2n)=O(n)}$. This rule is general for the various asymptotic notations.

Arrays

An array is a collection, mainly of similar data types, stored into a common variable. The collection forms a data structure where objects are stored linearly, one after another in memory. Sometimes arrays are even replicated into the memory hardware.

The structure can also be defined as a particular method of storing elements of indexed data. Elements of data are logically stored sequentially in blocks within the array. Each element is referenced by an index, or subscripts.

The index is usually a number used to address an element in the array. For example, if you were storing information about each day in August, you would create an array with an index capable of addressing 31 values -- one for each day of the month. Indexing rules are language dependent, however most languages use either 0 or 1 as the first element of an array.

The concept of an array can be daunting to the uninitiated, but it is really quite simple. Think of a notebook with pages numbered 1 through 12. Each page may or may not contain information on it. The notebook is an array of pages. Each page is an element of the array 'notebook'. Programmatically, you would retrieve information from a page by referring to its number or subscript, i.e., notebook(4) would refer to the contents of page 4 of the array notebook.

The notebook (array) contains 12 pages (elements)

Arrays can also be multidimensional - instead of accessing an element of a one-dimensional list, elements are accessed by two or more indices, as from a matrix or tensor.

Multidimensional arrays are as simple as our notebook example above. To envision a multidimensional array, think of a calendar. Each page of the calendar, 1 through 12, is an element, representing a month, which contains approximately 30 elements, which represent days. Each day may or may not have information in it. Programmatically then, calendar(4,15) would refer to the 4th month, 15th day. Thus we have a two-dimensional array. To envision a three-dimensional array, break each day up into 24 hours. Now calendar(4,15,9) would refer to 4th month, 15th day, 9th hour.

A simple 6 element by 4 element array

Array<Element> Operations

make-array(integer n): Array

Create an array of elements indexed from ${\displaystyle 0}$ to ${\displaystyle n-1}$, inclusive. The number of elements in the array, also known as the size of the array, is n.

get-value-at(Array a, integer index): Element

Returns the value of the element at the given index. The value of index must be in bounds: 0 <= index <= (n - 1). This operation is also known as subscripting.

set-value-at(Array a, integer index, Element new-value)

Sets the element of the array at the given index to be equal to new-value.

Arrays guarantee constant time read and write access, ${\displaystyle O(1)}$, however many lookup operations (find_min, find_max, find_index) of an instance of an element are linear time, ${\displaystyle O(n)}$. Arrays are very efficient in most languages, as operations compute the address of an element via a simple formula based on the base address element of the array.

Array implementations differ greatly between languages: some languages allow arrays to be re-sized automatically, or to even contain elements of differing types (such as Perl). Other languages are very strict and require the type and length information of an array to be known at run time (such as C).

Arrays typically map directly to contiguous storage locations within your computer's memory and are therefore the "natural" storage structure for most higher level languages.

Simple linear arrays are the basis for most of the other data structures. Many languages do not allow you to allocate any structure except an array, everything else must be implemented on top of the array. The exception is the linked list, that is typically implemented as individually allocated objects, but it is possible to implement a linked list within an array.

Type

The array index needs to be of some type. Usually, the standard integer type of that language is used, but there are also languages such as Ada and Pascal which allow any discrete type as an array index. Scripting languages often allow any type as an index (associative array).

Bounds

The array index consists of a range of values with a lower bound and an upper bound.

In some programming languages only the upper bound can be chosen while the lower bound is fixed to be either 0 (C, C++, C#, Java) or 1 (FORTRAN 66, R).

In other programming languages (Ada, PL/I, Pascal) both the upper and lower bound can be freely chosen (even negative).

Bounds check

The third aspect of an array index is the check for valid ranges and what happens when an invalid index is accessed. This is a very important point since the majority of computer worms and computer viruses attack by using invalid array bounds.

There are three options open:

1. Most languages (Ada, PL/I, Pascal, Java, C#) will check the bounds and raise some error condition when an element is accessed which does not exist.
2. A few languages (C, C++) will not check the bounds and return or set some arbitrary value when an element outside the valid range is accessed.
3. Scripting languages often automatically expand the array when data is written to an index which was not valid until then.

Declaring Array Types

The declaration of array type depends on how many features the array in a particular language has.

The easiest declaration is when the language has a fixed lower bound and fixed index type. If you need an array to store the monthly income you could declare in C

typedef double Income[12];


This gives you an array with in the range of 0 to 11. For a full description of arrays in C see C Programming/Arrays.

If you use a language where you can choose both the lower bound as well as the index type, the declaration is -- of course -- more complex. Here are two examples in Ada:

type Month is range 1 .. 12;
type Income is array(Month) of Float;


or shorter:

type Income is array(1 .. 12) of Float;


For a full description of arrays in Ada see Ada Programming/Types/array.

Array Access

We generally write arrays with a name, followed by the index in some brackets, square '[]' or round '()'. For example, august[3] is the method used in the C programming language to refer to a particular day in the month.

Because the C language starts the index at zero, august[3] is the 4th element in the array. august[0] actually refers to the first element of this array. Starting an index at zero is natural for computers, whose internal representations of numbers begin with zero, but for humans, this unnatural numbering system can lead to problems when accessing data in an array. When fetching an element in a language with zero-based indexes, keep in mind the true length of an array, lest you find yourself fetching the wrong data. This is the disadvantage of programming in languages with fixed lower bounds, the programmer must always remember that "[0]" means "1st" and, when appropriate, add or subtract one from the index. Languages with variable lower bounds will take that burden off the programmer's shoulder.

We use indexes to store related data. If our C language array is called august, and we wish to store that we're going to the supermarket on the 1st, we can say, for example

august[0] = "Going to the shops today"


In this way, we can go through the indexes from 0 to 30 and get the related tasks for each day in august.

List Structures and Iterators

We have seen now two different data structures that allow us to store an ordered sequence of elements. However, they have two very different interfaces. The array allows us to use get-element() and set-element() functions to access and change elements. The node chain requires us to use get-next() until we find the desired node, and then we can use get-value() and set-value() to access and modify its value. Now, what if you've written some code, and you realize that you should have been using the other sequence data structure? You have to go through all of the code you've already written and change one set of accessor functions into another. What a pain! Fortunately, there is a way to localize this change into only one place: by using the List Abstract Data Type (ADT).

List<item-type> ADT

get-begin():List Iterator<item-type>
Returns the list iterator (we'll define this soon) that represents the first element of the list. Runs in ${\displaystyle O(1)}$ time.
get-end():List Iterator<item-type>
Returns the list iterator that represents one element past the last element in the list. Runs in ${\displaystyle O(1)}$ time.
prepend(new-item:item-type)
Adds a new element at the beginning of a list. Runs in ${\displaystyle O(1)}$ time.
insert-after(iter:List Iterator<item-type>, new-item:item-type)
Adds a new element immediately after iter. Runs in ${\displaystyle O(N)}$ time.
remove-first()
Removes the element at the beginning of a list. Runs in ${\displaystyle O(1)}$ time.
remove-after(iter:List Iterator<item-type>)
Removes the element immediately after iter. Runs in ${\displaystyle O(N)}$ time.
is-empty():Boolean
True if there are no elements in the list. Has a default implementation. Runs in ${\displaystyle O(1)}$ time.
get-size():Integer
Returns the number of elements in the list. Has a default implementation. Runs in ${\displaystyle O(N)}$ time.
get-nth(n:Integer):item-type
Returns the nth element in the list, counting from 0. Has a default implementation. Runs in ${\displaystyle O(N)}$ time.
set-nth(n:Integer, new-value:item-type)
Assigns a new value to the nth element in the list, counting from 0. Has a default implementation. Runs in ${\displaystyle O(N)}$ time.

The iterator is another abstraction that encapsulates both access to a single element and incremental movement around the list. Its interface is very similar to the node interface presented in the introduction, but since it is an abstract type, different lists can implement it differently.

List Iterator<item-type> ADT

get-value():item-type
Returns the value of the list element that this iterator refers to.
set-value(new-value:item-type)
Assigns a new value to the list element that this iterator refers to.
move-next()
Makes this iterator refer to the next element in the list.
equal(other-iter:List Iterator<item-type>):Boolean
True if the other iterator refers to the same list element as this iterator.

All operations run in ${\displaystyle O(1)}$ time.

There are several other aspects of the List ADT's definition that need more explanation. First, notice that the get-end() operation returns an iterator that is "one past the end" of the list. This makes its implementation a little trickier, but allows you to write loops like:

var iter:List Iterator := list.get-begin()
while(not iter.equal(list.get-end()))
# Do stuff with the iterator
iter.move-next()
end while


Second, each operation gives a worst-case running time. Any implementation of the List ADT is guaranteed to be able to run these operation at least that fast. Most implementations will run most of the operations faster. For example, the node chain implementation of List can run insert-after() in ${\displaystyle O(1)}$.

Third, some of the operations say that they have a default implementation. This means that these operations can be implemented in terms of other, more primitive operations. They're included in the ADT so that certain implementations can implement them faster. For example, the default implementation of get-nth() runs in ${\displaystyle O(N)}$ because it has to traverse all of the elements before the nth. Yet the array implementation of List can implement it in ${\displaystyle O(1)}$ using its get-element() operation. The other default implementations are:

abstract type List<item-type>
method is-empty()
return get-begin().equal(get-end())
end method

method get-size():Integer
var size:Integer := 0
var iter:List Iterator<item-type> := get-begin()
while(not iter.equal(get-end()))
size := size+1
iter.move-next()
end while
return size
end method

helper method find-nth(n:Integer):List Iterator<item-type>
if n >= get-size()
error "The index is past the end of the list"
end if
var iter:List Iterator<item-type> := get-begin()
while(n > 0)
iter.move-next()
n := n-1
end while
return iter
end method

method get-nth(n:Integer):item-type
return find-nth(n).get-value()
end method

method set-nth(n:Integer, new-value:item-type)
find-nth(n).set-value(new-value)
end method
end type


Syntactic Sugar

Occasionally throughout this book we'll introduce an abbreviation that will allow us to write, and you to read, less pseudocode. For now, we'll introduce an easier way to compare iterators and a specialized loop for traversing sequences.

Instead of using the equal() method to compare iterators, we'll overload the == operator. To be precise, the following two expressions are equivalent:

iter1.equal(iter2)
iter1 == iter2


Second, we'll use the for keyword to express list traversal. The following two blocks are equivalent:

var iter:List Iterator<item-type> := list.get-begin()
while(not iter == list.get-end())
operations on iter
iter.move-next()
end while

for iter in list
operations on iter
end for


Implementations

In order to actually use the List ADT, we need to write a concrete data type that implements its interface. There are two standard data types that naturally implement List: the node chain described in the Introduction, normally called a Singly Linked List; and an extension of the array type called a Vector, which automatically resizes itself to accommodate inserted nodes.

type Singly Linked List<item-type> implements List<item-type>


head refers to the first node in the list. When it's null, the list is empty.

  data head:Node<item-type>


Initially, the list is empty.

  constructor()
end constructor

method get-begin():Sll Iterator<item-type>
end method



The "one past the end" iterator is just a null node. To see why, think about what you get when you have an iterator for the last element in the list and you call move-next().

  method get-end():Sll Iterator<item-type>
return new Sll-Iterator(null)
end method

method prepend(new-item:item-type)
end method

method insert-after(iter:Sll Iterator<item-type>, new-item:item-type)
var new-node:Node<item-type> := make-node(new-item, iter.node().get-next())
iter.node.set-next(new-node)
end method

method remove-first()
end method



This takes the node the iterator holds and makes it point to the node two nodes later.

  method remove-after(iter:Sll Iterator<item-type>)
iter.node.set-next(iter.node.get-next().get-next())
end method
end type


If we want to make get-size() be an ${\displaystyle O(1)}$ operation, we can add an Integer data member that keeps track of the list's size at all times. Otherwise, the default ${\displaystyle O(N)}$ implementation works fine.

An iterator for a singly linked list simply consists of a reference to a node.

type Sll Iterator<item-type>
data node:Node<item-type>

constructor(_node:Node<item-type>)
node := _node
end constructor


Most of the operations just pass through to the node.

  method get-value():item-type
return node.get-value()
end method

method set-value(new-value:item-type)
node.set-value(new-value)
end method

method move-next()
node := node.get-next()
end method


For equality testing, we assume that the underlying system knows how to compare nodes for equality. In nearly all languages, this would be a pointer comparison.

  method equal(other-iter:List Iterator<item-type>):Boolean
return node == other-iter.node
end method
end type


Vector

Let's write the Vector's iterator first. It will make the Vector's implementation clearer.

type Vector Iterator<item-type>
data array:Array<item-type>
data index:Integer

constructor(my_array:Array<item-type>, my_index:Integer)
array := my_array
index := my_index
end constructor

method get-value():item-type
return array.get-element(index)
end method

method set-value(new-value:item-type)
array.set-element(index, new-value)
end method

method move-next()
index := index+1
end method

method equal(other-iter:List Iterator<item-type>):Boolean
return array==other-iter.array and index==other-iter.index
end method
end type


We implement the Vector in terms of the primitive Array data type. It is inefficient to always keep the array exactly the right size (think of how much resizing you'd have to do), so we store both a size, the number of logical elements in the Vector, and a capacity, the number of spaces in the array. The array's valid indices will always range from 0 to capacity-1.

type Vector<item-type>
data array:Array<item-type>
data size:Integer
data capacity:Integer


We initialize the vector with a capacity of 10. Choosing 10 was fairly arbitrary. If we'd wanted to make it appear less arbitrary, we would have chosen a power of 2, and innocent readers like you would assume that there was some deep, binary-related reason for the choice.

  constructor()
array := create-array(0, 9)
size := 0
capacity := 10
end constructor

method get-begin():Vector-Iterator<item-type>
return new Vector-Iterator(array, 0)
end method


The end iterator has an index of size. That's one more than the highest valid index.

  method get-end():List Iterator<item-type>
return new Vector-Iterator(array, size)
end method


We'll use this method to help us implement the insertion routines. After it is called, the capacity of the array is guaranteed to be at least new-capacity. A naive implementation would simply allocate a new array with exactly new-capacity elements and copy the old array over. To see why this is inefficient, think what would happen if we started appending elements in a loop. Once we exceeded the original capacity, each new element would require us to copy the entire array. That's why this implementation at least doubles the size of the underlying array any time it needs to grow.

  helper method ensure-capacity(new-capacity:Integer)


If the current capacity is already big enough, return quickly.

    if capacity >= new-capacity
return
end if


Now, find the new capacity we'll need,

    var allocated-capacity:Integer := max(capacity*2, new-capacity)
var new-array:Array<item-type> := create-array(0, allocated-capacity - 1)


copy over the old array,

    for i in 0..size-1
new-array.set-element(i, array.get-element(i))
end for


and update the Vector's state.

    array := new-array
capacity := allocated-capacity
end method


This method uses a normally-illegal iterator, which refers to the item one before the start of the Vector, to trick insert-after() into doing the right thing. By doing this, we avoid duplicating code.

  method prepend(new-item:item-type)
insert-after(new Vector-Iterator(array, -1), new-item)
end method


insert-after() needs to copy all of the elements between iter and the end of the Vector. This means that in general, it runs in ${\displaystyle O(N)}$ time. However, in the special case where iter refers to the last element in the vector, we don't need to copy any elements to make room for the new one. An append operation can run in ${\displaystyle O(1)}$ time, plus the time needed for the ensure-capacity() call. ensure-capacity() will sometimes need to copy the whole array, which takes ${\displaystyle O(N)}$ time. But much more often, it doesn't need to do anything at all.

Amortized Analysis
In fact, if you think of a series of append operations starting immediately after ensure-capacity() increases the Vector's capacity (call the capacity here ${\displaystyle C}$), and ending immediately after the next increase in capacity, you can see that there will be exactly ${\displaystyle {\frac {C}{2}}=O(C)}$ appends. At the later increase in capacity, it will need to copy ${\displaystyle C}$ elements over to the new array. So this entire sequence of ${\displaystyle {\frac {C}{2}}}$ function calls took ${\displaystyle {\frac {3C}{2}}=O(C)}$ operations. We call this situation, where there are ${\displaystyle O(N)}$ operations for ${\displaystyle O(N)}$ function calls "amortized ${\displaystyle O(1)}$ time".

  method insert-after(iter:Vector Iterator<item-type>, new-item:item-type)
ensure-capacity(size+1)


This loop copies all of the elements in the vector into the spot one index up. We loop backwards in order to make room for each successive element just before we copy it.

    for i in size-1 .. iter.index+1 step -1
array.set-element(i+1, array.get-element(i))
end for


Now that there is an empty space in the middle of the array, we can put the new element there.

    array.set-element(iter.index+1, new-item)


And update the Vector's size.

    size := size+1
end method



Again, cheats a little bit to avoid duplicate code.

  method remove-first()
remove-after(new Vector-Iterator(array, -1))
end method



Like insert-after(), remove-after needs to copy all of the elements between iter and the end of the Vector. So in general, it runs in ${\displaystyle O(N)}$ time. But in the special case where iter refers to the last element in the vector, we can simply decrement the Vector's size, without copying any elements. A remove-last operation runs in ${\displaystyle O(1)}$ time.

  method remove-after(iter:List Iterator<item-type>)
for i in iter.index+1 .. size-2
array.set-element(i, array.get-element(i+1))
end for
size := size-1
end method



This method has a default implementation, but we're already storing the size, so we can implement it in ${\displaystyle O(1)}$ time, rather than the default's ${\displaystyle O(N).}$

  method get-size():Integer
return size
end method


Because an array allows constant-time access to elements, we can implement get- and set-nth() in ${\displaystyle O(1)}$, rather than the default implementation's ${\displaystyle O(N)}$

  method get-nth(n:Integer):item-type
return array.get-element(n)
end method

method set-nth(n:Integer, new-value:item-type)
array.set-element(n, new-value)
end method
end type


Bidirectional Lists

 To do: This is very terse. It should be fleshed out later.

Sometimes we want Data Structures/All Chaptersto move backward in a list too.

Bidirectional List<item-type> ADT

get-begin():Bidirectional List Iterator<item-type>
Returns the list iterator (we'll define this soon) that represents the first element of the list. Runs in ${\displaystyle O(1)}$ time.
get-end():Bidirectional List Iterator<item-type>
Returns the list iterator that represents one element past the last element in the list. Runs in ${\displaystyle O(1)}$ time.
insert(iter:Bidirectional List Iterator<item-type>, new-item:item-type)
Adds a new element immediately before iter. Runs in ${\displaystyle O(N)}$ time.
remove(iter:Bidirectional List Iterator<item-type>)
Removes the element immediately referred to by iter. After this call, iter will refer to the next element in the list. Runs in ${\displaystyle O(N)}$ time.
is-empty():Boolean
True iff there are no elements in the list. Has a default implementation. Runs in ${\displaystyle O(1)}$ time.
get-size():Integer
Returns the number of elements in the list. Has a default implementation. Runs in ${\displaystyle O(N)}$ time.
get-nth(n:Integer):item-type
Returns the nth element in the list, counting from 0. Has a default implementation. Runs in ${\displaystyle O(N)}$ time.
set-nth(n:Integer, new-value:item-type)
Assigns a new value to the nth element in the list, counting from 0. Has a default implementation. Runs in ${\displaystyle O(N)}$ time.

Bidirectional List Iterator<item-type> ADT

get-value():item-type
Returns the value of the list element that this iterator refers to. Undefined if the iterator is past-the-end.
set-value(new-value:item-type)
Assigns a new value to the list element that this iterator refers to. Undefined if the iterator is past-the-end.
move-next()
Makes this iterator refer to the next element in the list. Undefined if the iterator is past-the-end.
move-previous()
Makes this iterator refer to the previous element in the list. Undefined if the iterator refers to the first list element.
equal(other-iter:List Iterator<item-type>):Boolean
True iff the other iterator refers to the same list element as this iterator.

All operations run in ${\displaystyle O(1)}$ time.

Doubly Linked List Implementation

 To do: Explain this: It is part of linked lists that can show the connectivity between the list.

Vector Implementation

The vector we've already seen has a perfectly adequate implementation to be a Bidirectional List. All we need to do is add the extra member functions to it and its iterator; the old ones don't have to change.

type Vector<item-type>
... # already-existing data and methods


Implement this in terms of the original insert-after() method. After that runs, we have to adjust iter's index so that it still refers to the same element.

  method insert(iter:Bidirectional List Iterator<item-type>, new-item:item-type)
insert-after(new Vector-Iterator(iter.array, iter.index-1))
iter.move-next()
end method


Also implement this on in terms of an old function. After remove-after() runs, the index will already be correct.

  method remove(iter:Bidirectional List Iterator<item-type>)
remove-after(new Vector-Iterator(iter.array, iter.index-1))
end method
end type


 To do: Refactor useful information from below into above following outline from talk page: Common list operations & example set(pos, val), get(pos), remove(pos), append(val) [Perhaps discuss operations on Nodes, versus operations on the List itself: example, Nodes have a next operation, but the List itself has a pointer to the head and tail node, and an integer for the number of elements. This view would work well in both the Lisp and OO worlds.] Doubley linked list Vectors (resizeable arrays) 

In order to choose the correct data structure for the job, we need to have some idea of what we're going to *do* with the data.

• Do we know that we'll never have more than 100 pieces of data at any one time, or do we need to occasionally handle gigabytes of data ?
• How will we read the data out ? Always in chronological order ? Always sorted by name ? Randomly accessed by record number ?
• Will we always add/delete data to the end or to the beginning ? Or will we be doing a lot of insertions and deletions in the middle ?

We must strike a balance between the various requirements. If we need to frequently read data out in 3 different ways, pick a data structure that allows us to do all 3 things not-too-slowly. Don't pick some data structure that's unbearably slow for *one* way, no matter how blazingly fast it is for the other ways.

Often the shortest, simplest programming solution for some task will use a linear (1D) array.

If we keep our data as an ADT, that makes it easier to temporarily switch to some other underlying data structure, and objectively measure whether it's faster or slower.

For the most part, an advantage of an array is a disadvantage of a linked-list, and vice versa.

1. Index - Fast access to every element in the array using an index [], not so with linked list where elements in beginning must be traversed to your desired element.
2. Faster - In general, It is faster to access an element in an array than accessing an element in a linked-list.
1. Resize - Can easily resize the link-list by adding elements without affecting the majority of the other elements in the link-list.
2. Insertion - Can easily insert an element in the middle of a linked-list, (the element is created and then you code pointers to link this element to the other element(s) in the link-list).

Side-note: - How to insert an element in the middle of an array. If an array is not full, you take all the elements after the spot or index in the array you want to insert, and move them forward by 1, then insert your element. If the array is already full and you want to insert an element, you would have to, in a sense, 'resize the array.' A new array would have to be made one size larger than the original array to insert your element, then all the elements of the original array are copied to the new array taking into consideration the spot or index to insert your element, then insert your element.

 To do: queue implemented as an array: circular and fixed-sized

Stacks and Queues

Stacks

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. The basic concept can be illustrated by thinking of your data set as a stack of plates or books where you can only take the top item off the stack in order to remove things from it. This structure is used all throughout programming.

The basic implementation of a stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data, since as we will see there are various variations of stack implementations.

There are basically three operations that can be performed on stacks . They are 1) inserting an item into a stack (push). 2) deleting an item from the stack (pop). 3) displaying the contents of the stack(pip).

 Note: Depending on the language and implementation the data structure may share the name with an abstract data type that support all of the data structure characteristics.

Below are some of operations a stack data type normally supports:

Stack<item-type> Operations

push(new-item:item-type)
Adds an item onto the stack.
top():item-type
Returns the last item pushed onto the stack.
pop()
Removes the most-recently-pushed item from the stack.
is-empty():Boolean
True if no more items can be popped and there is no top item.
is-full():Boolean
True if no more items can be pushed.
get-size():Integer
Returns the number of elements on the stack.

All operations except get-size() can be performed in ${\displaystyle O(1)}$ time. get-size() runs in at worst ${\displaystyle O(N).}$

The basic linked list implementation is one of the easiest linked list implementations you can do. Structurally it is a linked list.

type Stack<item_type>
data list:Singly Linked List<item_type>

constructor()
list := new Singly-Linked-List()
end constructor


Most operations are implemented by passing them through to the underlying linked list. When you want to push something onto the list, you simply add it to the front of the linked list. The previous top is then "next" from the item being added and the list's front pointer points to the new item.

  method push(new_item:item_type)
list.prepend(new_item)
end method


To look at the top item, you just examine the first item in the linked list.

  method top():item_type
return list.get-begin().get-value()
end method


When you want to pop something off the list, simply remove the first item from the linked list.

  method pop()
list.remove-first()
end method


A check for emptiness is easy. Just check if the list is empty.

  method is-empty():Boolean
return list.is-empty()
end method


A check for full is simple. Linked lists are considered to be limitless in size.

  method is-full():Boolean
return False
end method


A check for the size is again passed through to the list.

  method get-size():Integer
return list.get-size()
end method
end type


A real Stack implementation in a published library would probably re-implement the linked list in order to squeeze the last bit of performance out of the implementation by leaving out unneeded functionality. The above implementation gives you the ideas involved, and any optimization you need can be accomplished by inlining the linked list code.

Performance Analysis

In a linked list, accessing the first element is an ${\displaystyle O(1)}$ operation because the list contains a pointer that checks for empty/fullness as done here are also ${\displaystyle O(1)}$. depending on what time/space tradeoff is made. Most of the time, users of a Stack do not use the getSize() operation, and so a bit of space can be saved by not optimizing it.

Since all operations are at the top of the stack, the array implementation is now much, much better.

  public class StackArray implements Stack
{
protected int top;
protected Object[] data;
...
}


The array implementation keeps the bottom of the stack at the beginning of the array. It grows toward the end of the array. The only problem is if you attempt to push an element when the array is full. If so

   Assert.pre(!isFull(),"Stack is not full.");


will fail, raising an exception. Thus it makes more sense to implement with Vector (see StackVector) to allow unbounded growth (at cost of occasional O(n) delays).

Complexity:

All operations are O(1) with exception of occasional push and clear, which should replace all entries by null in order to let them be garbage-collected. Array implementation does not replace null entries. The Vector implementation does...

Applications of Stacks

Stack of books

Using stacks, we can solve many applications, some of which are listed below.

Converting a decimal number into a binary number

The logic for transforming a decimal number into a binary number is as follows:

    * Read a number
* Iteration (while number is greater than zero)
1. Find out the remainder after dividing the number by 2
2. Print the remainder
3. Divide the number by 2
* End the iteration


However, there is a problem with this logic. Suppose the number, whose binary form we want to find is 23. Using this logic, we get the result as 11101, instead of getting 10111.

To solve this problem, we use a stack. We make use of the LIFO property of the stack. Initially we push the binary digit formed into the stack, instead of printing it directly. After the entire digit has been converted into the binary form, we pop one digit at a time from the stack and print it. Therefore we get the decimal number is converted into its proper binary form.

Algorithm:

   1. Create a stack
2. Enter a decimal number, which has to be converted into its equivalent binary form.
3. iteration1 (while number > 0)
3.1 digit = number % 2
3.2 Push digit into the stack
3.3 If the stack is full
3.3.1 Print an error
3.3.2 Stop the algorithm
3.4 End the if condition
3.5 Divide the number by 2
4. End iteration1

5. iteration2 (while stack is not empty)
5.1 Pop digit from the stack
5.2 Print the digit
6. End iteration2
7. STOP


Towers of Hanoi

Towers of Hanoi

One of the most interesting applications of stacks can be found in solving a puzzle called Tower of Hanoi. According to an old Brahmin story, the existence of the universe is calculated in terms of the time taken by a number of monks, who are working all the time, to move 64 disks from one pole to another. But there are some rules about how this should be done, which are:

1. You can move only one disk at a time.
2. For temporary storage, a third pole may be used.
3. You cannot place a disk of larger diameter on a disk of smaller diameter.[1]

Here we assume that A is first tower, B is second tower & C is third tower.

Towers of Hanoi step 1
Towers of Hanoi step 2
Towers of Hanoi step 3

Towers of Hanoi step 4

Tower of Hanoi

Output : (when there are 3 disks)

Let 1 be the smallest disk, 2 be the disk of medium size and 3 be the largest disk.

Move disk From peg To peg
1 A C
2 A B
1 C B
3 A C
1 B A
2 B C
1 A C

Output : (when there are 4 disks)

Move disk From peg To peg
1 A B
2 A C
1 B C
3 A B
1 C A
2 C B
1 A B
4 A C
1 B C
2 B A
1 C A
3 B C
1 A B
2 A C
1 B C

The C++ code for this solution can be implemented in two ways:

First Implementation (Without using Stacks)

Here we assume that A is first tower, B is second tower & C is third tower. (B is the intermediate)

void TowersofHanoi(int n, int a, int b, int c)
{
//Move top n disks from tower a to tower b, use tower c for intermediate storage.
if(n > 0)
{
TowersofHanoi(n-1, a, c, b);   //recursion
cout << " Move top disk from tower " << a << " to tower " << b << endl ;
//Move n-1 disks from intermediate(b) to the source(a) back
TowersofHanoi(n-1, c, b, a);   //recursion
}
}


[2]

Second Implementation (Using Stacks)
// Global variable , tower [1:3] are three towers
arrayStack<int> tower[4];
void TowerofHanoi(int n)
{
// Preprocessor for moveAndShow.
for (int d = n; d > 0; d--)        //initialize
tower[1].push(d);              //add disk d to tower 1
moveAndShow(n, 1, 2, 3);           /*move n disks from tower 1 to tower 3 using
tower 2 as intermediate tower*/
}

void moveAndShow(int n, int a, int b, int c)
{
// Move the top n disks from tower a to tower b showing states.
// Use tower c for intermediate storage.
if(n > 0)
{
moveAndShow(n-1, a, c, b);     //recursion
int d = tower[x].top();        //move a disc from top of tower x to top of
tower[x].pop();                //tower y
tower[y].push(d);
showState();                   //show state of 3 towers
moveAndShow(n-1, c, b, a);     //recursion
}
}


However complexity for above written implementations is O(${\displaystyle 2^{n}}$). So it's obvious that problem can only be solved for small values of n (generally n <= 30). In case of the monks, the number of turns taken to transfer 64 disks, by following the above rules, will be 18,446,744,073,709,551,615; which will surely take a lot of time!!

[1]

[2]

Expression evaluation and syntax parsing

Calculators employing reverse Polish notation use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form may be accomplished using a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context-free languages allowing them to be parsed with stack based machines.

Evaluation of an Infix Expression that is Fully Parenthesized

Input: (((2 * 5) - (1 * 2)) / (11 - 9))

Output: 4

Analysis: Five types of input characters

  * Opening bracket
* Numbers
* Operators
* Closing bracket
* New line character


Data structure requirement: A character stack

Algorithm

  1. Read one input character
2. Actions at end of each input
Opening brackets              (2.1)  Push into stack and then Go to step (1)
Number                        (2.2)  Push into stack and then Go to step (1)
Operator                      (2.3)  Push into stack and then Go to step (1)
Closing brackets              (2.4)  Pop it from character stack
(2.4.1) if it is opening bracket, then discard it, Go to step (1)
(2.4.2) Pop is used three times
The first popped element is assigned to op2
The second popped element is assigned to op
The third popped element is assigned to op1
Evaluate op1 op op2
Convert the result into character and
push into the stack
Go to step (2.4)
New line character            (2.5)  Pop from stack and print the answer
STOP


Result: The evaluation of the fully parenthesized infix expression is printed on the monitor as follows:

Input String: (((2 * 5) - (1 * 2)) / (11 - 9))

Input Symbol Stack (from bottom to top) Operation
( (
( ( (
( ( ( (
2 ( ( ( 2
* ( ( ( 2 *
5 ( ( ( 2 * 5
) ( ( 10 2 * 5 = 10 and push
- ( ( 10 -
( ( ( 10 - (
1 ( ( 10 - ( 1
* ( ( 10 - ( 1 *
2 ( ( 10 - ( 1 * 2
) ( ( 10 - 2 1 * 2 = 2 & Push
) ( 8 10 - 2 = 8 & Push
/ ( 8 /
( ( 8 / (
11 ( 8 / ( 11
- ( 8 / ( 11 -
9 ( 8 / ( 11 - 9
) ( 8 / 2 11 - 9 = 2 & Push
) 4 8 / 2 = 4 & Push
New line Empty Pop & Print

C Program

int main (int argc, char *argv[])
{
struct ch *charactop;
struct integer *integertop;
char rd, op;
int i = 0, op1, op2;
charactop = cclearstack();
integertop = iclearstack();
while(1)
{
rd = argv[1][i++];
switch(rd)
{
case '+':
case '-':
case '/':
case '*':
case '(': charactop = cpush(charactop, rd);
break;
case ')': integertop = ipop (integertop, &op1);
charactop = cpop (charactop, &op);
while(op != '(')
{
integertop = ipush (integertop, eval(op, op1, op2);
charactop = cpop (charactop, &op);
if (op != '(')
{
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
}
}
break;
case '\0': while (!= cemptystack(charactop))
{
charactop = cpop(charactop, &op);
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
integertop = ipush(integertop, eval(op, op1, op2);
}
integertop = ipop(integertop, &op1);
printf("\n The final solution is: %d", op1);
return 0;
default: integertop = ipush(integertop, rd - '0');
}
}
}

int eval(char op, int op1, int op2)
{
switch (op)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '/': return op1 / op2;
case '*': return op1 * op2;
}
}


Output of the program:

Input entered at the command line: (((2 * 5) - (1 * 2) / (11 - 9)) [3]

Evaluation of Infix Expression which is not fully parenthesized

Input: (2 * 5 - 1 * 2) / (11 - 9)

Output: 4

Analysis: There are five types of input characters which are:

               * Opening brackets
* Numbers
* Operators
* Closing brackets
* New line character (\n)


We do not know what to do if an operator is read as an input character. By implementing the priority rule for operators, we have a solution to this problem.

The Priority rule we should perform comparative priority check if an operator is read, and then push it. If the stack top contains an operator of prioirty higher than or equal to the priority of the input operator, then we pop it and print it. We keep on perforrming the prioirty check until the top of stack either contains an operator of lower priority or if it does not contain an operator.

Data Structure Requirement for this problem: A character stack and an integer stack

Algorithm:

   1. Read an input character
2. Actions that will be performed at the end of each input
Opening brackets              (2.1)  Push it into stack and then Go to step (1)
Digit                         (2.2)  Push into stack, Go to step (1)
Operator                      (2.3)  Do the comparative priority check
(2.3.1) if the character stack's top contains an operator with equal
or higher priority, then pop it into op
Pop a number from integer stack into op2
Pop another number from integer stack into op1
Calculate op1 op op2 and push the result into the integer
stack
Closing brackets              (2.4)  Pop from the character stack
(2.4.1) if it is an opening bracket, then discard it and Go to
step (1)
(2.4.2) To op, assign the popped element
Pop a number from integer stack and assign it op2
Pop another number from integer stack and assign it
to op1
Calculate op1 op op2 and push the result into the integer
stack
Convert into character and push into stack
Go to the step (2.4)
New line character            (2.5)  Print the result after popping from the stack
STOP


Result: The evaluation of an infix expression that is not fully parenthesized is printed as follows:

Input String: (2 * 5 - 1 * 2) / (11 - 9)

Input Symbol Character Stack (from bottom to top) Integer Stack (from bottom to top) Operation performed
( (
2 ( 2
* ( * Push as * has higher priority
5 ( * 2 5
- ( * Since '-' has less priority, we do 2 * 5 = 10
( - 10 We push 10 and then push '-'
1 ( - 10 1
* ( - * 10 1 Push * as it has higher priority
2 ( - * 10 1 2
) ( - 10 2 Perform 1 * 2 = 2 and push it
( 8 Pop - and 10 - 2 = 8 and push, Pop (
/ / 8
( / ( 8
11 / ( 8 11
- / ( - 8 11
9 / ( - 8 11 9
) / 8 2 Perform 11 - 9 = 2 and push it
New line 4 Perform 8 / 2 = 4 and push it
4 Print the output, which is 4

C Program

int main (int argc, char *argv[])
{
struct ch *charactop;
struct integer *integertop;
char rd, op;
int i = 0, op1, op2;
charactop = cclearstack();
integertop = iclearstack();
while(1)
{
rd = argv[1][i++];
switch(rd)
{
case '+':
case '-':
case '/':
case '*': while ((charactop->data != '(') && (!cemptystack(charactop)))
{
if(priority(rd) > (priority(charactop->data))
break;
else
{
charactop = cpop(charactop, &op);
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
integertop = ipush(integertop, eval(op, op1, op2);
}
}
charactop = cpush(charactop, rd);
break;
case '(': charactop = cpush(charactop, rd);
break;
case ')': integertop = ipop (integertop, &op2);
integertop = ipop (integertop, &op1);
charactop = cpop (charactop, &op);
while(op != '(')
{
integertop = ipush (integertop, eval(op, op1, op2);
charactop = cpop (charactop, &op);
if (op != '(')
{
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
}
}
break;
case '\0': while (!= cemptystack(charactop))
{
charactop = cpop(charactop, &op);
integertop = ipop(integertop, &op2);
integertop = ipop(integertop, &op1);
integertop = ipush(integertop, eval(op, op1, op2);
}
integertop = ipop(integertop, &op1);
printf("\n The final solution is: %d", op1);
return 0;
default: integertop = ipush(integertop, rd - '0');
}
}
}

int eval(char op, int op1, int op2)
{
switch (op)
{
case '+': return op1 + op2;
case '-': return op1 - op2;
case '/': return op1 / op2;
case '*': return op1 * op2;
}
}

int priority (char op)
{
switch(op)
{
case '^':
case '$': return 3; case '*': case '/': return 2; case '+': case '-': return 1; } }  Output of the program: Input entered at the command line: (2 * 5 - 1 * 2) / (11 - 9) Output: 4 [3] Evaluation of Prefix Expression Input: x + 6 * ( y + z ) ^ 3 Output:' 4 Analysis: There are three types of input characters  * Numbers * Operators * New line character (\n)  Data structure requirement: A character stack and an integer stack Algorithm:  1. Read one character input at a time and keep pushing it into the character stack until the new line character is reached 2. Perform pop from the character stack. If the stack is empty, go to step (3) Number (2.1) Push in to the integer stack and then go to step (1) Operator (2.2) Assign the operator to op Pop a number from integer stack and assign it to op1 Pop another number from integer stack and assign it to op2 Calculate op1 op op2 and push the output into the integer stack. Go to step (2) 3. Pop the result from the integer stack and display the result  Result: The evaluation of prefix expression is printed as follows: Input String: / - * 2 5 * 1 2 - 11 9 Input Symbol Character Stack (from bottom to top) Integer Stack (from bottom to top) Operation performed / / - / * / - * 2 / - * 2 5 / - * 2 5 * / - * 2 5 * 1 / - * 2 5 * 1 2 / - * 2 5 * 1 2 - / - * 2 5 * 1 2 - 11 / - * 2 5 * 1 2 - 11 9 / - * 2 5 * 1 2 - 11 9 \n / - * 2 5 * 1 2 - 11 9 / - * 2 5 * 1 2 - 9 11 / - * 2 5 * 1 2 2 11 - 9 = 2 / - * 2 5 * 1 2 2 / - * 2 5 * 2 2 1 / - * 2 5 2 2 1 * 2 = 2 / - * 2 2 2 5 / - * 2 2 5 2 / - 2 2 10 5 * 2 = 10 / 2 8 10 - 2 = 8 Stack is empty 4 8 / 2 = 4 Stack is empty Print 4 C Program int main (int argc, char *argv[]) { struct ch *charactop = NULL; struct integer *integertop = NULL; char rd, op; int i = 0, op1, op2; charactop = cclearstack(); integertop = iclearstack(); rd = argv[1][i]; while(rd != '\0') { charactop = cpush(charactop, rd); rd = argv[1][i++]; } while(!emptystack(charactop)) { charactop = cpop(charactop, rd); switch(rd) { case '+': case '-': case '/': case '*': op = rd; integertop = ipop(integertop, &op2); integertop = ipop(integertop, &op1); integertop = ipush(integertop, eval(op, op1, op2)); break; default: integertop = ipush(integertop, rd - '0'); } } } int eval(char op, int op1, int op2) { switch (op) { case '+': return op1 + op2; case '-': return op1 - op2; case '/': return op1 / op2; case '*': return op1 * op2; } } int priority (char op) { switch(op) { case '^': case '$':  return 3;
case '*':
case '/':  return 2;
case '+':
case '-': return 1;
}
}


Output of the program:

Input entered at the command line: / - * 2 5 * 1 2 - 11 9

Output: 4 [3]

Conversion of an Infix expression that is fully parenthesized into a Postfix expression

Input: (((8 + 1) - (7 - 4)) / (11 - 9))

Output: 8 1 + 7 4 - - 11 9 - /

Analysis: There are five types of input characters which are:

               * Opening brackets
* Numbers
* Operators
* Closing brackets
* New line character (\n)


Requirement: A character stack

Algorithm:

   1. Read an character input
2. Actions to be performed at end of each input
Opening brackets              (2.1)  Push into stack and then Go to step (1)
Number                        (2.2)  Print and then Go to step (1)
Operator                      (2.3)  Push into stack and then Go to step (1)
Closing brackets              (2.4)  Pop it from the stack
(2.4.1) If it is an operator, print it, Go to step (1)
(2.4.2) If the popped element is an opening bracket,
discard it and go to step (1)
New line character            (2.5)  STOP


Therefore, the final output after conversion of an infix expression to a postfix expression is as follows:

Input Operation Stack (after op) Output on monitor
( (2.1) Push operand into stack (
( (2.1) Push operand into stack ( (
( (2.1) Push operand into stack ( ( (
8 (2.2) Print it 8
+ (2.3) Push operator into stack ( ( ( + 8
1 (2.2) Print it 8 1
) (2.4) Pop from the stack: Since popped element is '+' print it ( ( ( 8 1 +
(2.4) Pop from the stack: Since popped element is '(' we ignore it and read next character ( ( 8 1 +
- (2.3) Push operator into stack ( ( -
( (2.1) Push operand into stack ( ( - (
7 (2.2) Print it 8 1 + 7
- (2.3) Push the operator in the stack ( ( - ( -
4 (2.2) Print it 8 1 + 7 4
) (2.4) Pop from the stack: Since popped element is '-' print it ( ( - ( 8 1 + 7 4 -
(2.4) Pop from the stack: Since popped element is '(' we ignore it and read next character ( ( -
) (2.4) Pop from the stack: Since popped element is '-' print it ( ( 8 1 + 7 4 - -
(2.4) Pop from the stack: Since popped element is '(' we ignore it and read next character (
/ (2.3) Push the operand into the stack ( /
( (2.1) Push into the stack ( / (
11 (2.2) Print it 8 1 + 7 4 - - 11
- (2.3) Push the operand into the stack ( / ( -
9 (2.2) Print it 8 1 + 7 4 - - 11 9
) (2.4) Pop from the stack: Since popped element is '-' print it ( / ( 8 1 + 7 4 - - 11 9 -
(2.4) Pop from the stack: Since popped element is '(' we ignore it and read next character ( /
) (2.4) Pop from the stack: Since popped element is '/' print it ( 8 1 + 7 4 - - 11 9 - /
(2.4) Pop from the stack: Since popped element is '(' we ignore it and read next character Stack is empty
New line character (2.5) STOP

Problem Description

It's a very nice application of stacks. Consider that a freight train has n railroad cars. Each to be left at different station. They're numbered 1 through n & freight train visits these stations in order n through 1. Obviously, the railroad cars are labeled by their destination.To facilitate removal of the cars from the train, we must rearrange them in ascending order of their number(i.e. 1 through n). When cars are in this order , they can be detached at each station. We rearrange cars at a shunting yard that has input track, output track & k holding tracks between input & output tracks(i.e. holding track).

Solution Strategy

To rearrange cars, we examine the cars on the the input from front to back. If the car being examined is next one in the output arrangement , we move it directly to output track. If not , we move it to the holding track & leave it there until it's time to place it to the output track. The holding tracks operate in a LIFO manner as the cars enter & leave these tracks from top. When rearranging cars only following moves are permitted:

• A car may be moved from front (i.e. right end) of the input track to the top of one of the holding tracks or to the left end of the output track.
• A car may be moved from the top of holding track to left end of the output track.

The figure shows a shunting yard with k = 3, holding tracks H1, H2 & H3, also n = 9. The n cars of freight train begin in the input track & are to end up in the output track in order 1 through n from right to left. The cars initially are in the order 5,8,1,7,4,2,9,6,3 from back to front. Later cars are rearranged in desired order.

A Three Track Example
• Consider the input arrangement from figure , here we note that the car 3 is at the front, so it can't be output yet, as it to be preceded by cars 1 & 2. So car 3 is detached & moved to holding track H1.
• The next car 6 can't be output & it is moved to holding track H2. Because we have to output car 3 before car 6 & this will not possible if we move car 6 to holding track H1.
• Now it's obvious that we move car 9 to H3.

The requirement of rearrangement of cars on any holding track is that the cars should be preferred to arrange in ascending order from top to bottom.

• So car 2 is now moved to holding track H1 so that it satisfies the previous statement. If we move car 2 to H2 or H3, then we've no place to move cars 4,5,7,8.The least restrictions on future car placement arise when the new car λ is moved to the holding track that has a car at its top with smallest label Ψ such that λ < Ψ. We may call it an assignment rule to decide whether a particular car belongs to a specific holding track.
• When car 4 is considered, there are three places to move the car H1,H2,H3. The top of these tracks are 2,6,9.So using above mentioned Assignment rule, we move car 4 to H2.
• The car 7 is moved to H3.
• The next car 1 has the least label, so it's moved to output track.
• Now it's time for car 2 & 3 to output which are from H1(in short all the cars from H1 are appended to car 1 on output track).

The car 4 is moved to output track. No other cars can be moved to output track at this time.

• The next car 8 is moved to holding track H1.
• Car 5 is output from input track. Car 6 is moved to output track from H2, so is the 7 from H3,8 from H1 & 9 from H3.

Quicksort

Sorting means arranging a group of elements in a particular order. Be it ascending or descending, by cardinality or alphabetical order or variations thereof. The resulting ordering possibilities will only be limited by the type of the source elements.

Quicksort is an algorithm of the divide and conquer type. In this method, to sort a set of numbers, we reduce it to two smaller sets, and then sort these smaller sets.

This can be explained with the help of the following example:

Suppose A is a list of the following numbers:

In the reduction step, we find the final position of one of the numbers. In this case, let us assume that we have to find the final position of 48, which is the first number in the list.

To accomplish this, we adopt the following method. Begin with the last number, and move from right to left. Compare each number with 48. If the number is smaller than 48, we stop at that number and swap it with 48.

In our case, the number is 24. Hence, we swap 24 and 48.

The numbers 96 and 72 to the right of 48, are greater than 48. Now beginning with 24, scan the numbers in the opposite direction, that is from left to right. Compare every number with 48 until you find a number that is greater than 48.

In this case, it is 60. Therefore we swap 48 and 60.

Note that the numbers 12, 24 and 36 to the left of 48 are all smaller than 48. Now, start scanning numbers from 60, in the right to left direction. As soon as you find lesser number, swap it with 48.

In this case, it is 44. Swap it with 48. The final result is:

Now, beginning with 44, scan the list from left to right, until you find a number greater than 48.

Such a number is 84. Swap it with 48. The final result is:

Now, beginning with 84, traverse the list from right to left, until you reach a number lesser than 48. We do not find such a number before reaching 48. This means that all the numbers in the list have been scanned and compared with 48. Also, we notice that all numbers less than 48 are to the left of it, and all numbers greater than 48, are to its right.

The final partitions look as follows:

Therefore, 48 has been placed in its proper position and now our task is reduced to sorting the two partitions. This above step of creating partitions can be repeated with every partition containing 2 or more elements. As we can process only a single partition at a time, we should be able to keep track of the other partitions, for future processing.

This is done by using two stacks called LOWERBOUND and UPPERBOUND, to temporarily store these partitions. The addresses of the first and last elements of the partitions are pushed into the LOWERBOUND and UPPERBOUND stacks respectively. Now, the above reduction step is applied to the partitions only after its boundary values are popped from the stack.

We can understand this from the following example:

Take the above list A with 12 elements. The algorithm starts by pushing the boundary values of A, that is 1 and 12 into the LOWERBOUND and UPPERBOUND stacks respectively. Therefore the stacks look as follows:

    LOWERBOUND:  1                   UPPERBOUND:  12


To perform the reduction step, the values of the stack top are popped from the stack. Therefore, both the stacks become empty.

    LOWERBOUND:  {empty}                UPPERBOUND: {empty}


Now, the reduction step causes 48 to be fixed to the 5th position and creates two partitions, one from position 1 to 4 and the other from position 6 to 12. Hence, the values 1 and 6 are pushed into the LOWERBOUND stack and 4 and 12 are pushed into the UPPERBOUND stack.

    LOWERBOUND:  1, 6                   UPPERBOUND: 4, 12


For applying the reduction step again, the values at the stack top are popped. Therefore, the values 6 and 12 are popped. Therefore the stacks look like:

    LOWERBOUND:  1                      UPPERBOUND: 4


The reduction step is now applied to the second partition, that is from the 6th to 12th element.

After the reduction step, 98 is fixed in the 11th position. So, the second partition has only one element. Therefore, we push the upper and lower boundary values of the first partition onto the stack. So, the stacks are as follows:

    LOWERBOUND:  1, 6                   UPPERBOUND:  4, 10


The processing proceeds in the following way and ends when the stacks do not contain any upper and lower bounds of the partition to be processed, and the list gets sorted.

The Stock Span Problem

The Stockspan Problem

In the stock span problem, we will solve a financial problem with the help of stacks.

Suppose, for a stock, we have a series of n daily price quotes, the span of the stock's price on a particular day is defined as the maximum number of consecutive days for which the price of the stock on the current day is less than or equal to its price on that day.

An algorithm which has Quadratic Time Complexity

Input: An array P with n elements

Output: An array S of n elements such that P[i] is the largest integer k such that k <= i + 1 and P[y] <= P[i] for j = i - k + 1,.....,i

Algorithm:

       1. Initialize an array P which contains the daily prices of the stocks
2. Initialize an array S which will store the span of the stock
3. for i = 0 to i = n - 1
3.1 Initialize k to zero
3.2 Done with a false condition
3.3 repeat
3.3.1 if ( P[i - k] <= P[i)] then
Increment k by 1
3.3.2 else
Done with true condition
3.4 Till (k > i) or done with processing
Assign value of k to S[i] to get the span of the stock
4. Return array S


Now, analyzing this algorithm for running time, we observe:

• We have initialized the array S at the beginning and returned it at the end. This is a constant time operation, hence takes O(n) time
• The repeat loop is nested within the for loop. The for loop, whose counter is i is executed n times. The statements which are not in the repeat loop, but in the for loop are executed n times. Therefore these statements and the incrementing and condition testing of i take O(n) time.
• In repetition of i for the outer for loop, the body of the inner repeat loop is executed maximum i + 1 times. In the worst case, element S[i] is greater than all the previous elements. So, testing for the if condition, the statement after that, as well as testing the until condition, will be performed i + 1 times during iteration i for the outer for loop. Hence, the total time taken by the inner loop is O(n(n + 1)/2), which is O(${\displaystyle n^{2}}$)

The running time of all these steps is calculated by adding the time taken by all these three steps. The first two terms are O(${\displaystyle n}$) while the last term is O(${\displaystyle n^{2}}$). Therefore the total running time of the algorithm is O(${\displaystyle n^{2}}$).

An algorithm that has Linear Time Complexity

In order to calculate the span more efficiently, we see that the span on a particular day can be easily calculated if we know the closest day before i , such that the price of the stocks on that day was higher than the price of the stocks on the present day. If there exists such a day, we can represent it by h(i) and initialize h(i) to be -1.

Therefore the span of a particular day is given by the formula, s = i - h(i).

To implement this logic, we use a stack as an abstract data type to store the days i, h(i), h(h(i)) and so on. When we go from day i-1 to i, we pop the days when the price of the stock was less than or equal to p(i) and then push the value of day i back into the stack.

Here, we assume that the stack is implemented by operations that take O(1) that is constant time. The algorithm is as follows:

Input: An array P with n elements and an empty stack N

Output: An array S of n elements such that P[i] is the largest integer k such that k <= i + 1 and P[y] <= P[i] for j = i - k + 1,.....,i

Algorithm:

       1. Initialize an array P which contains the daily prices of the stocks
2. Initialize an array S which will store the span of the stock
3. for i = 0 to i = n - 1
3.1 Initialize k to zero
3.2 Done with a false condition
3.3 while not (Stack N is empty or done with processing)
3.3.1 if ( P[i] >= P[N.top())] then
Pop a value from stack N
3.3.2 else
Done with true condition
3.4 if Stack N is empty
3.4.1 Initialize h to -1
3.5 else
3.5.1 Initialize stack top to h
3.5.2 Put the value of h - i in S[i]
3.5.3 Push the value of i in N
4. Return array S


Now, analyzing this algorithm for running time, we observe:

• We have initialized the array S at the beginning and returned it at the end. This is a constant time operation, hence takes O(n) time
• The while loop is nested within the for loop. The for loop, whose counter is i is executed n times. The statements which are not in the repeat loop, but in the for loop are executed n times. Therefore these statements and the incrementing and condition testing of i take O(n) time.
• Now, observe the inner while loop during i repetitions of the for loop. The statement done with a true condition is done at most once, since it causes an exit from the loop. Let us say that t(i) is the number of times statement Pop a value from stack N is executed. So it becomes clear that while not (Stack N is empty or done with processing) is tested maximum t(i) + 1 times.
• Adding the running time of all the operations in the while loop, we get:

${\displaystyle \sum _{i=0}^{n-1}t(i)+1}$
• An element once popped from the stack N is never pushed back into it. Therefore,

${\displaystyle \sum _{i=1}^{n-1}t(i)}$

So, the running time of all the statements in the while loop is O(${\displaystyle n}$)

The running time of all the steps in the algorithm is calculated by adding the time taken by all these steps. The run time of each step is O(${\displaystyle n}$). Hence the running time complexity of this algorithm is O(${\displaystyle n}$).

Queues

A queue is a basic data structure that is used throughout programming. You can think of it as a line in a grocery store. The first one in the line is the first one to be served.Just like a queue.

A queue is also called a FIFO (First In First Out) to demonstrate the way it accesses data.

Queue<item-type> Operations

enqueue(new-item:item-type)
Adds an item onto the end of the queue.
front():item-type
Returns the item at the front of the queue.
dequeue()
Removes the item from the front of the queue.
is-empty():Boolean
True if no more items can be dequeued and there is no front item.
is-full():Boolean
True if no more items can be enqueued.
get-size():Integer
Returns the number of elements in the queue.

All operations except get-size() can be performed in ${\displaystyle O(1)}$ time. get-size() runs in at worst ${\displaystyle O(N).}$

The basic linked list implementation uses a singly-linked list with a tail pointer to keep track of the back of the queue.

type Queue<item_type>
data list:Singly Linked List<item_type>
data tail:List Iterator<item_type>

constructor()
list := new Singly-Linked-List()
tail := list.get-begin() # null
end constructor


When you want to enqueue something, you simply add it to the back of the item pointed to by the tail pointer. So the previous tail is considered next compared to the item being added and the tail pointer points to the new item. If the list was empty, this doesn't work, since the tail iterator doesn't refer to anything

 method enqueue(new_item:item_type)
if is-empty()
list.prepend(new_item)
tail := list.get-begin()
else
list.insert_after(new_item, tail)
tail.move-next()
end if
end method


The front item on the queue is just the one referred to by the linked list's head pointer

  method front():item_type
return list.get-begin().get-value()
end method


When you want to dequeue something off the list, simply point the head pointer to the previous from head item. The old head item is the one you removed of the list. If the list is now empty, we have to fix the tail iterator.

  method dequeue()
list.remove-first()
if is-empty()
tail := list.get-begin()
end if
end method


A check for emptiness is easy. Just check if the list is empty.

  method is-empty():Boolean
return list.is-empty()
end method


A check for full is simple. Linked lists are considered to be limitless in size.

  method is-full():Boolean
return False
end method


A check for the size is again passed through to the list.

  method get-size():Integer
return list.get-size()
end method
end type


Performance Analysis

In a linked list, accessing the first element is an ${\displaystyle O(1)}$ operation because the list contains a pointer directly to it. Therefore, enqueue, front, and dequeue are a quick ${\displaystyle O(1)}$ operations.

The checks for empty/fullness as done here are also ${\displaystyle O(1)}$.

The performance of getSize() depends on the performance of the corresponding operation in the linked list implementation. It could be either ${\displaystyle O(n)}$, or ${\displaystyle O(1)}$, depending on what time/space tradeoff is made. Most of the time, users of a Queue do not use the getSize() operation, and so a bit of space can be saved by not optimizing it.

Priority Queue Implementation

 To do: Discuss priority queues and implementations including sorted lists and various heaps.

Deques

A Deque is a homogeneous list of elements in which insertions and deletion operations are performed on both the ends.
Because of this property it is known as double ended queue i.e. Deque
Deque has two types:

1. Input restricted queue: It allows insertion at only one end
2. Output restricted queue: It allows deletion at only one end

References

1. a b Dromey, R.G. How to Solve it by Computer. Prentice Hall of India.
2. a b Data structures, Algorithms and Applications in C++ by Sartaj Sahni
3. a b c Gopal, Arpita. Magnifying Data Structures. PHI.

Trees

A tree is a non-empty set one element of which is designated the root of the tree while the remaining elements are partitioned into non-empty sets each of which is a subtree of the root.

Tree nodes have many useful properties. The depth of a node is the length of the path (or the number of edges) from the root to that node. The height of a node is the longest path from that node to its leaves. The height of a tree is the height of the root. A leaf node has no children -- its only path is up to its parent.

See the axiomatic development of trees and its consequences for more information.

Types of trees:

Binary: Each node has zero, one, or two children. This assertion makes many tree operations simple and efficient.

Binary Search: A binary tree where any left child node has a value less than its parent node and any right child node has a value greater than or equal to that of its parent node.

Traversal

Many problems require we visit the nodes of a tree in a systematic way: tasks such as counting how many nodes exist or finding the maximum element. Three different methods are possible for binary trees: preorder, postorder, and in-order, which all do the same three things: recursively traverse both the left and right subtrees and visit the current node. The difference is when the algorithm visits the current node:

preorder: Current node, left subtree, right subtree (DLR)

postorder: Left subtree, right subtree, current node (LRD)

in-order: Left subtree, current node, right subtree (LDR)

levelorder: Level by level, from left to right, starting from the root node.

* Visit means performing some operation involving the current node of a tree, like incrementing a counter or checking if the value of the current node is greater than any other recorded.

Sample implementations for Tree Traversal

preorder(node)
visit(node)
if node.left  ≠ null then preorder(node.left)
if node.right ≠ null then preorder(node.right)

inorder(node)
if node.left  ≠ null then inorder(node.left)
visit(node)
if node.right ≠ null then inorder(node.right)

postorder(node)
if node.left  ≠ null then postorder(node.left)
if node.right ≠ null then postorder(node.right)
visit(node)

levelorder(root)
queue<node> q
q.push(root)
while not q.empty do
node = q.pop
visit(node)
if node.left  ≠ null then q.push(node.left)
if node.right ≠ null then q.push(node.right)


For an algorithm that is less taxing on the stack, see Threaded Trees.

Examples of Tree Traversals

preorder:  50,30, 20, 40, 90, 100
inorder: 20,30,40,50, 90, 100


Balancing

When entries that are already sorted are stored in a tree, all new records will go the same route, and the tree will look more like a list (such a tree is called a degenerate tree). Therefore the tree needs balancing routines, making sure that under all branches are an equal number of records. This will keep searching in the tree at optimal speed. Specifically, if a tree with n nodes is a degenerate tree, the longest path through the tree will be n nodes; if it is a balanced tree, the longest path will be log n nodes.

Algorithms/Left_rotation: This shows how balancing is applied to establish a priority heap invariant in a Treap, a data structure which has the queueing performance of a heap, and the key lookup performance of a tree. A balancing operation can change the tree structure while maintaining another order, which is binary tree sort order. The binary tree order is left to right, with left nodes' keys less than right nodes' keys, whereas the priority order is up and down, with higher nodes' priorities greater than lower nodes' priorities. Alternatively, the priority can be viewed as another ordering key, except that finding a specific key is more involved.

The balancing operation can move nodes up and down a tree without affecting the left right ordering.

AVL: A balanced binary search tree according to the following specification: the heights of the two child subtrees of any node differ by at most one.

Red-Black Tree: A balanced binary search tree using a balancing algorithm based on colors assigned to a node, and the colors of nearby nodes.

AA Tree: A balanced tree, in fact a more restrictive variation of a red-black tree.

Binary Search Trees

A typical binary search tree looks like this:

Terms

Node Any item that is stored in the tree. Root The top item in the tree. (50 in the tree above) Child Node(s) under the current node. (20 and 40 are children of 30 in the tree above) Parent The node directly above the current node. (90 is the parent of 100 in the tree above) Leaf A node which has no children. (20 is a leaf in the tree above)

Searching through a binary search tree

To search for an item in a binary tree:

1. Start at the root node
2. If the item that you are searching for is less than the root node, move to the left child of the root node, if the item that you are searching for is more than the root node, move to the right child of the root node and if it is equal to the root node, then you have found the item that you are looking for.
3. Now check to see if the item that you are searching for is equal to, less than or more than the new node that you are on. Again if the item that you are searching for is less than the current node, move to the left child, and if the item that you are searching for is greater than the current node, move to the right child.
4. Repeat this process until you find the item that you are looking for or until the node does not have a child on the correct branch, in which case the tree doesn't contain the item which you are looking for.
Example

For example, to find the node 40...

1. The root node is 50, which is greater than 40, so you go to 50's left child.
2. 50's left child is 30, which is less than 40, so you next go to 30's right child.
3. 30's right child is 40, so you have found the item that you are looking for :)

.........

Adding an item to a binary search tree

1. To add an item, you first must search through the tree to find the position that you should put it in. You do this following the steps above.
2. When you reach a node which doesn't contain a child on the correct branch, add the new node there.

For example, to add the node 25...

1. The root node is 50, which is greater than 25, so you go to 50's left child.
2. 50's left child is 30, which is greater than 25, so you go to 30's left child.
3. 30's left child is 20, which is less than 25, so you go to 20's right child.
4. 20's right child doesn't exist, so you add 25 there :)

Deleting an item from a binary search tree

It is assumed that you have already found the node that you want to delete, using the search technique described above.

Case 1: The node you want to delete is a leaf

For example, to delete 40...

• Simply delete the node!
Case 2: The node you want to delete has one child
1. Directly connect the child of the node that you want to delete, to the parent of the node that you want to delete.

For example, to delete 90...

• Delete 90, then make 100 the child node of 50.
Case 3: The node you want to delete has two children

One non-standard way, is to rotate the node into a chosen subtree, and attempt to delete the key again from that subtree, recursively, until Case 1 or Case 2 occurs. This could unbalance a tree, so randomly choosing whether to right or left rotate may help.

The standard way is to pick either the left or right child, say the right, then get the right's leftmost descendent by following left ,starting from the right child, until the next left is null. Then remove this leftmost descendant of the right child, replacing it with its right sub-tree ( it has a left child of null). Then use the contents of this former leftmost descendant of the right child, as replacement for the key and value of the node being deleted , so that its values now are in the deleted node, the parent of the right child. This still maintains the key ordering for all nodes. Example java code is below in the treap example code.

The following examples use the standard algorithm, that is, the successor is the left-most node in the right subtree of the node to be deleted.

For example, to delete 30

1. The right node of the node which is being deleted is 40.
2. (From now on, we continually go to the left node until there isn't another one...) The first left node of 40, is 35.
3. 35 has no left node, therefore 35 is the successor!
4. 35 replaces 30, at the original right node, and the node with 35 is deleted, replacing it with the right sub-tree, which has the root node 37.
Case 1 of two-children case: The successor is the right child of the node being deleted
1. Directly move the child to the right of the node being deleted into the position of the node being deleted.
2. As the new node has no left children, you can connect the deleted node's left subtree's root as it's left child.

For example, to delete 30

1. replace the contents to be deleted (30), with the successor's contents( 40).
2. delete the successor node (contents 40), replacing it with its right subtree (head contents 45).
Case 2 of two-children case: The successor isn't the right child of the node being deleted

This is best shown with an example

To delete 30...

1. Replace the contents to be deleted (30) with the successor's contents (35).
2. replace the successor (35) with it's right subtree (37). There is no left subtree because the successor is leftmost.

Example extract of java code for binary tree delete operation

private Treap1<K, V>.TreapNode deleteNode(K k, Treap1<K, V>.TreapNode node, Deleted del) {

if (node == null) {
return null;
} else if (k.compareTo(node.k) < 0) {
node.left = deleteNode(k, node.left, del) ;
} else if (k.compareTo(node.k) > 0) {
node.right =  deleteNode(k, node.right, del);

// k.compareTo(node.k) == 0
} else if ( node.left == null ) {
del.success = true;
return node.right;
} else if ( node.right == null) {
del.success = true;
return  node.left;
} else  if (node.left !=null && node.right != null){
/*
//  non-standard method,
// left rotate and all delete on left subtree

TreapNode tmp = node.right;
node.right = node.right.left;
tmp.left = node;
node = tmp;
node.left = deleteNode(k , node.left, del);

*/

// more standard method ? doesn't disturb tree structure as much
// find leftmost descendant of the right child node and replace contents

TreapNode n2  = node.right;
TreapNode previous2 = null;
while (n2.left != null) {
previous2 = n2;
n2 = n2.left;
}

if (previous2 != null) {
previous2.left = n2.right;
//n2 has no parent link, orphaned
} else {
node.right = n2.right;
//n2 has no parent link, orphaned
}

node.k = n2.k;
node.val = n2.val;
del.success = true;
// once n2 out of scope, the orphaned node at n2 will be garbage collected,
}

return node;
}


Red-Black trees

A red-black tree is a self-balancing tree structure that applies a color to each of its nodes. The structure of a red-black tree must adhere to a set of rules which dictate how nodes of a certain color can be arranged. The application of these rules is performed when the tree is modified in some way, causing the rotation and recolouring of certain nodes when a new node is inserted or an old node is deleted. This keeps the red-black tree balanced, guaranteeing a search complexity of O(log n).

The rules that a red-black tree must adhere to are as follows:

1. Each node must be either red or black.
2. The root is always black.
3. All leaves within the tree are black (leaves do not contain data and can be modelled as null or nil references in most programming languages).
4. Every red node must have two black child nodes.
5. Every path from a given node to any of its descendant leaves must contain the same number of black nodes.

A red-black tree can be modelled as 2-3-4 tree , which is a sub-class of B tree (below). A black node with one red node can be seen as linked together as a 3-node , and a black node with 2 red child nodes can be seen as a 4-node.

4-nodes are split , producing a two node, and the middle node made red, which turns a parent of the middle node which has no red child from a 2-node to a 3-node, and turns a parent with one red child into a 4-node (but this doesn't occur with always left red nodes).

A in-line arrangement of two red nodes, is rotated into a parent with two red children, a 4-node, which is later split, as described before.

      A  right rotate            'split 4-node'   |red
red / \    -->        B           --->    B
B               red/ \red               / \
red / \               C   A               C   A
C   D                 /                   /
D                   D


An optimization mentioned by Sedgewick is that all right inserted red nodes are left rotated to become left red nodes, so that only inline left red nodes ever have to be rotated right before splitting. AA-trees (above) by Arne Anderson , described in a paper in 1993 , seem an earlier exposition of the simplification, however he suggested right-leaning 'red marking' instead of left leaning , as suggested by Sedgewick, but AA trees seem to have precedence over left leaning red black trees. It would be quite a shock if the Linux CFS scheduler was described in the future as 'AA based'.

In summary, red-black trees are a way of detecting two insertions into the same side, and levelling out the tree before things get worse . Two left sided insertions will be rotated, and the two right sided insertions, would look like two left sided insertions after left rotation to remove right leaning red nodes. Two balanced insertions for the same parent could result in a 4-node split without rotation, so the question arises as to whether a red black tree could be attacked with serial insertions of one sided triads of a < P < b , and then the next triad's P' < a.

Python illustrative code follows

RED = 1
BLACK = 0
class Node:
def __init__(self, k, v):
# all newly inserted node's are RED
self.color = RED
self.k = k
self.v = v
self.left = None
self.right = None

class RBTree:
def __init__(self):
self.root = None

def insert(self, k, v) :
self.root = self._insert(self.root, k,v)

def _insert(self,  n , k, v):
if n is None:
return Node(k,v)
if k < n.k :
n.left = self._insert(n.left, k , v)
elif k > n.k :
n.right = self._insert(n.right, k, v)
if n.right.color is RED:
#always on the left red's
#left rotate
tmp = n.right
n.right = tmp.left
tmp.left = n
n = tmp

#color rotation is actually a swap
tmpcolor = n.color
n.color = n.left.color
n.left.color = tmpcolor

if n.left <> None and n.left.left <> None and n.left.left.color == RED and n.left.color == RED:
# right rotate in-line reds
print "right rotate"
tmp = n.left
n.left = tmp.right
tmp.right = n
n = tmp

#color rotation is actually a swap
tmpcolor = n.color
n.color = n.right.color
n.right.color = tmpcolor

if n.left <> None: print n.left.color, n.color, n.right.color

#no need to test, because after right rotation, will need to split 3-node , as right rotation has
#brought red left grandchild to become left red child, and left red child is now red right child
#so there are two red children.

#if n.left <> None and n.right <> None and n.left.color == RED and n.right.color == RED:
print "split"
n.color = RED
n.left.color = BLACK
n.right.color = BLACK

return n

def find(self, k):
return self._find_rb(k, self.root)

def _find_rb(self, k, n):
if n is None:
return None
if k < n.k:
return self._find_rb( k, n.left)
if k > n. k:
return self._find_rb( k, n.right)
return n.v

def inorder(self):
self.inorder_visit(self.root, "O")

def inorder_visit(self, node,label=""):
if node is None: return
self.inorder_visit(node.left, label+"/L")
print label, "val=", node.v
self.inorder_visit(node.right, label+"/R")

def test1(N):
t = RBTree()
for i in xrange(0,N):
t.insert(i,i)

l = []
t.inorder()
for i in xrange(0,N):
x =t.find(i)
if x <> None:
l.append((x, i) )
print "found", len(l)

if __name__ == "__main__":
import random
test1(100000)
test1(1000)
test1(100)
test1(10)


B Trees

Executive Summary
• Whereas binary trees have nodes that have two children, with the left child and all of its descendants less than the "value" of the node, and the right child and all of its children more than the "value" of the node, a B-tree is a generalization of this.
• The generalization is that instead of one value, the node has a list of values, and the list is of size n ( n > 2 ). n is chosen to optimize storage , so that a node corresponds in size to a block for instance. This is in the days before ssd drives, but searching binary nodes stored on ssd ram would still be slower than searching ssd ram for a block of values, loading into normal ram and cpu cache, and searching the loaded list.
• At the start of the list, the left child of the first element of the list has a value less than the first element , and so do all its children. To the right of the first element, is a child which has values more than the first element's value, as do all of its children, but also less than the value of the second element. Induction can be used , and this holds so for the child between element 1 and 2, 2 and 3, ... so on until n-1 and nth node.
• To insert into a non-full B tree node, is to do a insertion into a sorted list.
• In a B+ tree, insertions can only be done in leaf nodes, and non-leaf nodes hold copies of a demarcating value between adjacent child nodes e.g. the left most value of an element's right child's list of nodes.
• Whenever a list becomes full e.g. there are n nodes, the node is "split", and this means making two new nodes, and passing the demarcating value upto the parent.

B Trees were described originally as generalizations of binary search trees , where a binary tree is a 2-node B-Tree, the 2 standing for two children, with 2-1 = 1 key separating the 2 children. Hence a 3-node has 2 values separating 3 children, and a N node has N children separated by N-1 keys.

A classical B-Tree can have N-node internal nodes, and empty 2-nodes as leaf nodes, or more conveniently, the children can either be a value or a pointer to the next N-node, so it is a union.

The main idea with B-trees is that one starts with a root N-node , which is able to hold N-1 entries, but on the Nth entry, the number of keys for the node is exhausted, and the node can be split into two half sized N/2 sized N nodes, separated by a single key K, which is equal to the right node's leftmost key, so any entry with key K2 equal or greater than K goes in the right node, and anything less than K goes in the left. When the root node is split, a new root node is created with one key, and a left child and a right child. Since there are N children but only N-1 entries, the leftmost child is stored as a separate pointer. If the leftmost pointer splits, then the left half becomes the new leftmost pointer, and the right half and separating key is inserted into the front of the entries.

An alternative is the B+ tree which is the most commonly used in database systems, because only values are stored in leaf nodes, whereas internal nodes only store keys and pointers to other nodes, putting a limit on the size of the datum value as the size of a pointer. This often allows internal nodes with more entries able to fit a certain block size, e.g. 4K is a common physical disc block size. Hence , if a B+ tree internal node is aligned to a physical disc block, then the main rate limiting factor of reading a block of a large index from disc because it isn't cached in a memory list of blocks is reduced to one block read.

A B+ tree has bigger internal nodes, so is wider and shorter in theory than an equivalent B tree which must fit all nodes within a given physical block size, hence overall it is a faster index due to greater fan out and less height to reach keys on average.

Apparently, this fan out is so important, compression can also be applied to the blocks to increase the number of entries fitting within a given underlying layer's block size (the underlying layer is often a filesystem block).

Most database systems use the B+ tree algorithm, including postgresql, mysql, derbydb, firebird, many Xbase index types, etc.

Many filesystems also use a B+ tree to manage their block layout (e.g. xfs, NTFS, etc).

Transwiki has a java implementation of a B+ Tree which uses traditional arrays as key list and value list.

Below is an example of a B Tree with test driver, and a B+ tree with a test driver. The memory / disc management is not included, but a usable hacked example can be found at Hashing Memory Checking Example.

This B+ tree implementation was written out of the B Tree , and the difference from the transwiki B+ tree is that it tries to use the semantics of SortedMap and SortedSet already present in the standard Java collections library.

Hence , the flat leaf block list of this B+ implementation can't contain blocks that don't contain any data, because the ordering depends on the first key of the entries, so a leaf block needs to be created with its first entry.

A B tree java example

package btreemap;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

/** can't work without setting a comparator */
public class BTreeMap<K, V> implements SortedMap<K, V> {

private static final int NODE_SIZE = 100;

@Override
public Comparator<? super K> comparator() {
// TODO Auto-generated method stub

return comparator;
}

Comparator< ? super K> defaultComparator = new
Comparator<  K>() {

@Override
public int compare(K o1, K o2) {
// TODO Auto-generated method stub
Comparable c1 = (Comparable)o1;
Comparable c2 = (Comparable)o2;
return c1.compareTo(c2);
}
};
Comparator<? super K> comparator = defaultComparator;
BTBlock<K, V> root = new BTBlock<K, V>(NODE_SIZE, comparator);
/**
*
* @param comparator
*            - this is mandatory for the tree to work
*/
public void setComparator(Comparator<? super K> comparator) {
this.comparator = comparator;
root = new BTBlock<K, V>(NODE_SIZE, comparator);
}

/**
*
*
*
* @param <K>
* @param <V>
*            the entry is associated with a right child block.
*
*/
static class BlockEntry<K, V> {
K k;
V v;
BTBlock left;

BlockEntry() {

}

BlockEntry(K k, V v) {
left = null;
this.k = k;
this.v = v;
}
}

/**
*
*  - this represents the result of splitting a full block into
*         a left block, and a right block, and a median key, the right
*         block and the median key held in a BlockEntry structure as above.
* @param <K>
* @param <V>
* @param <V>g
*/
static class SplitRootEntry<K, V> {
BTBlock<K, V> right;
BlockEntry<K, V> entry;

SplitRootEntry(BlockEntry<K, V> entry, BTBlock<K, V> right) {
this.right = right;
this.entry = entry;
}

SplitRootEntry() {
super();
}
}

/**
* this is used to return a result of a possible split , during recursive
* calling.
*
*
*
* @param <K>
* @param <V>
*/
static class resultAndSplit<K, V> {

/**
* null , if there is no split.
*/
SplitRootEntry<K, V> splitNode;
V v;

resultAndSplit(V v) {
this.v = v;
}

resultAndSplit(SplitRootEntry<K, V> entry, V v) {
this.v = v;
this.splitNode = entry;
}
}

/**
* used to represent the insertion point after searching a block if compare
* is zero, then a match was found, and pos is the insertion entry if
* compare < 0 and pos == 0 , then the search ended up less than the
* leftmost entry else compare > 0 , and the search will be to the immediate
* right of pos.
*
*
*
*/
static class PosAndCompare {
int pos = 0;
int compare = 0;
}

static class BTBlock<K, V> {
List<BlockEntry<K, V>> entries;
BTBlock<K, V> rightBlock = null;
private int maxSz = 0;

Comparator<? super K> comparator;

Comparator<? super K> comparator() {
return comparator;
}

public BTBlock(int size, Comparator<? super K> c) {
entries = new ArrayList<BlockEntry<K, V>>();
maxSz = size;
this.comparator = c;
}

/**
* PosAndCompare usage: if compare is zero, then a match was found, and
* pos is the insertion entry if compare < 0 and pos == 0 , then the
* search ended up less than the leftmost entry else compare > 0 , and
* the search will be to the immediate right of pos.
*
*
*
*/
// private void blockSearch(K k, PosAndCompare pc) {
// for (int i = 0; i < entries.size(); ++i) {
// pc.compare = comparator.compare(k, entries.get(i).k);
// if (pc.compare == 0) {
// pc.pos = i;
// return;
// }
// if (pc.compare < 0 && i == 0) {
// pc.pos = 0;
// return;
// }
//
// if (pc.compare < 0) {
// pc.pos = i - 1;
// pc.compare = 1;
// return;
// }
//
// }
// pc.pos = entries.size() - 1;
// pc.compare = 1;
//
// // binary search, it's hard to get it right !
// // int left = 0;
// // int right = entries.size();
// //
// // while (left <= right && left < entries.size()) {
// // // pc.pos = (right - left) / 2 + left;
// // pc.pos = (left + right) / 2;
// // pc.compare = comparator().compare(k, entries.get(pc.pos).k);
// // if (pc.compare < 0) {
// // right = pc.pos - 1;
// // } else if (pc.compare > 0) {
// // left = pc.pos + 1;
// // } else {
// // return;
// // }
// // }
// //
// // BlockEntry<K, V> e = new BlockEntry<K, V>(k, null);
// // pc.pos = Collections.binarySearch(entries, e, cmp);
//
// }

Comparator<BlockEntry<K, V>> cmp = new Comparator<BlockEntry<K, V>>() {

@Override
public int compare(BlockEntry<K, V> o1, BlockEntry<K, V> o2) {
// TODO Auto-generated method stub
return comparator.compare(o1.k, o2.k);

}
};

resultAndSplit<K, V> put(K k, V v) {
V v2;
if (entries.size() == 0) {
entries.add(new BlockEntry<K, V>(k, v));
return new resultAndSplit<K, V>(v);
} else {

// PosAndCompare pc = new PosAndCompare();
BlockEntry<K, V> e = new BlockEntry<K, V>(k, v);
int res = Collections.binarySearch(entries, e, cmp);
int index = -res - 1;
// blockSearch(k, pc);

// a match
if (res >= 0) {
v2 = entries.get(res).v;
entries.get(res).v = v;
return new resultAndSplit<K, V>(v2);
}

// follow leftBlock if search is to left of first entry

if (index == entries.size() && rightBlock != null) {

resultAndSplit<K, V> result = rightBlock.put(k, v);
if (result.splitNode != null) {
rightBlock = result.splitNode.right;
}
} else if (index == entries.size() && rightBlock == null
&& entries.size() == maxSz) {
rightBlock = new BTBlock<K, V>(this.maxSz, comparator);
resultAndSplit<K, V> result = rightBlock.put(k, v);

} else if (index < entries.size()
&& entries.get(index).left != null) {
// follow right block if it exists
resultAndSplit<K, V> result = entries.get(index).left.put(
k, v);
if (result.splitNode != null) {
entries.get(index).left = result.splitNode.right;
// add to the left

}

} else {
// add to the left

}

// check if overflowed block , split if it has.
if (entries.size() > maxSz) {
int mid = entries.size() / 2;

// copy right half to new entries list.
List<BlockEntry<K, V>> leftEntries = new ArrayList<BlockEntry<K, V>>();
for (int i = 0; i < mid; ++i) {
}

BlockEntry<K, V> centreEntry = entries.get(mid);

BTBlock<K, V> leftBlock = new BTBlock<K, V>(maxSz,
comparator);

leftBlock.entries = leftEntries;

// the median entry's left block is the new left block's
// leftmost block
leftBlock.rightBlock = centreEntry.left;
// the new right block becomes the right block
centreEntry.left = leftBlock;

// reduce the old block's entries into its left half of
// entries.
ArrayList<BlockEntry<K, V>> newEntries = new ArrayList<BlockEntry<K, V>>();
for (int i = mid + 1; i < entries.size(); ++i)
this.entries = newEntries;
// create a return object, with the reduced old block as the
// left block
// and the median entry with the new right block attached

SplitRootEntry<K, V> split = new SplitRootEntry<K, V>(
centreEntry, this);

// the keyed value didn't exist before , so null
return new resultAndSplit<K, V>(split, null);

}
return new resultAndSplit<K, V>(v);
}

}

V get(K k) {

if (entries.size() == 0)
return null;

BlockEntry<K, V> e = new BlockEntry<K, V>(k, null);
int res = Collections.binarySearch(entries, e, cmp);
int index = -res - 1;

if (res >= 0) {
return entries.get(res).v;
}

if (index == entries.size() && rightBlock != null) {
return rightBlock.get(k);
} else if (index < entries.size()
&& entries.get(index).left != null) {
return (V) entries.get(index).left.get(k);
} else
return null;
}

void getRange(SortedMap map, K k1, K k2) {
BlockEntry<K, V> e = new BlockEntry<K, V>(k1, null);
int res = Collections.binarySearch(entries, e, cmp);
int index = -res - 1;
BlockEntry<K, V> e2 = new BlockEntry<K, V>(k2, null);
int res2 = Collections.binarySearch(entries, e2, cmp);
int index2 = -res2 - 1;

int from = res >= 0 ? res : index;
int to = res2 >= 0 ? res2 : index2;

for (int i = from; i <= to; ++i) {

if (i < entries.size() && (i > from || res < 0)
&& entries.get(i).left != null) {
entries.get(i).left.getRange(map, k1, k2);
// if (pc2.pos == pc.pos)
// break;
}
if (i < to || res2 >= 0)
map.put(entries.get(i).k, entries.get(i).v);

if (i == entries.size() && rightBlock != null) {
rightBlock.getRange(map, k1, k2);
}

}

}

if (rightBlock != null) {
}
return entries.get(0).k;
}

K tailKey() {
int i = entries.size() - 1;
if (entries.get(i).left != null) {
return (K) entries.get(i).left.tailKey();
}
return entries.get(i).k;
}

void show(int n) {
showTabs(n);
for (int i = 0; i < entries.size(); ++i) {
BlockEntry<K, V> e = entries.get(i);
System.err.print("#" + i + ":(" + e.k + ":" + e.v + ")  ");
}
System.err.println();
showTabs(n);

if (rightBlock != null) {
System.err.print("Left Block\n");
rightBlock.show(n + 1);
} else {
System.err.println("No Left Block");
}

for (int i = 0; i < entries.size(); ++i) {
BlockEntry<K, V> e = entries.get(i);
showTabs(n);
if (e.left != null) {

System.err.println("block right of #" + i);
e.left.show(n + 1);
} else {
System.err.println("No block right of #" + i);
}
}
showTabs(n);
System.err.println("End of Block Info\n\n");
}

private void showTabs(int n) {
// TODO Auto-generated method stub
for (int i = 0; i < n; ++i) {
System.err.print("  ");
}
}

}

@Override
public SortedMap<K, V> subMap(K fromKey, K toKey) {
TreeMap<K, V> map = new TreeMap<K, V>();
root.getRange(map, fromKey, toKey);
return map;
}

@Override
public SortedMap<K, V> headMap(K toKey) {
// TODO Auto-generated method stub
};

@Override
public SortedMap<K, V> tailMap(K fromKey) {
// TODO Auto-generated method stub
return subMap(fromKey, root.tailKey());
}

@Override
public K firstKey() {
// TODO Auto-generated method stub
}

@Override
public K lastKey() {
// TODO Auto-generated method stub
return root.tailKey();
}

@Override
public int size() {
// TODO Auto-generated method stub
return 0;
}

@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}

@Override
public boolean containsKey(Object key) {
// TODO Auto-generated method stub
return get(key) != null;
}

@Override
public boolean containsValue(Object value) {
// TODO Auto-generated method stub
return false;
}

@Override
public V get(Object key) {
// TODO Auto-generated method stub
return root.get((K) key);
}

@Override
public V put(K key, V value) {
resultAndSplit<K, V> b = root.put(key, value);
if (b.splitNode != null) {
root = new BTBlock<K, V>(root.maxSz, root.comparator);
root.rightBlock = b.splitNode.right;
}
return b.v;
}

@Override
public V remove(Object key) {
// TODO Auto-generated method stub
return null;
}

@Override
public void putAll(Map<? extends K, ? extends V> m) {
// TODO Auto-generated method stub

}

@Override
public void clear() {
// TODO Auto-generated method stub

}

@Override
public Set<K> keySet() {
// TODO Auto-generated method stub
return null;
}

@Override
public Collection<V> values() {
// TODO Auto-generated method stub
return null;
}

@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return null;
}

}

package btreemap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class TestBtree {

private static final int N = 50000;

public static void main(String[] args) {
BTreeMap<Integer, Integer> map = new BTreeMap<Integer , Integer>();
Random r = new Random();

ArrayList<Integer> t = new ArrayList<Integer>();

Comparator<Integer> comparator = new Comparator<Integer>() {

@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o1.intValue() - o2.intValue();
}

};
map.setComparator(comparator);
List<Integer> testVals = new ArrayList<Integer>();
for (int i =0 ; i < N ; ++i) {
}
for (int i = 0; i < N; ++i ) {
int x = r.nextInt(testVals.size());
x = testVals.remove(x);
//int x=i;
map.put(x, x);
}

System.err.println("output " + N + " vals");

map.root.show(0);

for (int i = 0; i < N; ++i) {
int x = t.get(i);

if ( x != map.get(x))
System.err.println("Expecting " + x + " got " + map.get(x));

}
System.err.println("Checked " + N + " entries");
}
}


A B+ tree java example

Experiments include timing the run ( e.g. time java -cp . btreemap.BPlusTreeTest1 ) , using an external blocksize + 1 sized leaf block size, so that this is basically the underlying entries TreeMap only , vs , say, 400 internal node size, and 200 external node size . Other experiments include using a SkipListMap instead of a TreeMap.

package btreemap;

import java.util.Collection;
import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.SortedSet;
import java.util.TreeMap;
import java.util.TreeSet;
/**
* a B+ tree, where leaf blocks contain key-value pairs and
* internal blocks have keyed entries pointing to other internal blocks
* or leaf blocks whose keys are greater than or equal to the associated key.
*
* @author syan
*
* @param <K> key type implements Comparable
* @param <V> value type
*/
public class BPlusTreeMap<K, V> implements SortedMap<K, V> {

private int maxInternalBlockSize;
BPlusAnyBlock<K, V> root;
private int maxExternalSize;

BPlusTreeMap(int maxInternalSize, int maxExternalSize) {
this.maxInternalBlockSize = maxInternalSize;
this.maxExternalSize = maxExternalSize;

}

static class SplitOrValue<K, V> {
V v;
K k;
BPlusAnyBlock<K, V> left, right;
boolean split;

public boolean isSplit() {
return split;
}

public void setSplit(boolean split) {
this.split = split;
}

public SplitOrValue(V value) {
v = value;
setSplit(false);
}

public SplitOrValue(BPlusAnyBlock<K, V> left2,
BPlusAnyBlock<K, V> bPlusBlock) {
left = left2;
right = bPlusBlock;
k = right.firstKey();
setSplit(true);
// System.err.printf("\n\n** split occured %s**\n\n", bPlusBlock
// .getClass().getSimpleName());
}

}

static abstract class BPlusAnyBlock<K, V> {
public abstract SplitOrValue<K, V> put(K k, V v);

abstract SplitOrValue<K, V> splitBlock();

public abstract V get(K k);

public abstract boolean isEmpty();

public abstract K firstKey();

}

SortedSet<BPlusLeafBlock<K, V>> blockList = getLeafBlockSet();

SortedSet<BPlusLeafBlock<K, V>> getLeafBlockSet() {
// return new ConcurrentSkipListSet<BPlusLeafBlock<K, V>>();
return new TreeSet<BPlusLeafBlock<K, V>>();
}

static class BPlusLeafBlock<K, V> extends BPlusAnyBlock<K, V> implements
Comparable<BPlusLeafBlock<K, V>> {
SortedMap<K, V> entries = getEntryCollection();

static <K, V> SortedMap<K, V> getEntryCollection() {
return new TreeMap<K, V>();
}

int maxSize;
private BPlusTreeMap<K, V> owner;

public boolean isEmpty() {
return entries.isEmpty();
}

public BPlusLeafBlock(BPlusTreeMap<K, V> bPlusTreeMap,
SortedMap<K, V> rightEntries) {
this.owner = bPlusTreeMap;
maxSize = owner.maxExternalSize;
entries = rightEntries;
}

public SplitOrValue<K, V> put(K k, V v) {
V v2 = entries.put(k, v);

if (entries.size() >= maxSize)
return splitBlock();
else
return new SplitOrValue<K, V>(v2);

}

public SplitOrValue<K, V> splitBlock() {

SortedMap<K, V> leftEntries = getEntryCollection();
SortedMap<K, V> rightEntries = getEntryCollection();

int i = 0;

for (Entry<K, V> e : entries.entrySet()) {
// System.out.println(this.getClass().getSimpleName() +
// " split entry " + e.getKey());
if (++i <= maxSize / 2)
leftEntries.put(e.getKey(), e.getValue());
else
rightEntries.put(e.getKey(), e.getValue());
}
BPlusLeafBlock<K, V> right = createBlock(rightEntries);
// System.out.println("finished block split");
// System.out.println("\nleft block");
// for (K ik : leftEntries.keySet()) {
// System.out.print(ik + " ");
// }
// System.out.println("\nright block");
// for (K ik : right.entries.keySet()) {
// System.out.print(ik + " ");
// }
// System.out.println("\n");
this.entries = leftEntries;

return new SplitOrValue<K, V>(this, right);
}

private BPlusLeafBlock<K, V> createBlock(SortedMap<K, V> rightEntries) {
return owner.createLeafBlock(rightEntries);
}

@Override
public V get(K k) {
return entries.get(k);
}

@Override
public int compareTo(BPlusLeafBlock<K, V> o) {

return ((Comparable<K>) entries.firstKey()).compareTo(o.entries
.firstKey());
}

@Override
public K firstKey() {
return entries.firstKey();
}

}

static class BPlusBranchBlock<K, V> extends BPlusAnyBlock<K, V> {
SortedMap<K, BPlusAnyBlock<K, V>> entries = createInternalBlockEntries();
int maxSize;

private BPlusAnyBlock<K, V> left;

public boolean isEmpty() {
return entries.isEmpty();
}

public BPlusBranchBlock(int maxSize2) {
this.maxSize = maxSize2;

}

public SplitOrValue<K, V> put(K k, V v) {
BPlusAnyBlock<K, V> b = getBlock(k);

SplitOrValue<K, V> sv = b.put(k, v);

if (sv.isSplit()) {

entries.put(sv.k, sv.right);

if (entries.size() >= maxSize)
sv = splitBlock();
else
sv = new SplitOrValue<K, V>(null);
}

return sv;
}

BPlusAnyBlock<K, V> getBlock(K k) {
assert (entries.size() > 0);
BPlusAnyBlock<K, V> b = entries.get(k);
if (b == null) {
// headMap returns less than k
b = left;

// System.out.println("for key " + k
// + " getting from leftmost block");
// showEntries();

} else {

// System.out.println("for key " + k
// + " getting from block with key " + head.lastKey());
// showEntries();
}
}
assert (b != null);
return b;
}

public void showEntries() {
System.out.print("entries = ");
for (K k : entries.keySet()) {
System.out.print(k + " ");
}
System.out.println();
}

public SplitOrValue<K, V> splitBlock() {

Set<Entry<K, BPlusAnyBlock<K, V>>> ee = entries.entrySet();
int i = 0;
BPlusBranchBlock<K, V> right = new BPlusBranchBlock<K, V>(maxSize);
SortedMap<K, BPlusAnyBlock<K, V>> leftEntries = createInternalBlockEntries();

for (Entry<K, BPlusAnyBlock<K, V>> e : ee) {
// System.out.print("split check " + e.getKey() + ":"
// );
if (++i <= maxSize / 2)
leftEntries.put(e.getKey(), e.getValue());
else
right.entries.put(e.getKey(), e.getValue());

}
// System.out.println("\n");
this.entries = leftEntries;

return new SplitOrValue<K, V>(this, right);
}

private SortedMap<K, BPlusAnyBlock<K, V>> createInternalBlockEntries() {
return new TreeMap<K, BPlusAnyBlock<K, V>>();
}

@Override
public V get(K k) {
BPlusAnyBlock<K, V> b = getBlock(k);

return b.get(k);
}

@Override
public K firstKey() {
return entries.firstKey();
}

}

@Override
public SortedMap<K, V> subMap(K fromKey, K toKey) {
TreeMap<K, V> map = new TreeMap<K, V>();
BPlusLeafBlock<K, V> b1 = getLeafBlock(fromKey);

BPlusLeafBlock<K, V> b2 = getLeafBlock(toKey);

SortedSet<BPlusLeafBlock<K, V>> range = blockList.subSet(b1, b2);

for (BPlusLeafBlock<K, V> b : range) {
SortedMap<K, V> m = b.entries.subMap(fromKey, toKey);
map.putAll(m);
}

return map;
}

private BPlusLeafBlock<K, V> getLeafBlock(K key) {
BPlusAnyBlock<K, V> b1;
b1 = root;
while (b1 instanceof BPlusBranchBlock<?, ?>) {
b1 = ((BPlusBranchBlock<K, V>) b1).getBlock(key);

}
return (BPlusLeafBlock<K, V>) b1;

}

public BPlusLeafBlock<K, V> createLeafBlock(SortedMap<K, V> rightEntries) {
BPlusLeafBlock<K, V> b = new BPlusLeafBlock<K, V>(this, rightEntries);
return b;
}

@Override
public SortedMap<K, V> headMap(K toKey) {
return subMap(firstKey(), toKey);
};

@Override
public SortedMap<K, V> tailMap(K fromKey) {
return subMap(fromKey, lastKey());
}

@Override
public K firstKey() {
return blockList.first().entries.firstKey();
}

@Override
public K lastKey() {
return blockList.last().entries.lastKey();
}

@Override
public int size() {
return (int) getLongSize();
}

private long getLongSize() {
long i = 0;
for (BPlusLeafBlock<K, V> b : blockList) {
i += b.entries.size();
}
return i;
}

@Override
public boolean isEmpty() {
return root.isEmpty();
}

@Override
public boolean containsKey(Object key) {
return get(key) != null;
}

@Override
public boolean containsValue(Object value) {
return false;
}

@Override
public V get(Object key) {
return (V) root.get((K) key);
}

@Override
public V put(K key, V value) {
if (root == null) {
SortedMap<K, V> entries = BPlusLeafBlock.getEntryCollection();
entries.put(key, value);
root = createLeafBlock(entries);
return null;
}
SplitOrValue<K, V> result = root.put(key, value);
if (result.isSplit()) {
BPlusBranchBlock<K, V> root = new BPlusBranchBlock<K, V>(
maxInternalBlockSize);
root.left = result.left;
root.entries.put(result.k, result.right);
this.root = root;
}
return result.v;
}

@Override
public V remove(Object key) {
return null;
}

@Override
public void putAll(Map<? extends K, ? extends V> m) {
for (K k : m.keySet()) {
put(k, m.get(k));
}
}

@Override
public void clear() {

}

@Override
public Set<K> keySet() {
TreeSet<K> kk = new TreeSet<K>();
for (BPlusLeafBlock<K, V> b : blockList) {
}
return kk;
}

@Override
public Collection<V> values() {
// TODO Auto-generated method stub
return null;
}

@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return null;
}

@Override
public Comparator<? super K> comparator() {
// TODO Auto-generated method stub
return null;
}

public void showLeaves() {

for (BPlusLeafBlock<K, V> b : blockList) {
System.out.println("Block");
for (Entry<K, V> e : b.entries.entrySet()) {
System.out.print(e.getKey() + ":" + e.getValue() + "  ");
}
System.out.println();
}
}
}

package btreemap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

/** driver program to test B+ tree */

public class BPlusTreeTest1 {

private static final int N = 1200000;

public static void main(String[] args) {
BPlusTreeMap<Integer, Integer> map = new BPlusTreeMap<Integer, Integer>(
400,  200 );// 5000002);
Random r = new Random();

ArrayList<Integer> t = new ArrayList<Integer>();

Comparator<Integer> comparator = new Comparator<Integer>() {

@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o1.intValue() - o2.intValue();
}

};

List<Integer> testVals = new ArrayList<Integer>();
for (int i = 0; i < N; ++i) {
}

for (int i = 0; i < N; ++i) {
int x = r.nextInt(N);
int z = testVals.set(x, testVals.get(0));
testVals.set(0, z);

}

for (int i = 0; i < N; ++i) {
map.put(testVals.get(i), testVals.get(i));
showProgress("put", testVals, i);
}
System.err.println("output " + N + " vals");

try {
for (int i = 0; i < N; ++i) {

showProgress("get", testVals, i);
int x = testVals.get(i);
if (x != map.get(x))
System.err.println("Expecting " + x + " got " + map.get(x));

}
System.err.println("\nChecked " + N + " entries");
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
map.showLeaves();
}
}

private static void showProgress(String label, List<Integer> testVals, int i) {
if (i % (N / 1000) == 0) {
System.out.printf("%s %d:%d; ", label, i, testVals.get(i));
if (i % (N / 10100) == 0)
System.out.println();
}
}
}


Treaps

The invariant in a binary tree is that left is less than right with respect to insertion keys. e.g. for a key with order, ord(L) < ord(R). This doesn't dictate the relationship of nodes however, and left and right rotation does not affect the above. Therefore another order can be imposed. If the order is randomised, it is likely to counteract any skewness of a plain binary tree e.g. when inserting an already sorted input in order.

Below is a java example implementation, including a plain binary tree delete code example.

import java.util.Iterator;
import java.util.Random;

public class Treap1<K extends Comparable<K>, V> {
public Treap1(boolean test) {
this.test = test;
}

public Treap1() {}
boolean test = false;
static Random random = new Random(System.currentTimeMillis());

class TreapNode {
int priority = 0;
K k;
V val;
TreapNode left, right;

public TreapNode() {
if (!test) {
priority = random.nextInt();
}
}
}

TreapNode root = null;

void insert(K k, V val) {
root = insert(k, val, root);
}

TreapNode insert(K k, V val, TreapNode node) {
TreapNode node2 = new TreapNode();
node2.k = k;
node2.val = val;
if (node == null) {
node = node2;
} else if (k.compareTo(node.k) < 0) {

node.left = insert(k, val, node.left);

} else {

node.right = insert(k, val, node.right);

}

if (node.left != null && node.left.priority > node.priority) {
// left rotate
TreapNode tmp = node.left;
node.left = node.left.right;
tmp.right = node;
node = tmp;
} else if (node.right != null && node.right.priority > node.priority) {
// right rotate
TreapNode tmp = node.right;
node.right = node.right.left;
tmp.left = node;
node = tmp;
}
return node;
}

V find(K k) {
return findNode(k, root);
}

private V findNode(K k, Treap1<K, V>.TreapNode node) {

if (node == null)
return null;
if (k.compareTo(node.k) < 0) {
return findNode(k, node.left);
} else if (k.compareTo(node.k) > 0) {
return findNode(k, node.right);
} else {
return node.val;
}
}

static class Deleted {
boolean success = false;
}

boolean delete(K k) {
Deleted del = new Deleted();
root = deleteNode(k, root, del);
return del.success;
}

private Treap1<K, V>.TreapNode deleteNode(K k, Treap1<K, V>.TreapNode node, Deleted del) {

if (node == null) {
return null;
} else if (k.compareTo(node.k) < 0) {
node.left = deleteNode(k, node.left, del) ;
} else if (k.compareTo(node.k) > 0) {
node.right =  deleteNode(k, node.right, del);

// k.compareTo(node.k) == 0
} else if ( node.left == null ) {
del.success = true;
return node.right;
} else if ( node.right == null) {
del.success = true;
return  node.left;
} else  if (node.left !=null && node.right != null){
/*
// left rotate and all delete on left subtree
TreapNode tmp = node.right;
node.right = node.right.left;
tmp.left = node;
node = tmp;
node.left = deleteNode(k , node.left, del);
*/
// more standard method ? doesn't disturb tree structure as much
// find leftmost descendant of the right child node and replace contents
TreapNode n2  = node.right;
TreapNode previous2 = null;
while (n2.left != null) {
previous2 = n2;
n2 = n2.left;
}

if (previous2 != null) {
previous2.left = n2.right;
//n2 has no parent link, orphaned
} else {
node.right = n2.right;
//n2 has no parent link, orphaned
}

node.k = n2.k;
node.val = n2.val;
del.success = true;
// once n2 out of scope, the orphaned node at n2 will be garbage collected,
}

return node;
}

public static void main(String[] args) {

for (int i = 0; i < 15000; ++i) {
}

testNumbers(dat, true); // no random priority balancing
testNumbers(dat, false);
}

private static void testNumbers(LinkedList<Integer> dat,
boolean test) {
Treap1<Integer, Integer> treap = new Treap1<>(test);

for (Integer integer : dat) {
treap.insert(integer, integer);
}

long t1 = System.currentTimeMillis();
Iterator<Integer> desc = dat.iterator();
int found = 0;
while (desc.hasNext()) {
Integer j = desc.next();
Integer i = treap.find(j);
if (j.equals(i)) {
++found;
}
}
long t2 = System.currentTimeMillis();
System.out.println("found = " + found + " in " + (t2 - t1));

System.out.println("test delete");
int deleted = 0;

for (Integer integer : dat) {
if (treap.delete(integer))
++deleted;
}
System.out.println("Deleted = " + deleted);

}
}


References

• William Ford and William Tapp. Data Structures with C++ using STL. 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2002.