基本上你有一个充满值的 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 中的那些),然后是我必须应用于值列表的参数列表(最小值、最大值、值)。