In this lecture, we will consider how to modify countries to implement an append method to the constant running time. Such an append method is crucial for implementing combiners sufficiently. The first step in implementing a combiner is providing a plus equals method. Assuming that a concluse base combiner internally holds a concluse object, the plus equals method would insert an element by creating a single element tree. This single element tree can then be concatenated with an existing tree. Let's append the element seven as a single tree. To append the single tree of height one into the larger tree, we need to descend to one of its leaves on the right side. And update the path from the root to that leaf. Since the depth of the tree is bound by all the running time of the plus equals method would also be. Logarithmic running time is not bad but it could be better. We would prefer if plus equals was a constant time method, as plus equals is invoked every time the processor adds a new element to the combiner. Surprisingly enough, it turns out this is possible. However, we will need to relax the previous invariance on this data structure, so we will extend the Conc-Tree with a new node type. The idea will be to represent the result of a plus equals operation differently. For this reason, we will introduce a new type of a node called Append. The Append node has exactly the same structure as the conc node does. It has a left and a right sub tree and it's level and size are defined in exactly the same way as they were for Conc notes. However, we will not impose the previous balance in variant on the Append nodes. We will allow arbitrary difference in levels between the left and the right child. So trees like this will be allowed. In this example, the left and the right subtrees have heights 5 and 3, and the difference between them is 2. But since they're connected by an append node, this is fine. With this newly introduced node type, here is one possible implementation of append leaf. This method first creates a single node, and then it creates a new append node to link them together. This method allocates two objects in total. So the total number of computational steps it takes is constant and does not depend on the size of the tree. It's running time is really 0(1). Unfortunately, a tree created this way is obviously unbalanced. If we are to later use it for parallelism or concatenations, we need to somehow transform the data structure back into a format that does not have any Append nodes. Question is, can we do this reasonably quickly, for example, in logarithmic time? We claim that this is not possible, and here is why. After we add n elements to the tree this way, we will have n Append nodes in total. Therefore, we would have to traverse and process all those nodes to eliminate them from the tree. And once again establish the balance in variance. The conversion to a normal Conc-Tree would have to take at least O(n) steps. The fundamental problem here is that we are essentially still building a link list with append nodes. So we need to link these notes more intelligently. In what follows, we will make sure that if the total number of elements in the tree is n, then there are never more than log n of append nodes in the data structure. To understand how to achieve this, let's consider a single unrelated task that we know very well and that is counting in a Binary Number System. How do we count in the standard positional Binary Number System? Let's see an example. We start with zero which is represented with a single digit in the Binary Number System. This digit is at zero's position, and has the weight 2 to the power of 0. Let's increment it by 1. If we add 1 to the 0 digit, it is incremented and becomes 1. To convert this number to the decimal system, you need to multiply the single digit 1 with its weight. We get the same representation one in the decimal number system. If we, again, add one to this digit, we can no longer increment it. Instead, we carry the digit one to the next position with the weight two to the power of one. To convert this number to the decimal system, you multiply 1 with 2 to the power of 1 and add it to 0, multiplied by the 2 to the power of 0. This time, we get the number 2 in the decimal number system. We continue counting like this and increase the list's signficant digit again. We get the number 1 1, which corresponds to the decimal number 3. In the next step, we need to perform two carry operations. First, we carry over the least significant digit, and then, since the next digit is also 1, we repeat the carry process. We get the digit 1 0 0, or the decimal number four. The binary number system has two important properties. First, to count up to n in the binary number system, we will have to do O(n) amount of work. If we count the number of digits we flipped to get to n, we will see that it is less than 2 times n. In the previous example, it is not incidental that we flipped exactly seven digits to get to the number 4. The second property is that a number n requires all of log n digits. If this were not the case it would be really hard to write big numbers. Here is a sanity check. Number 4 is written as 1 0 0. Number 8 is twice as large, but takes only an additional digit. Number 16 is again twice as large, and again requires only one more digit. So, while the number grows exponentially, the number of digits grows linearly. This is the same as saying that the number grows linearly, and the number of digits grows logarhythmically. Now, observe that there is a correspondence between a digit at position k, and a contrary with level k. When we link to trees with level k, you get a tree with level k plus one, just as adding two digits at position k becomes a digit at position k plus one. If we start with a tree at level zero and append another such tree, we can link them to a tree with level one in one computational step. If we again add a tree at level 0, we can add it directly to the empty position for the level 0 3. There is no need to link anything in this step. Next time we add a tree at level 0, we will first have to link the two trees at level 0 which corresponds to the first carry operation, and then link the two trees at level one, which corresponds to the second carry operation. Linking the trees in the same order as we count in a binary number system results in a similar pair of properties. First, to add n leaves likes this takes O(n) work. Meaning that on average adding each leaf requires O(1) work. Second, storing n leaves requires a logarithmic amount of Append nodes. We will use the Append nodes to store our binary number. In this binary number representation, the 0 digit will correspond to a missing tree, and the 1 digit will correspond to an existing tree. For example, assume that we have the following trees. In this append list, the trees with levels four, three, and one exist. And the trees with the levels two and zero are not present. The corresponding append list will look as follows. This corresponds to the following binary number. One one zero one zero. Note that they do not explicitly represent the zero digits. They are encoded as missing trees. Using this idea, let's re-implement the appendLeaf method which is this time, appends the single tree ys to the tree xs. This method, first better matches on xs to handle the trivial cases. When the first tree is empty, it just returns ys. When it gets two single trees, just links them together. Or links an inner node and bias into an append node. In the tree, xs is already an append node to start with. The work is delegated to the recursive append method. The append node essentially implements counting in a binary number system. If the tree ys is a level smaller than the right sub-tree of xs, a new append node is created. Here is an example. Otherwise the right sub-tree of xs and ys are linked into a normal tree, zed s. In our example, if we now append another tree of level zero, we need to link them together into zs of level one and then recursively call append again. The recursion then repeats the process. The remaining two cases handle the scenario in which the left sub-tree is not Append, which happens if we manage to push the tree all the way to the bottom of this Append list. To summarize, we have implemented an immutable data structure with constant time Append operation and logarithmic time concatenation. Although, it did not show how to transform a Conc-Tree with append nodes into a regular Conc-Tree in logarithmic time, we note that this should be straightforward to do. This requires concatenating the trees from the append list together. We leave this task to you as an optional exercise. In the next lecture, we will use the 0(1) append operation as a basis for an efficient mutable data structure, used to implement the combiner.
