Zrozumienie budowy drzewa wyszukiwania binarnego

Question

Mam trudności z zrozumieniem, jak budowane są drzewa wyszukiwania binarnego. Czy wymagają one posortowania początkowych danych w celu znalezienia najlepszego root'a?

Answer 1

kształt, że wyszukiwanie binarne drzewo trwa zależy od dwóch rzeczy:

1. kolejności, w której elementy są wstawiane i
2. saldo operacji Co, jeśli w ogóle, drzewo czy podczas wkładania.

Jeśli masz czyste drzewo wyszukiwania binarnego bez żadnej logiki przywrócenia równowagi, kolejność włożenia elementów będzie miała duży wpływ na kształt drzewa. Na przykład, przyjmuj wartości 1, 2, 3, 4, 5, 6, 7. Jeśli wstawisz je w kolejności 4, 2, 6, 1, 3, 5, 7, otrzymasz to drzewo:

 4 
    / \ 
    2  6 
    /\ /\ 
    1 3 5 7 

powodem tego jest to, że możemy przejść do serii drzew:

 4 

    4 
/
    2 

    4 
/ \ 
    2  6 

    4 
/ \ 
    2  6 
/
1 

    4 
/ \ 
    2  6 
/\ 
1 3 

    4 
/ \ 
    2  6 
/\ /
1 3 5 

    4 
/ \ 
    2  6 
/\ /\ 
1 3 5 7 

z drugiej strony, jeśli wstawić wartości w kolejności 1, 2, 3, 4, 5, 6 , 7, otrzymujesz to drzewo:

1 
\ 
    2 
    \ 
    3 
    \ 
     4 
     \ 
     5 
     \ 
      6 
      \ 
      7 

Co ciekawe, wstawianie elementów do BST w posortowanej kolejności jest o ne z najgorsze rzeczy, które można zrobić dla drzewa, ponieważ sprawia, że ​​drzewo jest liniową strukturę. Jesteś lepiej zbieranie losowych permutacji elementów wstawić, lub (jeśli są wszystkie znane wcześniej) ich sortowania i stosując następujący algorytm rekurencyjny na sortowanej kolejności:

• Jeśli nie ma żadnych elementów, gotowe.
• W przeciwnym razie:
  • Wstaw medianę do BST.
  • Rekurencyjnie wstaw pierwszą połówkę elementów do BST.
  • Rekurencyjnie wstaw drugą połówkę elementów do BST.

Nadzieja to pomaga!