Сортированный список для завершения представления массива 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 и сохраняете его в массиве.