[Powered by Google Translate] Jak byste reprezentovat všechny své rodinné příslušníky v počítači?
Mohli bychom jednoduše použít seznam,
ale je tu jasná hierarchie zde.
>> Řekněme, že jsme začali s velký-babička, Alice.
Má 2 syny, Bob
a tvůj dědeček, Charlie.
Charlie má 3 děti,
tvůj strýc, Dave, tvoje teta, Eve, a tvůj otec, Fred.
Jste Fredova jediné dítě.
>> Proč by organizování své rodinné příslušníky tímto způsobem
být lepší než jednoduchého seznamu reprezentaci?
Jedním z důvodů je to, že tato hierarchická struktura,
nazýván "strom," obsahuje více informací než jednoduchý seznam.
Známe rodinné vztahy mezi všemi
jen tím, že zkoumá strom.
Také lze urychlit
look-up čas ohromně, pokud strom data seřazena.
>> Nemůžeme využít, že zde, ale uvidíme příklad tak brzy.
Každý člověk je reprezentován uzlu stromu.
Uzly mohou mít podřízené uzly
stejně jako nadřazeného uzlu.
Jedná se o technické termíny,
i při použití stromy na věci, kromě rodiny.
Alicin uzel má 2 děti a žádné rodiče,
zatímco Charlie uzel má 3 děti a 1 rodič.
>> Koncový uzel je ten, který nemá žádné děti
na vnějším okraji stromu.
Nejvyšší uzel stromu, kořenový uzel,
nemá rodiče.
>> Binární strom je specifický druh stromu,
ve kterém každý uzel má nanejvýš 2 děti.
Zde je struct z uzlu binárního stromu C.
Každý uzel má nějaké údaje s ním spojené
a 2 ukazatele na další uzly.
>> V našem rodokmenu,
přidružené data byla každé jméno osoby.
Zde je to int, i když by to mohlo být cokoliv.
Jak to dopadá,
binární strom by nebylo dobré reprezentace pro rodinu,
protože lidé mají často více než 2 děti.
>> Binární vyhledávací strom
je zvláštní, objednané typ binárního stromu
, který nám umožňuje podívat se na hodnoty rychle.
Možná jste si všimli,
že každý uzel pod kořen stromu
je kořen jiného stromu, tzv. "podstromu."
Zde je kořen stromu je 6,
a její dítě, 2, je kořen podstromu.
>> V binární vyhledávací strom
všechny hodnoty uzlu je pravého podstromu
jsou větší než uzlu hodnoty. Tady: 6.
No, hodnoty v uzlu je levého podstromu
méně než uzlu hodnoty.
Pokud potřebujeme zvládnout duplicitní hodnoty,
můžeme změnit buď z těch, na volné nerovnosti,
což znamená, stejné hodnoty mohou spadat buď na levé nebo pravé,
tak dlouho, jak jsme důslední o tom celé.
Tento strom je binární vyhledávací strom
protože to vyplývá těchto pravidel.
>> To je, jak by to vypadalo, kdyby jsme se obrátili všechny uzly do structs C.
Všimněte si, že pokud dítě chybí,
ukazatel je null.
Jak jsme zkontrolovat, zda 7 je ve stromu?
Začneme u kořene.
Sedm je větší než 6, takže v případě, že je to ve stromu, musí být na pravé straně.
Pak, to je méně než 8, takže musí být vlevo.
Zde jsme zjistili, 7.
Nyní, budeme kontrolovat 5.
Pět je nižší než 6, takže musí být na levé straně.
Pět je větší než 2,
tak to musí být pravda,
a je také větší než 4, takže musí být zase v pořádku.
Je zde však žádné dítě zde.
Ukazatel je null.
To znamená, že 5 není v našem stromu.
>> Můžeme hledat binární strom s následujícím kódem:
Na každém uzlu, můžeme zkontrolovat, zda jsme našli
hodnota, kterou hledáte.
Pokud nenajdeme, jsme zjistit, zda by měl být
vlevo nebo vpravo a zkontrolujte, zda podstromu.
Tato smyčka bude pokračovat na strom
dokud není podřízený uzel buď doleva nebo doprava.
>> Pamatujte si, že 5 není ve stromu.
Jak jsme vložte ji?
Proces vypadá podobně jako vyhledávání.
Jsme iterovat dolů stromem od 6,
ponecháno na 2,
právo na 4,
a znovu doprava, ale 4 nemá dítě na této straně.
To bude nová pozice pro 5,
a začne s žádnými dětmi.
>> Jak rychle se operace binární vyhledávací strom?
Pamatujte si, že Bigohnotation se snaží poskytnout horní mez.
V nejhorším případě,
náš strom by mohl být jednoduše propojený seznam
což znamená, že vkládání, mazání a hledání
může trvat úměrný počtu uzlů ve stromu.
To je O (n).
>> Například, je následující platné binární vyhledávací strom.
Nicméně, pokud se snažíme najít 9,
musíme přejít každý uzel.
Není to lepší než propojeného seznamu.
V ideálním případě bychom chtěli každý uzel
našeho binárního vyhledávacího stromu mít 2 děti.
Tímto způsobem, vložení, mazání a vyhledávání
by se v nejhorším případě O (log n) času.
Strom z doby před mohly být vyrovnanější,
takhle.
Nyní, hledá nějaké hodnoty trvá nanejvýš 3 kroky.
Tento strom je vyvážený,
to znamená, že je má minimální hloubku
vzhledem k počtu uzlů.
>> Hledáte pro hodnotu ve vyváženém stromu binární hledání
je podobný binární vyhledávání na tříděném poli.
Ve skutečnosti, pokud nebudeme muset vložit nebo odstranit položky,
se chovají úplně stejně.
Nicméně, stromová struktura je lepší
manipulačních vložení a vymazání
>> Mé jméno je Bannus Van der Kloot.
To je CS50.