Нахождение минимального значения дерева 2-3-4
-
20-12-2019 - |
Вопрос
Во-первых, этот вопрос не является домашним заданием.Сейчас я читаю книгу Роберта Лафора "Структуры данных и алгоритмы, 2-е издание".В главе 10 мы узнали о 2-3-4 деревьях, а затем нас попросили написать метод для нахождения минимального значения в указанном дереве.
С точки зрения концепции, я понимаю, где находится минимальное значение.Это просто самый левый элемент данных на листе.
С точки зрения программирования, я немного запутался в том, как реализовать метод поиска этого элемента данных.У меня есть логическое значение, которое может определить, является ли узел листом.Итак, то, что я изначально сделал, было следующим:
public long minValue() {
Node curNode = root; // current node = root
long min = curNode.getMin();
while(!curNode.isLeaf()) { // while current node is NOT a leaf
curNode = getNextChild(curNode, min);
} // end while
return min;
} // end minValue()
Что это делает (по крайней мере, я думаю, что это должно делать), так это создает curNode, который начинается с корневого узла.Затем создайте минимальное значение, в котором хранится curNode.getMin.getMin() просто получает значение в массиве с индексом 0 (где должно храниться наименьшее значение).Затем, пока текущий узел не является конечным, мы должны перейти к следующему дочернему узлу от минимальной точки.Как только текущий узел становится конечным, он должен возвращать минимальное значение.
Однако это не работает.Есть ли у кого-нибудь идея о том, как это реализовать?Намеки, предложения или что-нибудь еще?
Редактировать:Чтобы ознакомиться с каждым из классов и с тем, как они взаимодействуют, вот ссылки на каждый отдельный класс.Я поместил метод минимального значения в свой класс Tree234
Элемент данных, Узел, Дерево 234, и где выполняется программа, Tree234App
Решение
Во-первых, чтобы быстрее получить лучшую помощь, опубликуйте SSCCE это дает нам минимальную реализацию всей вашей программы - то, что мы можем скопировать в нашу собственную среду IDE и запустить сами, чтобы посмотреть, что происходит.Трудно сказать, почему "это не работает", когда мы видим только этот фрагмент вашего кода.
Во-вторых, вам нужно уточнить, что означает "это не работает", т.е.расскажите нам точно, что он делает или не делает такого неожиданного.Вместо того, чтобы вы это сделали, как мы могли бы сказать вам с какой-либо степенью уверенности, почему он это делает?
Однако, одна вещь бросается в глаза:Вы создаете экземпляр min
как наименьший (прямой) дочерний элемент корневого узла, затем (предположительно) перебираете дерево, чтобы найти в нем самый левый элемент, но затем вы возвращаете то же самое min
значение, которое вы создали изначально.Другими словами, в то время как ваша итеративная процедура может выполнять именно то, что вы от нее хотите, в результате вы ничего не делаете с возвращаемым значением.
Я подозреваю, что вам нужно сделать что-то вроде:
public long minValue() {
Node curNode = root;
long min = curNode.getMin();
while(!curNode.isLeaf()) { //
curNode = getNextChild(curNode, min); //it's not immediately clear what min is doing here
}
//curNode is now the leftmost non-leaf element in the tree
min = curNode.getMin();
return min;
Обратите внимание, что единственным изменением, которое я внес, была вставка строки над оператором return, который переназначает min
к минимальному значению, привязанному к самому левому элементу в дереве.
Другие советы
Для большей эффективности обратите внимание, что вам не нужно вызывать getNextChild(curNode, min)
, поскольку элементы в узле всегда сортируются в порядке возрастания в дереве 2-3-4, а наименьший элемент всегда находится в индексе 0
.При запуске также не требуется указывать значение min.Таким образом, ваша программа могла бы быть такой:
public long minValue() {
Node curNode = root;
while (!curNode.isLeaf()) {
curNode = curNode.getChild(0);
}
return curNode.getMin();
}