What additional rotation is required to remove 2-3-4 left mahogany trees from top to bottom?

Question

I am implementing the LLRB package, which should work in either of two modes: Bottom-Up 2-3 or Top-Down 2-3-4 described by Sedgewick (the code is an improved code, although it only deals with 2-3 trees here , thanks RS for pointer).

Sedgewick gives a very clear description of tree operations for mode 2-3, although he spends a lot of time about mode 2-3-4. It also shows how a simple change in the order of color flipping during insertion can change the behavior of the tree (either split along the path down by 2-3-4, or split along the path up by 2-3):

private Node insert(Node h, Key key, Value value) { if (h == null) return new Node(key, value); // Include this for 2-3-4 trees if (isRed(h.left) && isRed(h.right)) colorFlip(h); int cmp = key.compareTo(h.key); if (cmp == 0) h.val = value; else if (cmp < 0) h.left = insert(h.left, key, value); else h.right = insert(h.right, key, value); if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); // Include this for 2-3 trees if (isRed(h.left) && isRed(h.right)) colorFlip(h); return h; } 

However, he suppresses the removal in 2-3-4 LLRB with the following:

The code on the next page is a complete implementation of delete () for LLRB 2-3 trees. It is based on the reverse approach used to insert 2-3-4 trees from top to bottom: we perform turns and color transitions along the path down the search path to ensure that the search does not end at 2-node, so that we can simply remove the node at the bottom. We use the fixUp () method to share code to flip and rotate color after recursive calls in insert () code. With fixUp (), we can leave the right red links and unbalanced 4-nodes along the search path so that these conditions are corrected along the path up the tree. ( The approach is also effective with 2-3-4 trees, but requires additional rotation when the right node from the search path is 4-node. )

Its delete () function:

 private Node delete(Node h, Key key) { if (key.compareTo(h.key) < 0) { if (!isRed(h.left) && !isRed(h.left.left)) h = moveRedLeft(h); h.left = delete(h.left, key); } else { if (isRed(h.left)) h = rotateRight(h); if (key.compareTo(h.key) == 0 && (h.right == null)) return null; if (!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h); if (key.compareTo(h.key) == 0) { h.val = get(h.right, min(h.right).key); h.key = min(h.right).key; h.right = deleteMin(h.right); } else h.right = delete(h.right, key); } return fixUp(h); } 

My implementation correctly supports LLRB 2-3 invariants for all tree operations on 2-3 trees, but is not suitable for a subclass of right-handed deletions on 2-3-4 trees (these unsuccessful deletions lead to the right red vertices, but a snowball to imbalance the trees and finally dereferencing null pointers). From a review of sample code that discusses LLRB trees and includes options for building trees in any of the modes, it seems that none of them correctly removes from 2-3-4 LLRBs (i.e., none of them have additional rotation, for example, Sedgewick java above and here ).

I am having trouble figuring out what it means by “extra rotation when the right node from the search path is 4-node”; apparently this rotation to the left, but where and when?

If I rotate the left side passing by the 4-node equivalent (i.e. RR node) or the right inclined 3-node equivalent (BR node) either before calling fixUp () or at the end of the fixUp function, I still get the same invariant contradiction.

Here are the states of the tree of the smallest unsuccessful examples that I found (generated by sequentially inserting elements from 0 to the corresponding maximum value).

The first pair of trees shows the transition from a state compatible with the invariant to the removal of element 15 to a clearly broken state after.

The second is essentially the same as above, but with the removal of 16 from 0..16 (removing 15 results in the same topology). Note that the invariant contradiction allows us to cross the root of the node.

The key will be understanding how to reverse the violations generated while walking through the tree to the target node. The next two trees show how the first tree looks from the top after walking down and left and right (without deleting and before going back with fixUp ()).

After trying to remove '-1' without fixUp:

After trying to remove '16' without fixUp:

Trying to turn left for a walk backwards when the node has only the red right child seems to be part of the solution, but it does not work correctly with two red right children in a row, before using flipColor when both children are red, it seems to improve the situation further. but still leave some invariants violated.

If I additionally check whether the right child of the right child is red when his brother is black and rotates to the left, if it is true, I only fail once, but at this moment I feel that I need a new theory, not a new one epicycle.

Any ideas?

For reference, my implementation is available here (No, this is not Java).

Subsequent:

Part of the reason I was interested in this was to confirm many of the claims that 2-3 LLRB trees are more efficient than 2-3-4 LLRB trees. My benchmarking confirmed this for insertion and deletion (2-3 is about 9% faster), but I find that searching is very slightly faster for 2-3-4 trees.

The following points are representative and consistent across all runs:

 BU23: BenchmarkInsert 1000000 1546 ns/op BenchmarkDelete 1000000 1974 ns/op BenchmarkGet 5000000 770 ns/op TD234: BenchmarkInsert 1000000 1689 ns/op BenchmarkDelete 1000000 2133 ns/op BenchmarkGet 5000000 753 ns/op 

The first column is the name of the bench, the second is the number of operations, the third is the result. Test for i5M 2.27.

I looked at the branch lengths for 2-3 trees and 2-3-4 trees, and little can be explained by the difference in search (average distance from root to node and SD of 1000 trees each with 10,000 random inserts):

 Means: TD234 leafs BU23 leafs 12.88940 12.84681 TD234 all BU23 all 11.79274 11.79163 StdDev: TD234 leafs BU23 leafs 1.222458 1.257344 TD234 all BU23 all 1.874335 1.885204 

Answer 1

Updated and verified

The key to testing is that the implementation does not support the removal of a nonexistent or previously deleted node! For too long I tried to find out why my working solution is “broken”. This can be fixed by doing a preliminary key search and returning false if it is not in the tree at all, and this solution was used in the linked code below.

Not displayed. Sedgewick wrote a 2-3-4 removal, which is publicly available. His results relate, in particular, to 2-3 trees (he makes only a superficial mention of 2-3-4 trees in that their average path length (and therefore the cost of the search), like other red-black trees, indistinguishable from 2-3 cases). No one else seems to have found either, so here is what I found after debugging the problem:

To get started, grab the Sedgewick code and fix the obsolete bits. In the slides here (p. 31), you can see that his code still uses the old 4-knot representation where this was done, having two left red ones in a row rather than a balance. The first bit to write a 2-3-4 removal procedure is to fix it so that we can perform a health check that helps us check our fixes later:

 private boolean is234(Node x) { if (x == null) return true; // Note the TD234 check is here because we also want this method to verify 2-3 trees if (isRed(x.right)) return species == TD234 && isRed(x.left); if (!isRed(x.right)) return true; return is234(x.left) && is234(x.right); } 

As soon as we succeed, we will learn a couple of things. Firstly, the article shows that 4 nodes should not be broken when using a 2-3-4 tree. The second is a special case for the right 4-node in the search path. There is a third special case that is not mentioned, and then you return to the tree, you can be where h.right.left is red, which will leave you invalid, just turning left. This is the mirror for the case described for insertion on page 4 of the document.

A rotation fix for 4-node is required:

  private Node moveRedLeft(Node h) { // Assuming that h is red and both h.left and h.left.left // are black, make h.left or one of its children red. colorFlip(h); if (isRed(h.right.left)) { h.right = rotateRight(h.right); h = rotateLeft(h); colorFlip(h); if (isRed(h.right.right) ) h.right = rotateLeft(h.right); } return h; } 

And this removes the splitting by 2-3-4, and also adds a fix for the third special case

 private Node fixUp(Node h) { if (isRed(h.right)) { if (species == TD234 && isRed(h.right.left)) h.right = rotateRight(h.right); h = rotateLeft(h); } if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); if (species == BU23 && isRed(h.left) && isRed(h.right)) colorFlip(h); return setN(h); } 

Finally, we need to check this out and make sure it works. They should not be the most efficient, but, as I discovered during debugging, they should actually work with the expected behavior of the tree (i.e. Do not insert / delete duplicate data)! I did this with test helper methods. The commented lines were there when I debugged, I broke and checked the tree for obvious imbalance. I tried this method with 100,000 nodes and it performed flawlessly:

  public static boolean Test() { return Test(System.nanoTime()); } public static boolean Test(long seed) { StdOut.println("Seeding test with: " + seed); Random r = new Random(seed); RedBlackBST<Integer, Integer> llrb = new RedBlackBST<Integer,Integer>(TD234); ArrayList<Integer> treeValues = new ArrayList<Integer>(); for (int i = 0; i < 1000; i++) { int val = r.nextInt(); if (!treeValues.contains(val)) { treeValues.add(val); llrb.put(val, val); } else i--; } for (int i = 0; i < treeValues.size(); i++) { llrb.delete(treeValues.get(i)); if (!llrb.check()) { return false; } // StdDraw.clear(Color.GRAY); // llrb.draw(.95, .0025, .008); } return true; } 

The full source can be found here .