Понимание того, как прийти к этому рекурсивному решению BST - PullRequest
Новая
       8

Понимание того, как прийти к этому рекурсивному решению BST

0 голосов
/ 28 августа 2018

Начиная с Cracking the Coding Interview, этот код создает двоичное дерево поиска с минимальной высотой (сбалансированной) с учетом отсортированного (в порядке возрастания) массива. 

Node createMinimalBST(int arr[]) {
 return createMinimalBST(array, 0, array.length - 1);
}

Node createMinimalBST(int arr[], int start, int end) {
 if (end < start) {
  return null;
 }

 int mid = (start + end) / 2;
 Node n = new Node(arr[mid]);
 n.left = createMinimalBST(arr, start, mid - 1);
 n.right = createMinimalBST(arr, mid + 1, end);
 return n;
}

Я полностью следую этому коду, но сам не смог придумать это решение.

В частности, после записи значений переменных в пример ввода, хитрость, как представляется, заключается в том, что начало должно быть <= конец. Это гарантирует, что мы вставим значения массива в правильное место, а также завершающие нулевые указатели. Но я действительно поражен тем, как кому-то удалось это выяснить и использовать для написания этой рекурсивной функции. Кто-нибудь может дать представление о том, как они пойдут о получении этого решения? </p>

1 Ответ

0 голосов
/ 29 августа 2018

Я бы подошел к этой проблеме следующим образом. Нам нужно построить BST. Самый очевидный способ построить это сначала выбрать корневой узел. Как мы выбираем это? Итак, мы знаем, что в BST все значения в левом поддереве меньше корневого значения, а все узлы в правом поддереве больше корневого значения. Но у нас есть другое требование - BST должен быть сбалансированным и иметь минимальную высоту. Интуитивно понятно, что это означает, что левое поддерево всего дерева должно быть того же размера, что и правое поддерево, а их высота не должна сильно отличаться (обычно не более чем на единицу). Теперь, как выбрать корневое значение, чтобы примерно половина значений была в левом поддереве (меньше корневого значения), а другая половина - в правом поддереве (больше корневого значения)? Сортируйте все значения и выберите среднее значение в качестве корневого значения. Достаточно удобно, у нас уже есть отсортированные значения. Теперь, когда мы выбрали корневое значение, нам нужно построить левое поддерево и правое поддерево. Как это сделать? Заметьте, что эти две проблемы - фактически та же самая проблема, с которой мы начали, поэтому применяемая нами логика применима. Действительно, у нас есть отсортированный массив (левая половина исходного массива), и нам нужно построить из него сбалансированный BST с минимальной высотой, чтобы сделать все дерево сбалансированным BST с минимальной высотой (аналогично для правой половины). Рассмотрим левую половину исходного массива и выберите его среднее значение как корень левого поддерева (правое поддерево строится аналогичным образом). Теперь мы видим шаблон и можем продолжить рекурсивно, убедившись, что мы возвращаем null, когда массив в рекурсивном вызове становится пустым (сбалансированный BST с минимальной высотой, созданный из пустого массива, является просто нулевым указателем).

...