[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.