Сортированный список для завершения представления массива BST

Мне интересно, существует ли отображение между отсортированным массивом (например, [1, 2, 3, 4, 5, 6]) и представлением, которое получается, когда кто-то строит полное двоичное дерево поиска из этого отсортированного массива, и выражает указанное двоичное дерево поиска в виде массива (например, [4, 2, 6, 1, 3, 5], см. рисунок ниже)?

     4
  2     6
1   3  5

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

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

Какие-нибудь мысли?

3 ответа

Решение

Высота дерева предсказуема roundUp(log2(nodes)), Мы также знаем, что правое поддерево никогда не бывает больше левого поддерева - |LS| >= |RS|, Более того, мы можем рассчитать количество отсутствующих узлов, чтобы сделать дерево идеальным: 2 ^ (height - 1) - arr.length, Это позволяет нам предсказать, как распределить узлы среди поддеревьев:

findRoot(int[] arr , int maxLeaves , int maxLevelL)
    //maxLeaves is the number of leaves on the maximum-level
    int l = min(maxLevelL / 2 , maxLeaves)
    return (arr.length - maxLeaves) / 2 + l

node buildTree(int[] arr , int maxLeaves , int maxLevelL)
    if maxLevelL == 0
        return null

    node result
    int rootidx = findRoot(arr , maxLeaves)

    result.val = arr[rootidx]

    result.left = buildTree(arr.subarray(0 , rootidx) , Math.min(maxLeaves , rootidx - 1) , maxLevelL / 2)
    result.right = buildTree(arr.subarray(rootidx + 1 , arr.length) , Math.max(0 , maxLeaves - rootidx - 1) , maxLevelL / 2)

    return node

Основная идея заключается в следующем: все полные BST имеют одно свойство в отношении рекурсивного определения BST: (LS , R , RS) OR null, где LS а также RS являются левым и правым поддеревьями, которые также определяются как BST. И то и другое LS а также RS завершены, и по крайней мере один из них должен быть идеальным. Мы можем легко предсказать, какой из двух идеален: на высшем уровне m узлы, но в массиве нам не хватает x узлы для построения идеального дерева. Таким образом:

if m - x == m / 2 then both are complete and the height of RS is height(LS) - 1
if m - x < m / 2 RS is perfect, LS only complete but not perfect
if m - x > m / 2 LS is perfect, RS only complete but not perfect
if m - x == 0 both LS and RS are perfect and of equal height

Мы можем найти корень дерева, используя следующее правило: Рассчитать количество узлов слева (l) и правильно (r) поддерево, которое будет размещено на самом высоком уровне. Теперь мы можем легко удалить эти узлы из дерева, вычислить корень идеального BST и позже неявно добавить левый и правый узлы обратно в дерево: root = (arr.length - (l + r)) / 2 + l

E.g.:
Input:   1  2  3  4  5 
Nodes on maxLevel: 2
maxLevelL: 4

l = 2
r = 0

root_idx = (arr.length - (l + r)) / 2 + l =
     = (5 - 2) / 2 + 2 = 
     = 3

Apply this algorithm recursively to define subtrees:
...

result:
                  4
                /   \
               2     5
             /   \
            1     3

ПРИМЕЧАНИЕ. Я не проверял этот код. Возможно, он все еще содержит несколько арифметических недостатков, которые необходимо исправить. Логика верна, хотя. Это должно просто представлять способ переназначения индексов из одного массива в другой. Реальная реализация может сильно отличаться от кода, который я предоставил.

После этого обсуждения во второй раз, вот определение полного BST:

В полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее.

из википедии

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

РЕДАКТИРОВАТЬ:
Приведенный выше алгоритм может быть изменен следующим образом для непосредственного построения массива:

  • корень дерева имеет индекс 0
  • левый потомок узла с индексом n имеет индекс (n + 1) * 2 - 1
  • правый потомок узла с индексом n имеет индекс (n + 1) * 2

Обычно эти операции доступа выполняются для массива на основе 1, но для удобства я изменил их для соответствия массиву на основе 0

Таким образом, мы можем переопределить buildTree напрямую создать массив:

node buildTree(int[] arr , int maxLeaves , int maxLevelL , 
          int[] result , int nodeidx)
    if maxLevelL == 0
        return

    int rootidx = findRoot(arr , maxLeaves)

    //insert value into correct position of result-array
    result[nodeidx] = arr[rootidx]

    //build left subtree
    buildTree(arr.subarray(0 , rootidx) , Math.min(maxLeaves , rootidx - 1) , maxLevelL / 2 , 
              result , (nodeidx + 1) * 2 - 1)

    //build right subtree
    buildTree(arr.subarray(rootidx + 1 , arr.length) , Math.max(0 , maxLeaves - rootidx - 1) , maxLevelL / 2 ,
              result , (nodeidx + 1) * 2)

Обратите внимание, что в отличие от arr мы никогда не используем подмассивы result, Индексы соответствующих узлов никогда не меняются при любых вызовах методов.

Это мой способ решить эту задачу, надеюсь вам понравится!)

def GenerateBBSTArray(a):
    a.sort()
    level = 0
    accum = []
    elements = []
    while len(a) // 2**level > 0:
        accum = [elem for elem in a[len(a) // 2**(level + 1)::(len(a) // 2**level) + 1]]
        elements.extend(accum)
        accum = []
        level += 1
    return elements

Вот что я придумал. Он не идеален в том смысле, что это не та функция, которую я имел в виду, но она экономит усилия по созданию дерева и последующему созданию массива из него.

find_idx(n) {
  if n == 1 { return 0; }

  h = ceil(lg(n+1)) // height of the tree
  f_h = floor(lg(n+1)) // height of the full portion (h or h-1)
  m_n = 2^h - 1 // # of nodes if tree were full
  f_n = 2^f_h -1 // # of nodes of full portion

  return floor(f_n / 2) + min(n - f_n, floor((m_n - f_n) / 2)
}

to_bst_array(array) {
   q = new empty queue
   res = resulting vector

   q.push(array)

   while !q.is_empty() {
     subarray = q.pop()
     idx = find_idx(subarray.len())

     res.push(subarray[idx])

     if subarray.len() > 1 {
       q.push(subarray[..idx]) // slice from 0 to idx
     }

     if subarray.len() > idx + 1 {
       q.push(subarray[idx + 1..]) // slice from idx+1 till end of subarray
     }
   }

   return res
}

Нет Прямое представление Между выражением Binary Tree Search (BST) и прямым массивом сортировки. Единственная взаимосвязь между отсортированным массивом - это когда вы выполняете обратный порядок в BST и сохраняете его в массиве.

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