二叉搜索树平衡

Question

我正在研究一个 BST，它将根据节点的命中及其元素来平衡节点，其中命中是一个属性，当使用 find()、contains() 等找到节点时会增加。树的根是命中次数最多的节点。我的所有代码都没有问题，除了在我增加命中后平衡树的平衡方法。我正在使用修改后的 AVL 树旋转方法 (https://users.cs.fiu.edu/~weiss/dsj2/code/weiss/nonstandard/Rotations.java)，我不比较元素，而是比较节点的命中。无论我尝试什么，我都无法让它工作，我无法让树正确平衡到目前为止，这是我的代码：

 public void balanceTree() {
    balanceTree(root);
}

private void balanceTree(Node node) {

    if (node.left.getHits() <= node.getHits() && node.right.getHits() <= node.getHits()) {
        return;
    } else if (node.left.getHits() > node.getHits()) {
        node = rotateWithLeftChild(node);

    } else if (node.right.getHits() > node.getHits()) {
        node = rotateWithRightChild(node);

    }


}

static Node rotateWithLeftChild(Node k2) {
    Node k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;
    return k1;
}

static Node rotateWithRightChild(Node k1) {
    Node k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;
    return k2;
}

现在平衡方法只是删除了它应该旋转的节点，我尝试调试它但看不出有什么问题。

Answer 1

这段代码有两处错误。
1) 我想念这棵树的结构。所以他们需要根据他们的 hitCount 进行排序，基本上是不是 List/Collection 按 hitCount 排序？

现在，如果他们的 hitCount 比他们自己高，您正在用他们的左节点和右节点交换节点。所以想象一下 2 个节点 [A, B] A 有 1 个 hitCount，B 有 2 个 hitCount。所以在排序时（你可能会迭代节点）：
开始情况：[A, B]

第一类： A 的 hitCount 比 B 低，所以用 right 交换。结果 = [B, A]

第二类： A 的 hitCount 比 B 低，因此与 left 交换。结果 = [A, B]

我们在哪里结束？一个更好的主意可能是使用一个列表并根据它们的 hitCount 对节点进行排序。这样你就不必搞砸了。

2) 您的交换方法并不像您认为的那样有效。仔细看看这个：

 static Node rotateWithLeftChild(Node k2) {
     Node k1 = k2.left;
     k2.left = k1.right;
     k1.right = k2;
     return k1;
 }

 // exact the same results:
 static Node rotateWithLeftChild(Node k2)
 {
     k2.left = k2;
     return k2.left;
 }

我觉得不对。可能你的意思是：

 static Node rotateWithLeftChild(Node k2)
 {
     Node k1 = k2.left;
     k1.right = k2.right;
     k2.left = k1.left;
     k1.left = k2;
     k2.right = k1;
     return k1;
 }

当然 "rotateWithRightChild" 正好相反。

希望对您有所帮助。

编辑：

如何实现订单List/Collection？将节点添加到树后，只需将节点添加到 Lisf/Collection。当你想对节点进行排序时，只需使用这个：

 //myNodesCollection is the List/Collection containing all the nodes.
 static void sortByHitCount()
 {
     Collections.sort(myNodesCollection, (n1, n2) -> n1.getHits() - n2.getHits());
 }

这可能看起来很复杂，但这是一种为您完成所有排序的方法。第一个参数是你要排序的List/Collection。第二个参数是一个比较器，在这种情况下，它根据每个节点的 hitCount 进行比较。

文档：https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

Answer 2

在java中无法更改传递的参数，因此需要return新的节点值。

public void balanceTree() {
    root = balanceTree(root);
}

private Node balanceTree(Node node) 
    if (node.left.getHits() <= node.getHits()
            && node.right.getHits() <= node.getHits()) {
        node.left = balanceTree(node.left);
        node.right = balanceTree(node.right);
    } else if (node.left.getHits() > node.getHits()) {
        node = rotateWithLeftChild(node);
    } else if (node.right.getHits() > node.getHits()) {
        node = rotateWithRightChild(node);
    }
    return node;
}

假设您在每次插入后重新平衡树，那么不需要在旋转后递归来平衡子树。

没有循环就需要递归

目前的算法是先左后右递归，但是如果在左边发生了旋转，那么右子树可能就不再递归了。

这种修改算法更令人担忧的是它可能不稳定：保持重新平衡。但是您肯定会在测试中发现这一点。

二叉搜索树平衡

Binary Search Tree balance

java

binary-search-tree

tree-balancing