[Powered by Google Translate] Як бы вы ўяўляеце ўсіх членаў вашай сям'і ў кампутары? Мы маглі б проста выкарыстоўваць спіс, але ёсць выразная іерархія тут. 

Скажам, мы пачынаем з вашай прабабулі, Alice. Яна мае 2 сыноў, Боба і вашы дзядулі, Чарлі. Чарлі мае 3 дзяцей, Ваш дзядзька, Дэйв, твая цётка, Ева, і ваш бацька, Фрэд. Вы адзінае дзіця ў сям'і Фрэда. 

Чаму арганізацыю членаў вашай сям'і, такім чынам, быць лепш, чым простае прадстаўленне спісу? Адной з прычын з'яўляецца тое, што гэтая іерархічная структура, называюць «дрэвам», утрымлівае больш інфармацыі, чым просты спіс. Мы ведаем, што сямейныя адносіны паміж усімі толькі шляхам вывучэння дрэва. Акрамя таго, гэта можа паскорыць даведачнай час надзвычай, калі дрэва сартавання дадзеных. 

Мы не можам скарыстацца тым, што тут, але мы бачым прыклад гэтаму ў бліжэйшы час. Кожны чалавек уяўляе сабой вузел на дрэве. Вузлы могуць мець даччыныя вузлы а таксама бацькоўскага вузла. Гэтыя тэхнічныя тэрміны, нават пры выкарыстанні дрэў для рэчаў, акрамя сям'і. Вузлу Алісы мае 2 дзяцей, і няма бацькоў, у той час як вузел Чарлі мае 3 дзяцей і 1 бацька. 

Ліставым вузлом з'яўляецца той, які не мае дзяцей па вонкавым краі дрэва. Самы верхні вузел дрэва, каранёвай вузел, не мае бацькі. 

Бінарнае дрэва з'яўляецца спецыфічны тып дрэва, , У якой кожны вузел мае, самае большае, 2 дзяцей. Вось структура вузла ў бінарным дрэве ў C. Кожны вузел мае некаторыя звязаныя з ім дадзеныя і 2 паказальнікі на іншыя вузлы. 

У наш генеалагічнае дрэва, звязаныя з ім дадзеныя клікалі кожнага чалавека. Вось яна Int, хоць гэта можа быць што заўгодна. Як высветлілася, бінарнае дрэва не было б добрае ўяўленне для сям'і, так як людзі часта маюць больш за 2 дзяцей. 

Бінарнае дрэва пошуку гэта асаблівы, спарадкаваны тып бінарнага дрэва , Што дазваляе нам глядзець на значэннях хутка. Вы, магчыма, заўважылі, што кожны вузел пад корань дрэва корань іншага дрэва, званага "поддерево". Тут, корань дрэва 6, і яе дзіцяці, 2, з'яўляецца коранем поддерева. 

У бінарным дрэве пошуку ўсе значэння вузла правага поддерева больш, чым значэнне вузла. Тут: 6. Ну, значэнні у левым поддереве вузла менш, чым значэнне вузла. Калі трэба апрацоўваць паўтараюцца значэння, мы можам змяніць любы з тых, свабодныя няроўнасць, то ёсць аднолькавыя значэння можа ўпасці альбо на левы ці правы, тых часоў, як мы паслядоўныя пра гэта ўсім. Гэта дрэва бінарнае дрэва пошуку таму што ён варта гэтых правілах. 

Вось як гэта будзе выглядаць, калі мы павярнулі ўсіх вузлоў у структурах C. Звярніце ўвагу, што калі дзіця адсутнічае, паказальнік з'яўляецца нулявым. Як мы правяраем, калі 7 у дрэве? Мы пачынаем у корані. Сем больш за 6, так што калі гэта ў дрэва, яно павінна быць з правага боку. Тады, гэта менш, чым 8, таму ён павінен быць злева. Тут мы знайшлі 7. Цяпер мы праверым на 5. Пяць менш, чым 6, таму ён павінен быць злева. Пяць больш за 2, таму ён павінен быць правільным, і гэта таксама больш за 4, таму ён павінен быць яшчэ раз направа. Тым не менш, няма ні аднаго дзіцяці тут. Паказальнік з'яўляецца нулявым. Гэта азначае, што 5 не ў нашых дрэў. 

Мы можам шукаць двайковага дрэва з дапамогай наступнага кода: На кожным вузле, мы правяраем, калі мы знайшлі Значэнне, якое мы шукаем. Калі мы не знойдзем яго, мы вызначыць, калі яна павінна быць на левы ці правы і пераканацца, што поддерево. Гэты цыкл будзе працягвацца ўніз па дрэве пакуль не будзе даччыны вузел на левым ці правым. 

Памятаеце, што 5 не быў у дрэва. Як мы можам ўставіць яго? Гэты працэс падобны на пошук. Мы ітэрацыю па дрэве, пачынаючы з 6, злева 2, Права 4, і яшчэ раз направа, а 4 не мае дзіцем на гэтым баку. Гэта будзе новая пасада на 5, і ён пачне без дзяцей. 

Як хутка аперацый на бінарным дрэве пошуку? Памятаеце, што Bigohnotation імкнецца забяспечыць верхняй мяжы. У горшым выпадку, наша дрэва можа быць проста звязаны спіс Гэта азначае, што ўстаўкі, выдалення і пошуку можа заняць час, прапарцыйнае ліку вузлоў у дрэве. Гэта O (N). 

Напрыклад, наступнае з'яўляецца сапраўдным бінарнае дрэва пошуку. Аднак, калі мы спрабуем знайсці 9, мы павінны прайсці кожным вузле. Гэта не лепш, чым звязаны спіс. У ідэале, мы хацелі б, кожны вузел нашы бінарнае дрэва пошуку, каб мець 2 дзяцей. Такім чынам, устаўка, выдаленне і пошук бы, на худы канец, O (часопіс N) часу. Дрэва, перш чым магла б быць больш збалансаванай, як гэта. Цяпер, гледзячы любое значэнне мае, самае большае, 3 кроку. Гэта дрэва з'яўляецца збалансаваным, значэнне, якое мае мінімальную глыбіню у параўнанні з лікам вузлоў. 

Шукае значэнне ў бінарнае дрэва падобна на двайковы пошук у адсартаваным масіве. На самай справе, калі нам не трэба ўстаўляць або выдаляць элементы, яны паводзяць сябе сапраўды гэтак жа. Тым не менш, структура дрэва лепш для апрацоўкі уставак і выдаленняў 

Мяне клічуць Bannus Ван-дэр-Kloot. Гэта CS50.