Подсчет Трепов

Question

Рассмотрим проблему подсчета числа структурно различных деревьев двоичного поиска :

Учитывая N, найдите количество структурно различных деревьев двоичного поиска, содержащих значения 1 .. N

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

countBST(numKeys)
    if numKeys <= 1
        return 1
    else
        result = 0
        for i = 1 .. numKeys
            leftBST = countBST(i - 1)
            rightBST = countBST(numKeys - i)

            result += leftBST * rightBST

        return result

Недавно я ознакомился с ловушками , и я поставил перед собой следующую проблему:

Учитывая N, найдите количество различных трэпов, содержащих значения 1 .. N с приоритетами 1 ... N. Два трепа различны, если они структурно отличаются от ЛЮБОГО ключа ИЛИ приоритета (читайте дальше для пояснения).

Я пытался выяснить формулу или алгоритм, который может решить эту проблему некоторое время, но я не добился успеха. Это то, что я заметил, хотя:

1. Ответы на n = 2 и n = 3 кажутся 2 и 6, основываясь на том, что я рисовал деревья на бумаге.
2. Если мы игнорируем часть, в которой говорится, что трепы могут также отличаться относительно приоритета узлов, проблема, похоже, идентична подсчету только двоичных деревьев поиска, поскольку мы сможем назначить приоритеты каждому BST так, чтобы это также уважает инвариант кучи. Хотя я этого не доказал.

3. Я думаю, что самая сложная часть заключается в возможности перестановки приоритетов без изменения структуры. Например, рассмотрим этот трэп, где узлы представлены в виде (key, priority) пар:

             (3, 5)
             /    \ 
        (2, 3)    (4, 4)
        /              \
   (1, 1)               (5, 2)
   

   Мы можем переставлять приоритеты как второго, так и третьего уровней, сохраняя при этом инвариант кучи, поэтому мы получаем больше решений, даже если никакие ключи не меняются местами. Это, вероятно, становится еще хуже для больших деревьев. Например, этот треп отличается от приведенного выше:

             (3, 5)
             /    \ 
        (2, 4)    (4, 3) // swapped priorities
        /              \
   (1, 1)               (5, 2)
   

Буду признателен, если кто-нибудь сможет поделиться какими-либо идеями о том, как подойти к этому. Это казалось интересной проблемой подсчета, когда я думал об этом. Может быть, кто-то еще думал об этом и даже решил это!

Answer 1

Интересный вопрос!Я считаю, что ответ N факториален!

Учитывая древовидную структуру, есть только один способ заполнить значения ключа бинарного дерева поиска.

Таким образом, все, что нам нужно сделать, это подсчитать разныеколичество куч.

Учитывая кучу, рассмотрим обход дерева по порядку.

Это соответствует перестановке чисел от 1 до N.

Теперь данолюбая перестановка {1,2 ..., N}, вы можете построить кучу следующим образом:

Найти положение самого большого элемента.Элементы слева образуют левое поддерево, а элементы справа образуют правое поддерево.Эти поддеревья формируются рекурсивно путем нахождения самого большого элемента и расщепления там.

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

Таким образом, требуемое число - N!.

Например:

    5
   / \
  3   4          In-order traversal ->   35142
     / \ 
     1  2

Теперь начните с 35142. Самое большое - 5, поэтому 3 - это левое поддерево, а 142 -right.

    5
   / \
  3  {142}

В 142 4 является наибольшим, а 1 - левым, а 2 - правым, поэтому мы получаем

    5
   / \
  3   4
     / \
    1   2

Единственный способ заполнить двоичные ключи поиска для этого:

    (2,5)
   /     \
(1,3)    (4,4)
        /     \
       (3,1)   (5,2)

---

Для более формального доказательства:

Если H _N - это количество куч на 1 ... N, то имеем

H _N = сумма_ {L = от 0 до N-1} H _L * H _N-1-L * (N-1 выберите L)

(в основном мы выбираем максимальное значение и назначаем root. Выберите размер левого поддерева, а затем выберите столько элементов и рекурсив слева и справа).

Теперь,

H0 = 1
H1 = 1
H2 = 2
H3 = 6

Если H _n = n!для 0 ≤ n ≤ k

Тогда H _{K + 1} = Sum_{L=0 to K} L! * (K-L)! * (K!/L!*(K-L)!) = (K+1)!

Answer 2

def countBST(numKeys:Long):Long = numKeys match {
  case 0L => 1L
  case 1L => 1L
  case _ => (1L to numKeys).map{i=>countBST(i-1) * countBST(numKeys-i)}.sum
}

Вы фактически не определили структурное сходство для ловушек - вы просто привели примеры.Я собираюсь принять следующее определение: два дерева структурно различны тогда и только тогда, когда они имеют различную форму, или существуют узлы a (из дерева A) и b (из дерева B), такие что a и b находятся вта же позиция, и приоритеты детей а находятся в порядке, обратном приоритетам детей б.(Очевидно, что если два трэпа с одинаковыми значениями имеют одинаковую форму, то значения в соответствующих узлах одинаковы.)

Другими словами, если мы визуализируем два дерева, просто давая приоритеты на узлахследующие два дерева структурно схожи:

      7               7
   6      5        6      5
  4 3    2 1      2 1    4 3  <--- does not change the relative order
                                   of the children of any node
                                   6's left child is still greater than 6's right child
                                   5's left child is still greater than 5's right child

, но следующие два дерева структурно различны:

      7               7
   5      6        6      5   <--- changes the relative order of the children
  4 3    2 1      4 3    2 1       of node 7

Таким образом, для задачи Treap каждый внутренний узел имеет 2 порядка, иэти два порядка никак не влияют на форму дерева.Итак ...

def countTreap(numKeys:Long):Long = numKeys match {
  case 0L => 1L
  case 1L => 1L
  case _ => 2 * countBST(numKeys-1) +  //2 situations when the tree has only 1 child
            2 * (2L to (numKeys-1)).map{i=>countBST(i-1) * countBST(numKeys-i)}.sum
            // and for each situation where the tree has 2 children, this node  
            // contributes 2 orderings the priorities of its children
            // (which is independent of the shape of the tree below this level)
}