Нахождение самого большого поддерева в BST - PullRequest
Новая
       2

Нахождение самого большого поддерева в BST

6 голосов
/ 25 февраля 2010

Учитывая двоичное дерево, я хочу найти самое большое поддерево, которое в нем является BST.

Наивный подход:

Я имею в виду наивный подход, когда я посещаю каждый узел дерева и передаю этот узел функции isBST. Я также буду отслеживать количество узлов в поддереве, если это BST.

Есть ли лучший подход, чем этот?

Ответы [ 9 ]

12 голосов
/ 23 ноября 2010

Я разместил полное решение и объяснение в своем блоге:

http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

Идея состоит в том, чтобы выполнить обход в глубину и передать минимальное и максимальное значения снизу вверх вместо сверху вниз. Другими словами, мы проверяем более глубокие узлы, прежде чем проверять, удовлетворяют ли вышеуказанные узлы требованиям BST.

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

По сравнению с подходом «сверху вниз», подход «снизу вверх» является таким замечательным выбором, потому что результаты по общему количеству узлов могут быть переданы вверх по дереву. Это спасает нас от пересчета снова и снова. Общее количество узлов для поддерева - это просто общее количество узлов его левого и правого поддеревьев плюс один.

Этот алгоритм работает в O (N) временной сложности и O (1) пространстве, что настолько эффективно, насколько это возможно. (где N - общее количество узлов в двоичном дереве).

Ниже приведен код C ++, который работает. Сложной частью реализации является забота о том, как минимальные и максимальные значения передаются снизу вверх. Обратите внимание, что я не инициализировал минимальное и максимальное значения, так как они инициализируются в нижней части дерева. 

// Find the largest BST subtree in a binary tree.
// If the subtree is a BST, return total number of nodes.
// If the subtree is not a BST, -1 is returned.
int findLargestBSTSubtree(BinaryTree *p, int &min, int &max,
                   int &maxNodes, BinaryTree *& largestBST) {
  if (!p) return 0;
  bool isBST = true;
  int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST);
  int currMin = (leftNodes == 0) ? p->data : min;
  if (leftNodes == -1 ||
     (leftNodes != 0 && p->data <= max))
    isBST = false;
  int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST);
  int currMax = (rightNodes == 0) ? p->data : max;
  if (rightNodes == -1 ||
     (rightNodes != 0 && p->data >= min))
    isBST = false;
  if (isBST) {
    min = currMin;
    max = currMax;
    int totalNodes = leftNodes + rightNodes + 1;
    if (totalNodes > maxNodes) {
      maxNodes = totalNodes;
      largestBST = p;
    }
    return totalNodes;
  } else {
    return -1;   // This subtree is not a BST
  }
}

BinaryTree* findLargestBSTSubtree(BinaryTree *root) {
  BinaryTree *largestBST = NULL;
  int min, max;
  int maxNodes = INT_MIN;   // INT_MIN is defined in <climits>
  findLargestBSTSubtree(root, min, max, maxNodes, largestBST);
  return largestBST;
}
8 голосов
/ 25 февраля 2010

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

class TreeNode
{
    public int value;
    public TreeNode left;
    public TreeNode right;
}

