Как проверить, сортируется ли B-дерево

Question

У меня просто было это как вопрос для интервью, и мне было интересно, знает ли кто-нибудь ответ?

Напишите метод, который проверяет правильность сортировки B-дерева. Вам не нужно проверять, сбалансировано ли дерево . Используйте следующую модель для узла в B-дереве.

Это должно было быть сделано в Java и использовать эту модель:

class Node { 
List<Integer> keys; 
List<Node> children; 
} 

Answer 1

Один (космос-неэффективна, но простой) способ сделать это, чтобы сделать обобщенный Симметричного обходом 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) и использует пространство О (п), где п число элементов в B-дереве. Вы можете сократить использование пространства до O (h), где h - высота B-дерева, не сохраняя все элементы в обходе и вместо этого просто отслеживая последний, останавливая поиск раньше, встречающееся значение не больше предыдущего. Я не делал этого здесь, потому что он требует больше кода, но концептуально это не слишком сложно.

Надеюсь, это поможет!