Учитывая сбалансированный BST. мин, макс и значение, как вы можете найти самый большой Xor в мин и макс? - PullRequest
Новая
       38

Учитывая сбалансированный BST. мин, макс и значение, как вы можете найти самый большой Xor в мин и макс?

3 голосов
/ 01 марта 2012

В основном у вас есть BST, заполненный значениями.например.1-16 мин, максимум и значение (10,15,3), и вам нужно найти максимальное значение xor между значениями в BST и заданным значением, которые находятся в пределах мин и макс дерева.

Мне интересно, есть ли способ сделать это без итерации по всему дереву.если бы мин и макс не существовало, мой подход был бы следующим: 

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

В основном следите за узлами, которые производят более высокие значения xor.

Проблема, с которой я сталкиваюсь с min иmax, когда я помещаю проверки для узла> = min && node <= max, дерево будет проходить нормально, но когда я нахожусь в пределах диапазона, возможно, что я получаю плохую ветвь для числа вне диапазона.</p>

Позвольте мне объяснить.Возьмите эту правую сторону от BST 1-16 

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

учитывая:

  • min = 10
  • max = 15
  • value =3

Максимальное значение Xor равно 3^12=15

Однако с моим алгоритмом, когда я нахожусь на 13 узле, вместо того, чтобы поднять левое дерево к 11, явзяв правильное дерево до 15 (потому что оно пытается получить 16, но это вне диапазона).

У кого-нибудь есть лучшее решение?я должен сортировать мой BST по-другому?Должен ли я использовать что-то вместо BST?Можно ли сделать это, не обходя весь список значений?Здесь предполагается, что у меня будет один список значений (те, что я положил в свой BST), а затем список параметров (min, max, value), которые я должен применить к списку значений.

1 Ответ

1 голос
/ 14 марта 2012

Мое предложение состояло бы в том, чтобы следовать подходу, подобному этому ответу на другой вопрос:

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

Хотя одной из проблем является то, что вы не используете тот факт, что все элементы уже вставлены в дерево.

Или, может быть, вместо двоичного дерева вы могли бы построить дерево, которое моделирует дерево рекурсии с последующим решением? Просто мои 2 цента:)

...