Rotating a node up a BST depending on the access count to optimize the tree for searching

Question

I have been running into an interesting error while building a "search optimized" BST (each node has an access count identifier). I can successfully move nodes up the tree however, some nodes do not move up the tree as many times as expected.

For example:

When I call my find method on value 1 the tree successfully adjusts and 1 becomes the root. Subsequently when I call the method on 4 the node moves up to be the right child of the root 1.

However, when I call on 5 or 6 the node only rotates upwards once, then the optimization ends.

Here is my code that optimizes the tree, it is called on the root of the tree after a node is found using the find method:

private void RecOptimize(TreeNode<T> currentNode, TreeNode<T> prevNode)
        {
            if (currentNode == null) return;

            RecOptimize(currentNode.left, currentNode);
            RecOptimize(currentNode.right, currentNode);

            var left = currentNode.left;
            var right = currentNode.right;
            var oldNode = currentNode;

            if(right != null)
            {
                if (right.iAccessCount > currentNode.iAccessCount)
                {
                    currentNode = MakeRightRoot(currentNode);
                }
            }
            if(left != null)
            {
                if (left.iAccessCount > currentNode.iAccessCount)
                {
                    currentNode = MakeLeftRoot(currentNode);
                }
            }
            if(prevNode != null)
            {
                if(prevNode.left != null && prevNode.left.Equals(oldNode))
                {
                    prevNode.left = currentNode;
                }

                if(prevNode.right != null && prevNode.right.Equals(oldNode))
                {
                    prevNode.right = currentNode;
                }
            }
            else
            {
                this.rootNode = currentNode;
            }
        }

Edit Thought I would clear something up.

MakeLeftRoot(node) and MakeRightRoot(node) simply perform a rotation about the node, MakeLeftRoot rotates the nodes left node and returns it. While MakeRightRoot does the same but to the right side.

Edit 2 Heres the code for the rotation methods

        protected TreeNode<T> MakeRightRoot(TreeNode<T> oldRoot)
    {
        var newRoot = oldRoot.right;
        oldRoot.right = newRoot.left;
        newRoot.left = oldRoot;
        return newRoot;
    }

    protected TreeNode<T> MakeLeftRoot(TreeNode<T> oldRoot)
    {
        var newRoot = oldRoot.left;
        oldRoot.left = newRoot.right;
        newRoot.right = oldRoot;
        return newRoot;
    }

Answer 1

I will assume all your other code is correct, including the functions that perform rotations. Then there is still this issue in RecOptimize:

If currentNode changes by the call of MakeRightRoot(currentNode), then the left and right variables no longer represent the left and right nodes of currentNode and so the next if block will not be doing what is intended, as at that moment left is a grandchild of currentNode.

I understand why you also pass prevNode to this function, and how the if(prevNode != null) block is dealing with setting the link with prevNode and the potentially changed reference for currentNode, but it will be much easier if you use the same coding pattern as for your rotation functions: let the function return the potentially changed reference for currentNode, and let the caller be responsible for attaching that node back to its parent node.

Also, you should determine whether it is possible that a higher access count occurs in both subtrees of a node or not. If it cannot occur (because after each access you call this function), then you may want to use an if ...else if construct for the two first blocks. If however it could occur, then think how you want the tree to get rotated. I believe it is better to then to deal with each subtree separately: first finish the work for one subtree completely (recursive call + potential rotation), and then only deal with the other subtree (recursive call + potential rotation).

Here is the suggested code:

private TreeNode<T> RecOptimize(TreeNode<T> node) {
    if (node == null) return null;

    if (node.right != null) {
        node = RecOptimize(node.right);
        if (node.right.iAccessCount > node.iAccessCount) {
            node = MakeRightRoot(node);
        }
    }
    if (node.left != null) {
        node = RecOptimize(node.left);
        if (node.left.iAccessCount > node.iAccessCount) {
            node = MakeLeftRoot(node);
        }
    }
    return node;
}

Main call:

this.rootNode = RecOptimize(this.rootNode);

One more comment: RecOptimize is going to visit every node in the tree. This is not optimal. If you access a node through binary search, then you should only have to check for rotations along the path to that found node, as a "bubble up" phase.