0

我正在研究一个 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;
}

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

4

2 回答 2

0

在java中不能改变传递的参数，所以需要返回新的Node值。

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

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

没有旋转就需要递归。

当前算法向左然后向右递归，但如果在左侧发生旋转，则右子树可能不再递归。

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

于 2016-10-23T19:53:31.163 回答
0

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

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

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

第二类：A 的 hitCount 比 B 低，所以与左交换。结果 = [A, B]

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

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”则相反。

我希望这对你有所帮助。

编辑：

如何实现订单列表/集合？将节点添加到树后，只需将节点添加到 Lisf/Collection。当您想要对节点进行排序时，只需使用以下命令：

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

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

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

于 2016-10-23T19:35:52.803 回答