Odniesienie: Zadano mi to pytanie @MS SDE interview, 3. runda. I to nie jest problem z pracą domową. Pomyślałem też i wspomniałem o moim podejściu poniżej.

Pytanie: Zmodyfikuj BST, aby był jak najbardziej zrównoważony. Nie trzeba wspominać, że powinieneś robić to jak najbardziej efektywnie.

Wskazówka: Przeprowadzający wywiad powiedział, że jest to logiczne pytanie, jeśli myślisz inaczej, otrzymasz odpowiedź. Nie było trudnego kodowania.
-> Powiedziawszy to, nie sądzę, żeby spodziewał się, że wskażę drzewa AVL / RB.

Moje rozwiązanie: Zaproponowałem, że zrobiłbym to samo, przechodząc przez drzewo, biorąc środkowy element jako root nowego drzewa (nazwijmy go nowym rootem). Następnie przejdź do lewej części środkowego elementu, weź jego środkowy element jako korzeń lewego poddrzewa nowego korzenia drzewa. Podobnie zrobić dla prawej części. Wykonanie tego rekurencyjnie da optymalny zrównoważony BST.

Dlaczego publikuję tutaj: Ale nie był usatysfakcjonowany odpowiedzią :( Czy jest więc sposób na zrobienie tego bez strategii barwienia wag / RB, czy po prostu wygłupiał się ze mną? Proszę wpisać swoje myśli eksperckie.

Duplikować? Nie! Wiem, że to jestpytanie ale rozwiązanie zaproponowane przez wnioskodawcę jest zbyt skomplikowane, a inne mówi o drzewach AVL.