Нахождение минимального значения 2-3-4 дерева

Во-первых, этот вопрос не домашнее задание. В настоящее время я читаю книгу Роберта Лафора "Структуры данных и алгоритмы, 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

DataItem, Node, Tree234 и где запускается программа Tree234App

Источник

2 ответа

Решение

Во-первых, чтобы лучше помогать быстрее, опубликуйте 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, Декларация мин также не требуется при запуске. Итак, ваша программа может быть такой:

public long minValue() {
    Node curNode = root;
    while (!curNode.isLeaf()) {
        curNode = curNode.getChild(0);
    }
    return curNode.getMin();
}
Источник
Другие вопросы по тегам