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

Ответ 1

Мы можем решить это с помощью умного рекурсивного алгоритма.

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

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

              v
             / \
            L   R

Здесь v - корень, а L и R - правые поддеревья соответственно.

Если мы хотим создать это двоичное дерево поиска, нам нужно будет начать сначала вставлять v - если бы мы этого не сделали, v не был бы корнем. После того, как мы вставим v, нам нужно вставить элементы в упорядочение, которое приведет к восстановлению поддеревьев L и R. Трудная часть здесь заключается в том, что нам не нужно создавать все L до создания R или наоборот; мы могли бы вставить некоторые элементы из L, затем некоторые элементы из R, затем больше элементов из L, затем больше элементов из R и т.д.

К счастью, есть полезное замечание, которое мы можем сделать. Предположим, что S _L представляет собой последовательность элементов, которая, если она вставлена ​​в BST, образует BST L. Аналогично, пусть S _R - последовательность элементов, которая, если она вставлена ​​в BST образуют BST R. Если мы рассмотрим любое возможное чередование последовательностей S _L и S _R, мы получим последовательность элементов, которые, если они будут вставлены в BST, содержащий только v, будет создавать дерево

   v
  / \
 L   R

В качестве примера рассмотрим это дерево:

       4
     /   \
    2     6
   / \   / \
  1   3 5   7

Одна возможная последовательность, которая строит левое поддерево (удерживая 1, 2, 3), равно 2, 1, 3. Одна возможная последовательность, которая строит правое поддерево, равна 6, 5, 7. Любое возможное чередование этих последовательностей при вставке в BST, содержащий только корень node 4, закончит построение вышеуказанного BST. Например, любая из этих последовательностей будет работать:

 2, 1, 3, 6, 5, 7
 2, 6, 1, 5, 3, 7
 6, 5, 2, 1, 3, 7
 ...

Так как заданы любые последовательности S _L и S _R, которые создают L и R, мы можем чередовать их в любом порядке, мы можем записать хорошую формулу для числа последовательностей, которые будут строить дерево с v в качестве его корня, L в качестве его левого поддерева и R в качестве его правого поддерева:

# ways = (# чередования S _L и S _R) & times; (# возможно S _L s) & times; (# возможно S _R s)

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

Итак, как много перемежений? Если нам даны две последовательности длины m и n без дубликатов в них, мы можем придумать количество перемежений этих последовательностей со следующим наблюдением. Рассмотрим последовательность

L L L ... L R R R ... R
  m times     n times

Любая перестановка этой последовательности вернет ряд Ls и Rs, где число Ls равно числу элементов в последовательности длины m, а число Rs равно числу элементов в последовательности длины n. Мы можем интерпретировать эту последовательность как способ описания того, как создать чередование - в любое время, когда мы видим L, мы вставляем элемент из левой последовательности, и в любое время, когда мы видим R, мы вставляем элемент из правой последовательности. Например, рассмотрим последовательности 4, 1, 0, 3 и 2, 7. Тогда перестановка LLRLRL дает последовательность

 4, 1, 2, 0, 3, 7
 L  L  R  L  R  L

Если мы начнем с последовательности m L и n R, число различных перестановок вернется как

(m + n)!
-------- = (m + n) choose m
 m!  n!

Это выполняется потому, что существуют (m + n)! возможные способы переупорядочения Ls и Rs, если они все различны. Так как это не так, каждый заказ считается m! п! слишком много раз, потому что мы можем перечислить L неразличимо и R неразличимо. Еще один способ подумать об этом - рассмотреть набор индексов {1, 2, 3,..., m + n} в чередовании, затем выбрать m из них для заполнения элементами из первой последовательности, неявно заполняя остальные из них с элементами из правой последовательности.

Хорошо... теперь у нас есть способ определить количество способов чередования двух последовательностей длины m и n. Поэтому мы имеем следующее:

# ways = (# чередования S _L и S _R) & times; (# возможно S _L s) & times; (# возможно S _R s)

= ((m + n) выбрать n) & times; (# возможно S _L s) & times; (# возможно S _Rс)

Где m - количество элементов в левом поддереве, а n - количество элементов в правом поддереве. Ура!

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

function countInsertionOrderings(Tree t) {
    if t is null, return 1;
    otherwise:
       let m = numElementsIn(t.left);
       let n = numElementsIn(t.right);
       return choose(m + n, n) * 
              countInsertionOrderings(t.left) *
              countInsertionOrderings(t.right);
}

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

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

Ответ 2

Это интересный вопрос. Я реализовал эту идею в python, и эта рекурсия и запоминание имеют довольно хорошую производительность. "Seq" - это список уникальных целых чисел

def answer(seq):
    from math import factorial
    BStore = dict() # store binomsial coefficient
    Store = dict() # store the recusion step 
    def TreeGenerator(a,L): # for a given number a and a list L, this functions returns the left tree (a list) and the right tree (a list)
        LT = []
        RT = []
        for i in L:
            if i<a:
               LT.append(i)
            else:
               RT.append(i)
        solution = [LT,RT]
        return(solution)       
    def binomial_coefficient(n, k):
        d = n - k
        if d < 0:
           return(0)
        return(factorial(n) / factorial(k) / factorial(d))
    def binomial(n, k):
        if (n, k) in BStore:
           return(BStore[n, k])
        else:
           solution = binomial_coefficient(n, k)
           BStore[n, k] = solution
           return(solution)    
    def R(S): # recursion starts here
        if tuple(S) in Store:
           return(Store[tuple(S)])
        else:
           if len(S)<2:
              results = 1
           else:
              a = S[0]
              S = S[1:]
              Tree = TreeGenerator(a,S)
              R1 = R(Tree[0])
              R2 = R(Tree[1]) 
              results = binomial(len(R1)+len(R2), len(R2))*R1*R2             
        Store[tuple(S)] = results
        return(results)
     return(R(seq))