Поскольку данное двоичное дерево находит максимальное поддерево двоичного поиска

Интересный вопрос!

Моя более ранняя попытка была ошибочной!

Вот еще одна попытка (надеюсь, исправленная на этот раз).

Я предполагаю, что дерево связано.

Предположим, что для каждого узла n дерева у вас есть набор потомков n, S _n со свойством,

• Для каждого члена x из S _n , уникальный путь от n до x - это двоичное дерево поиска (это всего лишь путь, но вы все равно можете рассматривать его как дерево).

• Для каждого потомка y элемента x, такого что путь от n к y является BST, y находится в S _n .

Набор узлов S _n дает вам самый большой BST с корнем n.

Мы можем построить S _n для каждого узла, выполнив поиск в глубину дерева и передав информацию о пути (путь от корня до текущего узла) и обновив наборы узлов. в пути, возвращаясь по пути.

Когда мы посещаем узел, мы идем вверх по пути и проверяем, удовлетворяется ли свойство BST для этого сегмента пути, пройденного до сих пор. Если это так, мы добавляем текущий узел к соответствующему набору узлов пути, по которому мы только что прошли. Мы прекращаем идти по пути в момент нарушения свойства BST. Проверка того, является ли пройденный нами до сих пор сегмент пути BST, может быть выполнена за время O (1) для общего времени обработки O (path_length) времени для каждого узла.

В конце для каждого узла будет заполнен соответствующий ему S _n . Теперь мы можем пройтись по дереву и выбрать узел с наибольшим значением S _n .

