Python erstellen einen binären Suchbaum mit der vorhandenen Funktion

Question

Ich übe die Erstellung eines ausgewogenen binären Suchbaums in Python. Ich habe bereits diese unten, irgendeine Idee, wie man eine balance_bst-Funktion erstellt, die eine Liste von eindeutigen Werten übergibt, die in aufsteigender Reihenfolge sortiert sind. Es gibt einen Verweis auf die Wurzel eines ausgewogenen binären Suchbaums zurück:

class LN: 
    def __init__(self,value,next=None): 
     self.value = value 
     self.next = next 

def list_to_ll(l): 
    if l == []: 
     return None 
    front = rear = LN(l[0]) 
    for v in l[1:]: 
     rear.next = LN(v) 
     rear = rear.next 
    return front 

def str_ll(ll): 
    answer = '' 
    while ll != None: 
     answer += str(ll.value)+'->' 
     ll = ll.next 
    return answer + 'None' 



# Tree Node class and helper functions (to set up problem) 

class TN: 
    def __init__(self,value,left=None,right=None): 
     self.value = value 
     self.left = left 
     self.right = right 

def height(atree): 
    if atree == None: 
     return -1 
    else: 
     return 1+ max(height(atree.left),height(atree.right)) 

def size(t): 
    if t == None: 
     return 0 
    else: 
     return 1 + size(t.left) + size(t.right) 

def is_balanced(t): 
    if t == None: 
     return True 
    else: 
     return abs(size(t.left)-size(t.right)) <= 1 and is_balanced(t.left) and is_balanced(t.right) 

def str_tree(atree,indent_char ='.',indent_delta=2): 
    def str_tree_1(indent,atree): 
     if atree == None: 
      return '' 
     else: 
      answer = '' 
      answer += str_tree_1(indent+indent_delta,atree.right) 
      answer += indent*indent_char+str(atree.value)+'\n' 
      answer += str_tree_1(indent+indent_delta,atree.left) 
      return answer 
    return str_tree_1(0,atree) 

Wie schreibt man den balance_bst?

def balance_bst(l): 

Hier ist, was ich getan habe:

def build_balanced_bst(l): 
    if l == None: 
     return None 
    else: 
     middle = len(l) // 2 
     return TN(l[middle], 
     build_balanced_bst(l[:middle]), 
     build_balanced_bst(l[middle + 1:])) 

Es gibt mir:

IndexError: list index out of range 

Wie kann ich das Problem beheben?

Answer 1

Ich werde es nicht für dich schreiben, da das nicht SO ist, aber hier ist die allgemeine Idee. Da die Liste bereits sortiert ist, sollte der Stamm das Element in der Mitte der Liste sein. Sein linkes Kind ist die Wurzel des ausgewogenen Baums, der aus den Elementen links von der Wurzel in der Liste besteht, und der rechte Teilbaum ist der Rest.