[Powered by Google Translate] Bir kompüter bütün ailə üzvləri necə təmsil edəcək?
Biz sadəcə, bir siyahısını istifadə edə bilər
lakin aydın iyerarxiya burada var.
>> Gəlin biz sizin böyük-nənəsi, Alice ilə başlayan etdiyiniz deyirlər.
O, 2 oğulları, Bob var
və babası, Charlie.
Charlie, 3 övladı var
Sizin əmisi Dave, sizin xalası, Həvva və atası Fred.
Siz Fred yalnız uşaq var.
>> Niyə bu şəkildə ailə üzvləri təşkil edərdi
sadə siyahısı təmsil daha yaxşı olacaq?
Bir səbəbi bu iyerarxik struktur,
adlandırıb 'ağac, bir sadə siyahısı daha çox məlumat var.
Biz hər kəs arasında ailesel əlaqələr bilirik
yalnız ağac araşdıraraq.
Həmçinin, sürətləndirmək bilər
göz-up vaxt böyük, ağac data sıralanır olunur.
>> Biz burada istifadə edə bilməz, amma, biz tezliklə bu nümunə görəcəksiniz.
Hər bir şəxs ağac bir node ilə təmsil olunur.
Bölmələri uşaq qovşaqlarının ola bilər
habelə valideyn node kimi.
Bu, texniki şərtlər var
ailələrin başqa şeylər üçün ağac istifadə edərək hətta.
Alice in node, 2 uşaq və valideynləri var
Charlie nin node 3 uşaq və 1 valideyn isə.
>> A yarpaq node uşaqların olmayan biri
ağac kənarda kənarında.
Ağacın topmost node, kök node,
heç bir valideyn var.
>> A ikili ağac, ağac xüsusi bir növü
hər node, ən azı, 2 övladı var.
Burada C. ikili ağac bir node və struct edir
Hər node ilə bağlı bəzi məlumatlar var
digər qovşaqlarının və 2 göstəricilər.
>> Bizim ailə ağac,
bağlı data hər bir şəxsin adı oldu.
Bir şey ola bilər, baxmayaraq Burada, bir int edir.
O çıxır ki,
ikili ağac, bir ailə üçün yaxşı təmsil olmaz
insanlar tez-tez çox 2 övladı var-ci ildən.
>> A ikili axtarış ağac
binar ağac xüsusi, sifarişli növü
bizə tez dəyərlər baxmaq üçün imkan verir.
Siz qeyd edə bilər
bir ağacın kökü aşağıda hər node
digər ağac kökü, bir 'subtree. "adlanır
Burada ağac kökü, 6
və onun uşaq, 2, subtree köküdür.
>> Ikili axtarış ağac
bir node bütün dəyərlər sağ subtree var
node dəyəri daha böyükdür. Burada: 6.
Yaxşı, bir node sol subtree dəyərlər
node dəyəri çox azdır.
Biz cüt dəyərlər idarə etmək lazımdır,
biz bir boş bərabərsizlik ya bu dəyişə bilərsiniz
eyni dəyərlər sol və ya sağ ya düşə bilər, yəni
kimi uzun biz ərzində bu barədə ardıcıl var.
Bu ağac ikili axtarış ağac
bu qaydalarına əməl edir.
>> Bu C structs daxil bütün qovşaqlarının çevrilmişdir əgər görünür necə.
Qeyd edək ki, bir uşaq itkin əgər,
İmleci null edir.
Necə 7 ağac olub olmadığını görmek üçün kontrol olsun?
Biz kök-da başlanır.
Bu ağac əgər yeddi 6 böyükdür, belə ki, bu, doğru olmalıdır.
Sonra o, 8-dən az, belə ki, onu tərk etmək lazımdır.
Burada 7 tapmışdır.
İndi biz 5-kontrol edəcəyik.
Beş 6 azdır, belə ki, sol olmalıdır.
Beş, 2 daha böyük
belə ki, doğru olmalıdır
və bu da 4-dən böyük, belə ki, sağ yenidən olmalıdır.
Lakin, heç bir uşaq burada var.
Bu göstərici null edir.
Bu 5 bizim ağac deyil deməkdir.
>> Biz aşağıdakı kodu ilə ikili ağac axtarış edə bilərsiniz:
Hər node-hazırda, biz gördük kontrol edin
biz axtarır dəyəri.
Biz bu tapmasanız olmalıdır, əgər biz müəyyən
sol və ya sağ və ki subtree yoxlayın.
Bu loop ağac aşağı davam edəcək
sol və ya sağ ya heç bir uşaq node var qədər.
>> 5 ağac olmadığını unutmayın.
Biz bu daxil edə bilərəm?
Prosesi axtarış benzer.
Biz, 6 ildən başlayaraq ağac aşağı təkrarlamaq
2-sol
4 hüququ
və sağ yenidən, lakin 4 bu tərəfində heç bir uşaq var.
Bu, 5 yeni mövqe olacaq
və heç bir uşaq ilə başlayacaq.
>> Necə sürətli bir ikili axtarış ağac əməliyyatları var?
Bigohnotation bir üst bound təmin etməyə çalışır unutmayın.
Ən pis halda,
bizim ağac sadəcə bir bağlı siyahı ola bilər
ki, durub, silinməsi, və axtarış məna
ağac ilə qovşaqlarının sayı mütənasib vaxt bilər.
Bu O (n) edir.
>> Məsələn, aşağıdakı cari ikili axtarış ağac.
Lakin, biz 9 tapmaq üçün cəhd əgər,
hər node axır var.
Bu bağlı siyahı daha yaxşıdır.
İdeal halda biz hər node istəyirəm
bizim ikili axtarış ağac 2 övladı var.
Bu yolla, durub, silinməsi və axtarış
, ən pis halda, O (Giriş n) vaxt olardı.
Əvvəl ağac, daha balanslı ola bilər
bunu bəyənir.
İndi, heç bir dəyəri axtarır 3 addımlar, ən azı edir.
Bu ağac, balanslaşdırılmış edir
ki, mənası bir minimal dərinliyi
qovşaqlarının sayı nisbətən.
>> Balanslaşdırılmış ikili axtarış ağac bir dəyər Axtarıram
bir sıralanır array haqqında ikili axtarış kimi.
Əslində, biz maddələr daxil və ya silmək üçün ehtiyac yoxdur, əgər
onlar tam eyni şəkildə davranmaq.
Lakin, bir ağac strukturu yaxşı
user insertions ve silme üçün
>> My name Bannus Van der Kloot edir.
Bu CS50 edir.