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

Question

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

 4 
    2  6 
1 3 5 

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

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

Любые мысли?

Answer 1

Высота дерева предсказуема 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 

Основная идея заключается в следующем: все полные BSTs разделяют одно свойство, о рекурсивном определении 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) поддерева, которые будут размещены на уровне heighest. Теперь мы можем легко удалить эти узлы из дерева, вычислить корень совершенного 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:

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

from wikipedia

Полного BSTs подкласс сбалансированного BSTs, с некоторыми дополнительными ограничениями, которые позволяют уникальное отображение полного 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. Индексы соответствующих узлов никогда не изменяются во всех методах-вызовах.

Answer 2

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

Answer 3

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

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 
}