Время, затраченное на это, представляет собой сумму глубин узлов (в худшем случае), и в среднем это составляет O (nlogn) (см. Раздел 5.2.4 в http: // www. toves.org/books/data/ch05-trees/index.html), но O (n ^ 2) в худшем случае.

Возможно, более умный способ обновления наборов гарантирует сокращение времени в худшем случае.

Псевдокод может выглядеть примерно так:

static Tree void LargestBST(Tree t)
{
    LargestBST(t, new List<Pair>());
    // Walk the tree and return the largest subtree with max |S_n|.
}

static Tree LargestBST(Tree t, List<Pair> path)
{
    if (t == null) return;

    t.Set.Add(t.Value);

    int value = t.Value;
    int maxVal = value;
    int minVal = value;

    foreach (Pair p in path)
    {
        if (p.isRight)
        {
            if (minVal < p.node.Value)
            {
                break;
            }
        }

        if (!p.isRight)
        {
            if (maxVal > p.node.Value)
            {
                break;
            }
        }

        p.node.Set.Add(t.Value);

        if (p.node.Value <= minVal)
        {
            minVal = p.node.Value;
        }

        if (p.node.Value >= maxVal)
        {
            maxVal = p.node.Value;
        }
    }

    Pair pl = new Pair();
    pl.node = t;
    pl.isRight = false;

    path.Insert(0, pl);
    LargestBST(t.Left, path);

    path.RemoveAt(0);

    Pair pr = new Pair();
    pr.node = t;
    pr.isRight = true;

    path.Insert(0, pr);

    LargestBST(t.Right, path);

    path.RemoveAt(0);

}

Бинарное дерево поиска даст вам отсортированный результат, если вы выполните обход В ПОРЯДКЕ. Итак, проведем обход всего двоичного дерева по порядку. Самая длинная отсортированная последовательность - это ваше самое большое поддерево двоичного поиска.

• Выполните обход элементов в порядке (ПОСЕТИТЬ ВЛЕВО, ПОСЕТИТЬ КОРНЮ, ПОСЕТИТЬ ВПРАВО)
• При этом получите данные узла, сравните, меньше ли данные предыдущего узла, чем данные следующего. Если да, увеличьте счетчик на 1. Сохраните начальный узел.
• Если сравнение не удается, сохранить конечный узел и сбросить счетчик на 0
• Сохраните эту информацию (счетчик, начало, конец) узла в структуре массива, чтобы позже найти, который имеет максимальное значение, и это даст вам поддерево самого длинного двоичного поиска

GetLargestSortedBinarySubtree(thisNode, ref OverallBestTree)
    if thisNode == null
        Return null
    LeftLargest = GetLargestSortedBinarySubtree(thisNode.LeftNode, ref OverallBestTree)
    RightLargest = GetLargestSortedBinarySubtree(thisNode.RightNode, ref OverallBestTree)
    if LeftLargest.Max < thisNode.Value & RightLargest.Min > thisNode.Value
        currentBestTree = new BinaryTree(LeftLargest, thisNode.Value, RightLargest)
    else if LeftLargest.Max < thisNode.Value
        currentBestTree = new BinaryTree(LeftLargest, thisNode.Value, null)
    else if RightLargest.Min > thisNode.Value
        currentBestTree = new BinaryTree(null, thisNode.Value, RightLargest)
    else
        currentBestTree = new BinaryTree(null, thisNode.Value, null)
    if (currentBestTree.Size > OverallBestTree.Size)
        OverallBestTree = currentBestTree
    return currentBestTree

Как указал BlueRaja, этот алгоритм неверен.

На самом деле он должен называться GetLargestSortedBinarySubtreeThatCanBeRecursivelyConstructedFromMaximalSortedSubtrees .

root(Tree L A R) = A

MaxBST(NULL) = (true, 0, NULL)
MaxBST(Tree L A R as T) = 
  let
    # Look at both children
    (L_is_BST, L_size, L_sub) = MaxBST(L)
    (R_is_BST, R_size, R_sub) = MaxBST(R)
  in
  # If they're both good, then this node might be good too
  if L_is_BST and R_is_BST and (L == NULL or root(L) < A) and (R == NULL or A < root(R))
  then (true, 1 + L_size + R_size, T)
  else
       # This node is no good, so give back the best our children had to offer
       (false, max(L_size, R_size), if L_size > R_size then L_sub else R_sub)

Проверяет каждый узел дерева ровно один раз, поэтому выполняется за O (N).

Edit: Crud, это не учитывает, что он может пропустить некоторые части поддерева. Когда я читал поддерево, я предполагал, что «все дерево укоренено в каком-то узле». Я могу вернуться, чтобы исправить это позже.

Предыдущий алгоритм (см. изменения) был O(n^2) - мы можем обобщить его до O(n log n), заметив следующие факты:

1. Если b - корень наибольшего BST и b.left. value < b.value, то b.left также находится в BST (то же самое для b.right.value ≥ b.value)
2. Если b является корнем наибольшего BST и a также находится в BST, то каждый узел между a и b находится в BST.

Поэтому если c находится между a и b, и c не входит в BST, корнем которого является b, то и a не входит (в силу (2.)). Используя этот факт, мы можем легко определить, находится ли узел в BST с корнем от любого данного предка. Для этого мы передадим узел в нашу функцию вместе со списком его предков и соответствующими min/maxValues, которым должен удовлетворять текущий дочерний узел, если этот предок действительно является корнем наибольшего BST (мы назовем этот список ancestorList). Всю коллекцию потенциальных корней будем хранить в overallRootsList

Определим структуру под названием potentialRoot следующим образом:

Каждый potentialRoot содержит следующие значения:
* node: Узел, который мы рассматриваем в качестве корня BST
* minValue и maxValue: диапазон, в который должен попасть другой узел, чтобы стать частью BST, корнем которого является узел (для каждого узла свой)
* subNodes: Список остальных узлов в самом большом BST, укорененном узлом

Псевдокод выглядит следующим образом (обратите внимание, что все упомянутые списки являются списками потенциальных корней):

FindLargestBST(node, ancestorList):
    leftList, rightList = empty lists
    for each potentialRoot in ancestorList:
        if potentialRoot.minValue < node.Value ≤ potentialRoot.maxValue:
            add node to potentialRoot.subNodes (due to (1.))
            (note that the following copies contain references, not copies, of subNodes)
            add copy of potentialRoot to leftList, setting maxValue = node.Value
            add copy of potentialRoot to rightList, setting minValue = node.Value

    add the potentialRoot (node, -∞, +∞) to leftList, rightList, and overallRootsList
    FindLargestBST(node.left, leftList)
    FindLargestBST(node.right, rightList)

В конце overallRootsList будет список n потенциальных корней, каждый из которых имеет список подузлов. Тот, у которого список subNodes больше всего, является вашим BST.

Поскольку в ancestorList существует < значений treeHeight, то (предполагая, что дерево сбалансировано) алгоритм выполняется за O(n log n)