3

基本上你有一个充满值的 BST。例如。1-16 a min,max and value (10,15,3) 并且您需要找到 BST 中的值与树的 min 和 max 内的给定值之间的最大异或值。

我想知道是否有一种方法可以在不遍历整个树的情况下做到这一点。如果 min 和 max 不存在，我的方法是。

int xor (Node curent,min,max,value,highestXor){
 1. if node == null return highestXor
 2. check node.value ^ value, if > highestXor replace.
 3. check node.left ^ value and node.right ^ value, nextNode= highest between them 
 4. xor(nextNode,min,max,value,newHighest)
}

基本上继续关注产生更高异或值的节点。

我在使用 min 和 max 时遇到的问题是，当我对 node>=min && node<=max 进行检查时，树会很好地遍历，但是当我在范围内时，我可能会采取错误分支到范围之外的数字。

让我解释。采取 BST 1-16 的右侧

      9 
    /   \
  /       \
5           13
           /   \
         11     15
         /\     /\
       10  12 14  16

给定：

  • 最小值 = 10
  • 最大值 = 15
  • 值 = 3

最大异或值为3^12=15

然而，使用我的算法，当我在 13 节点时，我没有将左树带到 11，而是将右树带到 15（因为它试图达到 16，但那超出了范围）。

有没有人有更好的解决方案？我应该对我的 BST 进行不同的排序吗？我应该使用什么东西而不是 BST 吗？是否可以在不遍历整个值列表的情况下执行此操作？这里的假设是我将有一个值列表（我放入 BST 中的那些），然后是我必须应用于值列表的参数列表（最小值、最大值、值）。

4

1 回答 1

1

我的建议是采用与另一个问题的答案类似的方法：

https://stackoverflow.com/a/9320467/1015955

虽然，这样做的一个问题是您没有使用所有元素都已插入树中的事实。

或者，也许，您可以构建一棵树来模拟递归树，而不是二叉树，然后是上述解决方案？只是我的 2 美分 :)

于 2012-03-14T05:54:44.700 回答