Czy istnieje metoda na zbudowanie zrównoważonego drzewa wyszukiwania binarnego?Budowanie zrównoważonego drzewa wyszukiwania binarnego
Przykład:
1 2 3 4 5 6 7 8 9
5
/\
3 etc
/\
2 4
/
1
myślę istnieje metoda, aby to zrobić, bez korzystania z bardziej złożonych samobalansujący drzew. W przeciwnym razie mogę zrobić to na własną rękę, ale ktoś prawdopodobnie zrobił to już :)
Dzięki za odpowiedzi! Jest to ostateczny kod Python:
def _buildTree(self, keys):
if not keys:
return None
middle = len(keys) // 2
return Node(
key=keys[middle],
left=self._buildTree(keys[:middle]),
right=self._buildTree(keys[middle + 1:])
)
Median nie jest właściwą terminologią. Po pierwsze, mediana może nie istnieć w oryginalnych danych. Na przykład mediana 3 i 4 wynosi 3,5. Zobacz http://en.wikipedia.org/wiki/Median –
Masz rację. Najwyraźniej (ze strony wikipedia, do której się odwołujesz) słowo to jest medoidem. Dokonałem edycji. –