Wo fange ich mit dem binären Suchbaum an?

Question

Nach meinem Verständnis, wenn Sie eine binäre Suche abschließen, beginnen Sie mit dem mittleren Wert und vervollständigen einen Divide and Conquer-Algorithmus, bis Sie den richtigen Wert gefunden haben.

Wenn ich jedoch binäre Suchbäume betrachte, habe ich verstanden, dass dies in der gleichen Weise abgeschlossen wird, wobei der Anfangsknoten der mittlere Wert ist. Allerdings habe ich Beispiele für unsortierte Listen gesehen, wobei der erste Knoten der erste Wert ist im Array.

Welche Methode ist richtig?

Dank

Answer 1

Normalerweise beginnen Sie mit dem mittleren Knoten, dann die linke und rechte Hälften untersuchen.

Divide and Conquer-Algorithmen nähern sich dem Problem rekursiv, indem sie das ursprüngliche Problem in Teilprobleme kleinerer Größe aufteilen. Das Problem wird reduziert, bis es klein genug ist, um auf einfache Weise gelöst zu werden.

Bei dem binären Suchbaum übernimmt der Algorithmus den mittleren Knoten und löst rekursiv die rechten und linken Teilprobleme.

BinarySearch(Array arr, value) 
    return BinarySearchAux(arr, value, 0, arr.length) 

BinarySearch(Array arr, value, start, end) 
    if start >= end 
     return value == arr[start] 
    mid = floor((end - start)/2) 
    if value == arr[mid] 
     return true 
    return 
     BinarySearchAux(arr, value, start, mid-1) || 
     BinarySearchAux(arr, value, mid+1, end)