Creare un albero di ricerca binaria completo dalla lista

Question

Sto provando a creare un algoritmo che crea un albero di ricerca binaria completo con un elenco di valori. Completa, in quanto tutti i livelli sono pieni tranne forse l'ultimo livello, che deve avere tutti gli elementi spostati il ​​più a sinistra possibile.

Ho implementato qualcosa (in Python) che creerà un BST equilibrato, in questo modo:

# TreeNode constructor takes (data, left, right, parent) 
def make_tree(arr, parent): 
    if not arr: 
     return None 

    length = len(arr) 
    if length == 1: 
     return TreeNode(arr[0], None, None, parent) 
    else: 
     mid = int(len(arr)/2) 
     mid_node = TreeNode(arr[mid], None, None, parent) 
     mid_node.left = make_tree(arr[0:mid], mid_node) 
     mid_node.right = make_tree(arr[mid+1:length], mid_node) 
     return mid_node 

Agisce in modo ricorsivo dividendo l'elenco per il punto medio, e facendo il punto medio di un nodo padre.

Tuttavia, ciò non crea uno completo BST. Data la lista [2,4,7,8,10], si creerà questo:

 7 

/ \ 

    4  10 

/ /

2  8 

Ma un BST completa sarebbe simile a questa:

 8 

/ \ 

    4  10 

/\ 

2 7 

Avete qualche suggerimento su come modificare il mio approccio per realizzare questo?

Answer 1

La costruzione di un BST completo è simile a quella di una BST bilanciata. Devi solo trovare il corretto medio. Ho usato la seguente funzione:

def perfect_tree_partition(n): 
    """find the point to partition n keys for a perfect binary tree""" 
    x = 1 

    # find a power of 2 <= n//2 
    # while x <= n//2: # this loop could probably be written more elegantly :) 
    #  x *= 2 
    x = 1 << (n.bit_length() - 1) # indeed you can 

    if x//2 - 1 <= (n-x): 
     return x - 1  # case 1 
    else: 
     return n - x//2 # case 2 == n - (x//2 - 1) - 1 

Ci sono due casi: o

• caso 1: sottoalbero sinistro della radice è perfetto e sottoalbero destro ha meno nodi o
• caso 2: il sottoalbero sinistro della radice ha più nodi e il sottoalbero destro è perfetto.

In entrambi i casi il numero di nodi nel sottoalbero perfetta è qualche 2**d - 1 così la radice è il nodo 2**d th contando da sinistra (caso 1) o destra (caso 2). Devi solo sottrarre 1 perché l'indicizzazione inizia da 0.

Answer 2

Se questa è solo una operazione singola, è possibile innanzitutto ordinare l'elenco e quindi costruire il BST. Ciò rende il problema banale.