Найдите количество перестановок данной последовательности целых чисел, которые приводят к тому же дереву двоичного поиска

Question

Найдите количество перестановок данной последовательности целых чисел, которые приводят к тому же дереву двоичного поиска

Мы в настоящее время не используем внешние ключи. И по большей части мы не сожалеем о нем.

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

Схематическое изображение. Настолько легче произвести схему базы данных, если существуют отношения внешнего ключа, правильно используемые.
поддержка Инструмента. Намного легче создать модели данных с помощью Visual Studio 2008 , который может использоваться для LINQ to SQL, если существуют надлежащие отношения внешнего ключа.

, Таким образом, я предполагаю, что моя точка - то, что мы нашли, что, если мы делаем большую ручную работу SQL (создают запрос, выполнение запросов, и тому подобное) внешние ключи не обязательно важны. Как только Вы начинаете входить в использование инструментов, тем не менее, они становятся намного более полезными.

9

algorithm binary-search-tree

задан Gaurang Tandon 8 February 2019 в 16:31

2 ответа

Другие вопросы по тегам:

algorithm binary-search-tree

Похожие вопросы:

score 12 · Answer 1

Your question is equivalent to the question of counting the number of topological orderings for the given BST.

For example, for the BST

the set of topological orderings can be counted by hand like this: 10 starts every ordering. The number of topological orderings for the subtree starting with 20 is two: (20, 15, 30) and (20, 30, 15). The subtree starting with 5 has only one ordering: (5, 7). These two sequence can be interleaved in an arbitrary manner, leading to 2 x 10 interleavings, thus producing twenty inputs which produce the same BST. The first 10 are enumerated below for the case (20, 15, 30):

 10 5 7 20 15 30
 10 5 20 7 15 30
 10 5 20 15 7 30
 10 5 20 15 30 7
 10 20 5 7 15 30
 10 20 5 15 7 30
 10 20 5 15 30 7
 10 20 15 5 7 30
 10 20 15 5 30 7
 10 20 15 30 5 7

The case (20, 30, 15) is analogous --- you can check that any one of the following inputs produces the same BST.

This examples also provides a recursive rule to calculate the number of the orderings. For a leaf, the number is 1. For a non-leaf node with one child, the number equals to the number of topological orderings for the child. For a non-leaf node with two children with subtree sizes |L| and |R|, both having l and r orderings, resp., the number equals to

  l x r x INT(|L|, |R|)

Where INT is the number of possible interleavings of |L| and |R| elements. This can be calculated easily by (|L| + |R|)! / (|L|! x |R|!). For the example above, we get the following recursive computation:

  Ord(15) = 1
  Ord(30) = 1
  Ord(20) = 1 x 1 x INT(1, 1) = 2  ; INT(1, 1) = 2! / 1 = 2
  Ord(7) = 1
  Ord(5) = 1
  Ord(10) = 1 x 2 x INT(2, 3) = 2 x 5! / (2! x 3!) = 2 x 120 / 12 = 2 x 10 = 20

This solves the problem.

Note: this solution assumes that all nodes in the BST have different keys.

score -1 · Answer 2

Вы можете сделать это в обратном порядке: учитывая BST, перечислить все массивы целых чисел, которые могут дать этот BST ...

Не могли бы вы (используя недетерминизм ...)

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

Недетерминизм даст вам все такие массивы. Тогда вы сможете их пересчитать.