void LargestBST(TreeNode bt, IDictionary<TreeNode, bool> isBST, IDictionary<TreeNode, int> nodeCount, ref TreeNode largestBST)
{
    if (bt == null)
        return;
    if (IsBST(bt, isBST) && (largestBST == null || NodeCount(bt, nodeCount) > NodeCount(largestBST, nodeCount)) 
        largestBST = bt;
    else
    {
        LargestBST(bt.left, isBST, nodeCount, ref largestBST);
        LargestBST(bt.Right, isBST, nodeCount, ref largestBST);
    }
}

bool IsBST(TreeNode node, IDictionary<TreeNode, bool> isBST)
{
    if (node == null)
        return true;

    bool result;
    if (!isBST.TryGetValue(node, out result))
    {
        TreeNode maxLeft = Max(node.Left);
        TreeNode minRight = Min(node.Right);
        result = (maxLeft == null || maxLeft.value <= node.value) &&
                 (minRight == null || minRight.value >= node.value) &&
                 IsBST(node.left, isBST) && IsBST(node.Right, isBST);
        isBST.Add(node, result);
    }
    return result;
}

TreeNode Max(TreeNode node)
{
    if (node == null)
        return null;
    while (node.right != null)
        node = node.right;
    return node;
}

TreeNode Min(TreeNode node)
{
    if (node == null)
        return null;
    while (node.left != null)
        node = node.left;
    return node;
}

int NodeCount(TreeNode node, IDictionary<TreeNode, int> nodeCount)
{
    if (node == null)
        return 0;
    int result;
    if (!nodeCount.TryGetValue(node, out result))
    {
        result = 1 + NodeCount(node.left, nodeCount) + NodeCount(node.right, nodeCount);
        nodeCount.Add(node, result);
    }
    return result;
}
2 голосов
/ 25 февраля 2010

Дерево - это BST, если его упорядоченный обход дает вам элементы в отсортированном порядке. Вы можете использовать этот код здесь, если вы хотите пример реализации: http://placementsindia.blogspot.com/2007/12/c-program-to-check-whether-binary-tree.html

Время выполнения O (N), где N = количество узлов.

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

    3
   / \
  2   4
 / \
1  5

Теперь, чтобы получить самое большое поддерево, которое является BST, рассмотрим это дерево: 

    3
   / \
  2   4
 / \
1  5

Обход по порядку равен 1 2 5 3 4. Я думаю, что вы можете решить исходную задачу, найдя отсортированную непрерывную подпоследовательность максимальной длины в обходе по порядку. Вы просто должны быть осторожны, чтобы не выбирать последовательности, которые не описывают BST. Например, для: 

    10
   / \
  2   14
 / \  |
1  5  20

Обход по порядку: 1 2 5 10 20 14. Не выбирайте 20. Я думаю, что это можно сделать, убедившись, что вы отбрасываете элементы, пока их выбор не имеет смысла. Например, когда вы достигнете 14, отклоните 20. Я не уверен, что это можно сделать эффективно, как бы то ни было. Я отредактирую свой пост, если найду точный путь.

1 голос
/ 25 февраля 2010 
int getMinMaxValue(Node* root, bool isMin)
{
   if (!root)
   {
      // Not real limits...
      return (isMin ? INT_MAX : INT_MIN);
   }
   int leftVal = getMinMaxValue(root->left, isMin);
   int rightVal = getMinMaxValue(root->right, isMin);
   if (isMin)
   {
      return min(root->value, min(leftVal, rightVal));
   }
   else
   {
      return max(root->value, max(leftVal, rightVal));
   }
}

bool isBST(Node* root)
{
   if (!root)
   {
      return true;
   }

   Node* left = root->left;
   Node* right = root->right;

   if (left)
   {
      if (getMinMaxValue(left, false) > root->value)
      {
         return false;
      }
   }

   if (right)
   {
      if (getMinMaxValue(right, true) < root->value)
      {
         return false;
      }
   }

   return isBST(left) && isBST(right);
}

Затем просто спустите с корневого узла, проверяя, является ли поддерево BST, и возьмите самое большое.

1 голос
/ 25 февраля 2010

Я думаю, вы могли бы избежать проверки, является ли каждый узел корнем BST, работая сверху вниз, а не снизу вверх. Если поддерево является BST, оно будет больше, чем любое поддерево само по себе, поэтому вам не нужно проверять внутри поддерева, прошло ли оно тест isBST. Тогда вам просто нужно, чтобы isBST возвращал размер действительного дерева и сохранял его вместе с указателем на корень поддерева, если вам нужно будет найти его снова, вместо того, чтобы просто знать, какой из них самый большой.

UPDATE:

Некоторые из кода, размещенного здесь, чтобы проверить, является ли что-то BST, могут потерпеть неудачу в некоторых случаях, так как они проверяют только родительский узел.

Взять, к примеру: 

       10
     /    \
   4      99
          /
         2

Это не действительный BST (2 находится вне позиции по отношению к 10), но если вы не отправите минимальное и максимальное значения вниз по дереву, вы неверно подтвердите его как действительное. Этот псевдокод учитывает это. 

main
{
    Verify(root, MIN_VALUE, MAX_VALUE)
}

boolean Verify(node , min, max)
{

 if(node == null)
   return true;

  if(node.value > min &&
     node.value < max &&
     Verify(node.leftchild, min, node.value) &&
     Verify(node.rightchild,node.value,max)
  {
      return true;
  }
  else
  {
      return false;
  }
}
0 голосов
/ 13 сентября 2013

Для решения вышеуказанной проблемы:

  1. можно сделать обход дерева по порядку
  2. Сохраните его в массиве и найдите «наибольшее отсортированное подмножество».
0 голосов
/ 13 апреля 2013

Одно из возможных решений будет следующим: 

int maxNodes = INT.MIN;
Node* lb = NULL; 
int largesBST(Node* root) { 
    largesBST(root, INT.MIN, INT.MAX);
}

int largesBST(Node* p, int MIN, int MAX) { 
     if(!p) { return 0; } 
     if(p->data > MIN || p->data < MAX) { return -1; }
     int lc = largestBST(p->left, p->data, MAX);
     if(lc == -1) { return -1; } 
     int rc = largestBST(p->right, MIN, p->data);
     if(rc == -1) { return -1; } 
     // At this point, cur node is BST
     int curNodes = lc + rc + 1;
     if(curNodes > maxNodes) { 
        maxNodes = curNodes;
        lb = p;
     }
}
0 голосов
/ 25 января 2013

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

0 голосов
/ 02 мая 2010

Чтобы проверить, является ли узел корнем BST, мы должны рекурсивно проверить каждого левого и правого потомков. Если вы начинаете с корня, вам придется повторить все дочерние процессы, прежде чем вы сможете решить, является ли корень двоичного дерева BST или нет. Поэтому нет смысла вызывать «isBST» для каждого узла. Вот мой подход

  1. Запуск от root
  2. Найти максимум слева и справа
  3. Если не макс на левый и правый возврат "НЕ ЛУЧШИЙ"
  4. если BST слева, проверьте, больше, чем максимум до сих пор. Если да сохранить его и вернуть "НЕ BST"
  5. если BST справа, проверьте, больше, чем максимум до сих пор. Если да сохранить его и вернуть "НЕ BST"
  6. Если левый и правый BST, есть новый BST с текущим рутом в качестве ROOT и с количеством оставленных узлов + правый + 1

Пара трудностей при создании этой работы - это сохранение max, для которого я использовал переменную ref MaxNumNodes. У maxbst withh есть корень самого большого BST, найденного при возврате функции. 

public int MaxBST(Node root, int min, int max, ref Node maxbst, 
        ref int MaxNumNodes)
    {
        if (root == null) return 0;

        //Not a BST
        if (root.data < min || root.data > max) return -1;

        //Find Max BST on left
        int left = MaxBST(root.left, min, root.data, ref maxbst, 
                                    ref MaxNumNodes);
        //Find Max BST on right
        int right = MaxBST(root.right, root.data + 1, max, ref maxbst,
                                            ref MaxNumNodes);

        //Case1: -1 from both branches . No BST in both branches
        if (left == -1 && right == -1) return -1;

        //Case2:No BST in left branch , so choose right 
        //See if the BST on right is bigger than seen so far
        if (left == -1)
        {
            if (right> MaxNumNodes)
            {
                MaxNumNodes = right;
                maxbst = root.right;
            }
            return -1;
        }

        //Case3:No BST in right branch , so choose left 
        //See if the BST on left is bigger than seen so far
        if (right == -1)
        {
            if (left > MaxNumNodes)
            {
                MaxNumNodes = left;
                maxbst = root.left;
            }
            return -1;
        }

        //Case4:Both are BST , new max is left BST + right BST
        maxbst = root;
        return left + right + 1;

    }
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...