Tavallinen BST voi degeneroitua linkitetyksi listaksi (O(n) operaatiot), jos avaimet saapuvat lajitellussa järjestyksessä. Itse tasapainottavat BST:t — kuten AVL ja punamusta puut — kiertävät automaattisesti solmuja lisäysten/poistojen jälkeen pitääkseen korkeuden ~log n, takaa O(log n) operaatiot.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL-puu | Punamusta puu | |
|---|---|---|
| Tasapainontiukkuus | tiukka (korkeustasapainotettu) | löyhempi |
| Haut | nopeampi (lyhyempi) | hieman hitaampi |
| Lisäys/poisto | enemmän kierroksia | vähemmän kierroksia |
| Paras | lukuintensiiville kuormille | kirjoitusintensiiville kuormille |
| Operaatio | Aika |
|---|---|
| haku | O(log n) |
| lisäys | O(log n) |
| poisto | O(log n) |
Molemmat säilyttävät tasapainon kierroksilla — paikalliset O(1) uudelleenjärjestelyt, jotka säilyttävät BST:n järjestyksen ja vähentävät korkeutta.
Tasapainotettavat puut tukevat järjestettyjä karttoja ja joukkoja vakiokirjastoissa (esim. Java TreeMap, C++ std::map käyttävät punamusta puita), jotka tarjoavat järjestetyn iteroinnin sekä taatut logaritmiset operaatiot.
Ne ovat vastaus silloin, kun tarvitset BST:n järjestystä ja kovaa suorituskykytakuuta vastustavia syötteitä vastaan.
Kirjasto IT-haastattelukysymyksiä yksityiskohtaisine vastauksineen — Juniorista Senioriin.
Lahjoita