Для заданного двоичного дерева найдите максимальное дерево двоичного поиска

Question

Для заданного двоичного дерева найти наибольшее поддерево, которое также является двоичным деревом поиска?

Пример:

Ввод:

                   10
               /         \
             50           150
            /  \         /   \
          25    75     200    20
         / \   / \    /  \    / \
        15 35 65 30  120 135 155 250 

Выход:

                   50
                  /   \
                 25   75
                / \   /
               15 35  65

Answer 1

Этот ответ ранее содержал алгоритм O (n log n), основанный на деревьях ссылок / разрезов.Вот более простое решение O (n) .

Ядро - это процедура, которая принимает узел, уникальный максимум BSST с корнем у его левого потомка, уникальный максимум BSST с корнем у него справаchild, и указатели на самый левый и самый правый элементы этих BSST.Он уничтожает свои входные данные (которых можно избежать с помощью постоянных структур данных) и создает уникальный максимальный BSST, укорененный в данном узле, вместе с его минимальным и максимальным элементами.Все узлы BSST помечены числом потомков.Как и прежде, эта процедура вызывается повторно из обхода после заказа.Чтобы восстановить поддерево, запомните корень самого большого BSST;реконструкция требует только простого обхода.

Я буду лечить только левый BSST;право симметрично.Если корень левого BSST больше, чем новый корень, то удаляется все поддерево, и новый корень теперь является самым левым.В противном случае старый левый узел все еще остается самым левым.Начиная с самого правого узла левого BSST и двигаясь вверх, найдите первый узел, который меньше или равен корню.Его правильный ребенок должен быть удален;теперь обратите внимание, что из-за свойства BST другие узлы не нужны! Перейдите к корню левого BSST, обновив счетчики, чтобы отразить удаление.

Причина в том, что O(n) заключается в том, что, несмотря на цикл, каждое ребро в исходном дереве, по сути, пройдено только один раз.

---

РЕДАКТИРОВАТЬ: вместе, пройденные пути являются максимальными прямыми путями в BSTкроме левого и правого позвоночника.Например, на входе

              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / \             / \
    /   \           /   \
   /     \         /     \
  B       F       J       N
 / \     / \     / \     / \
A   C   E   G   I   K   M   O

приведены рекурсивные вызовы, по которым проходит каждое ребро:

              H
             / \
            /   \
           /     \
          /       \
         /         \
        /           \
       /             \
      D               L
     / h             h \
    /   h           h   \
   /     h         h     \
  B       F       J       N
 / d     d h     h l     l \
A   C   E   G   I   K   M   O

Answer 2

Предыдущий алгоритм (см. Редакции) был 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

. Давайте определим структуру под названием потенциалRoot следующим образом:

Каждый потенциалRoot содержит следующеезначения:
* узел : узел, который мы рассматриваем для корня 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потенциалRoots, каждый со списком подузлов.Тот, у кого самый большой список подузлов, - это ваш BST.

Поскольку в ancestorList есть значения O(n log n)

Answer 3

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

Моя предыдущая попытка была глупой!

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

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

Предположим, что для каждого узла 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 ( п ^ 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);

}

Answer 4

КРУПНЕЙШИЙ БИНАРНЫЙ ПОИСК ДЕРЕВА В БИНАРНОМ ДЕРЕВЕ:

Есть два способа решения этой проблемы:

i) Самый большой BST не индуцирован (От узла все его дочерние элементы не должны удовлетворять условию BST)

ii) Наибольший индуцированный BST (из узла все его дочерние элементы будут удовлетворять условию BST)

Мы поговорим о самом большом BST (не индуцированном) здесь. Для решения этой проблемы мы будем использовать подход «снизу вверх» (обратный заказ).

а) Достичь листового узла

b) Узел дерева (из листа) вернет объект TreeNodeHelper, в котором есть следующие поля.

public static class TreeNodeHelper {
        TreeNode node;
        int nodes;
        Integer maxValue;
        Integer minValue;
        boolean isBST;


        public TreeNodeHelper() {}

        public TreeNodeHelper(TreeNode node, int nodes, Integer maxValue, Integer minValue, boolean isBST) {
            this.node = node;
            this.nodes = nodes;
            this.maxValue = maxValue;
            this.minValue = minValue;
            this.isBST = isBST;
        }      
    }

в) Первоначально из конечного узла node = 1 isBST = true, minValue = maxValue = node.data. Кроме того, количество узлов будет увеличено, если оно удовлетворяет условию BST.

d) С помощью этого мы проверим состояние BST с текущим узлом. И мы повторим то же самое до корня.

e) Из каждого узла будут возвращены два объекта. один для последнего максимального BST и еще один для текущих узлов, удовлетворяющих BST. Таким образом, из каждого узла (над листом) (2 + 2) = 4 (2 для левого поддерева и 2 для правого поддерева) будут сравниваться объекты и возвращаться два.

f) Последний максимальный объект узла от root будет самым большим BST

ПРОБЛЕМА:

В этом подходе есть проблема. Следуя этому подходу, если поддерево не удовлетворяет условию BST с текущим узлом, мы не можем просто проигнорировать поддерево (даже если оно имеет меньшее количество узлов). Например

 55
  \
   75
  /  \
 27  89
    /  \
   26  95
      /  \
     23  105
         /  \
        20  110

Из листовых узлов (20,110) объекты будут проверены с помощью узла (105), он удовлетворяет условию. Но когда он достигает узла (95), листовой узел (20) не удовлетворяет условию BST. Поскольку это решение для BST (не индуцировано), мы не должны игнорировать узел (105) и узел (110), который удовлетворяет условию. Таким образом, из узла (95) мы должны вернуться назад, проверяя состояние BST, и перехватить эти узлы (105, 110).

Полный код для этой реализации доступен по этой ссылке

https://github.com/dineshappavoo/Implementation/tree/master/LARGEST_BST_IN_BT_NOT_INDUCED_VER1.0

Answer 5

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).

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

Answer 6

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.

Answer 7

Двоичное дерево поиска даст вам отсортированный результат, если вы выполните обход IN-ORDER. Итак, выполните обход по порядку для всего двоичного дерева. Самая длинная отсортированная последовательность - это ваше наибольшее поддерево поиска.

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