根据访问计数将节点向上旋转 BST 以优化搜索树

Question

我在构建“搜索优化”BST（每个节点都有一个访问计数标识符）时运行遇到了一个有趣的错误。我可以成功地将节点向上移动树但是，有些节点没有像预期的那样多次向上移动树。

例如：

当我在值 1 上调用我的查找方法时，树成功调整并且 1 成为根。随后，当我在 4 上调用方法时，节点向上移动成为根 1.

的右子节点

然而，当我调用5或6时，节点只向上旋转一次，然后优化结束。

这是我优化树的代码，在使用 find 方法找到节点后在树的根上调用它：

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;
            }
        }

编辑以为我会清理一些东西。

MakeLeftRoot(node) 和 MakeRightRoot(node) 只是围绕节点执行旋转，MakeLeftRoot 将节点向左旋转，returns 旋转。虽然 MakeRightRoot 做同样的事情，但在右侧。

编辑 2 这是旋转方法的代码

        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

我将假定您的所有其他代码都是正确的，包括执行旋转的函数。然后在RecOptimize:

中还有这个问题

如果currentNode被MakeRightRoot(currentNode)的调用改变了，那么left和right变量就不再代表currentNode的左右节点了因此下一个 if 块将不会按预期执行，因为在那一刻 left 是 currentNode.

的孙子

我明白你为什么还要将 prevNode 传递给此函数，以及 if(prevNode != null) 块如何处理将 link 设置为 prevNode 和可能更改的引用对于 currentNode，但如果您使用与旋转函数相同的编码模式，将会容易得多：让函数 return 可能已更改的参考 currentNode，并让调用者负责将该节点附加回其父节点。

此外，您应该确定是否有可能在节点的两个子树中出现更高的访问计数。如果它不会发生（因为在每次访问后调用此函数），那么您可能希望对前两个块使用 if ...else if 构造。但是，如果它可能发生，那么请考虑您希望如何旋转树。我认为最好然后分别处理每个子树：首先完全完成一个子树的工作（递归调用+潜在旋转），然后 then 只处理另一个子树（递归看涨+潜在轮换）。

这里是建议的代码：

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;
}

主要调用：

this.rootNode = RecOptimize(this.rootNode);

还有一条评论：RecOptimize 将访问树中的每个节点。这不是最佳的。如果您通过二进制搜索访问一个节点，那么您应该只需要检查沿找到该节点的路径的旋转，作为“冒泡”阶段。

根据访问计数将节点向上旋转 BST 以优化搜索树

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

c#

data-structures

binary-search-tree