ik heb alle dingen die ik heb geleerd doorgenomen en ontdekte dat deze website, en dat is zeggen dat het ergste geval van zoeken in Binary Tree O (n) complexiteit heeft. Tot nu toe heb ik geweten dat de binaire zoekboom een gesorteerde boom is die we kunnen doorzoeken met binaire zoekactie die waarschijnlijk O(log n)-log base 2 heeft.
Kan iemand het uitleggen?
Antwoord 1, autoriteit 100%
In het ergste geval zou een binaire boom met N-elementen een gelinkte lijst zijn.
Er zouden dus Nniveaus zijn en een zoekopdracht zou Nverplaatsingen vergen.
~ Root ~
____
| 42 |
|____|
/ \
____/ \
| 13 | X
|____|
/ \
____/ \
| 11 | X
|____|
/ \
/ \
... X
Daarom is het in het ergste geval O(N).
En daarom moeten we de bomen in evenwicht brengen om O(log N)zoeken te bereiken.
Antwoord 2, autoriteit 11%
O(log n) is alleen geldig als btree gebalanceerd is.
In het geval dat uw invoegingen zich allemaal aan dezelfde kant van de boom bevinden, moet u om iets te vinden alle items doorlopen, dan O(n)