У меня был этот вопрос на собеседовании, и мне было интересно, знает ли кто-нибудь ответ?
Напишите метод, который проверяет, правильно ли отсортировано B-дерево. Вам НЕ нужно проверять, сбалансировано ли дерево. Используйте следующую модель для узла в B-дереве.
Это должно было быть сделано на Java и использовать эту модель:
class Node {
List<Integer> keys;
List<Node> children;
}
Один (неэффективный, но простой) способ сделать это - выполнить обобщенный обход B-дерева в порядке, чтобы вернуть ключи в том порядке, в котором следует отсортировать, а затем проверить, действительно ли эта последовательность находится в отсортированном порядке. Вот небольшой код для этого:
public static boolean isSorted(Node root) {
ArrayList<Integer> values = new ArrayList<Integer>();
performInorderTraversal(root, values);
return isArraySorted(values);
}
private static void performInorderTraversal(Node root, ArrayList<Integer> result) {
/* An empty tree has no values. */
if (result == null) return;
/* Process the first tree here, then loop, processing the interleaved
* keys and trees.
*/
performInorderTraversal(root.children.get(0), result);
for (int i = 1; i < root.children.size(); i++) {
result.add(root.children.get(i - 1));
performInorderTraversal(root.children.get(i), result);
}
}
private static boolean isArraySorted(ArrayList<Integer> array) {
for (int i = 0; i < array.size() - 1; i++) {
if (array.get(i) >= array.get(i + 1)) return false;
}
return true;
}
Это занимает время O (n) и использует пространство O (n), где n - количество элементов в B-дереве. Вы можете сократить использование пространства до O (h), где h - высота B-дерева, не сохраняя все элементы в обходе, а вместо этого просто отслеживая самый последний, останавливая поиск раньше, если следующий- встреченное значение не больше предыдущего. Я не делал этого здесь, потому что для этого требуется больше кода, но концептуально это не так уж сложно.
Надеюсь это поможет!
