[Гуляе музыка] Даг Lloyd: Так мы былі неўзабаве можа стаць і бліжэй, што Святы Грааль дадзеных структуры, які мы можам ўставіць у, выключыць і паглядзець у пастаяннае час. Права. Гэта свайго роду мэты. Мы хочам, каб быць у стане зрабіць рэчы вельмі, вельмі хутка. 

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

Такім чынам, для масіва, напрыклад, Ключ індэкс элемента масіва або Месцазнаходжанне на карце 0 або 1 масіў і гэтак далей. І значэнне дадзеных што існуе ў гэтым месцы. Так што захоўваецца ў масіве 0? Што захоўваецца ў масіве 1 па параўнанні з проста 0 і 1, якія будуць ключы. 

З хэш-табліцы, гэта накшталт той жа ідэі. З хэш-табліцы, у нас ёсць гэты хэш Функцыя, якая генеруе хэш-коды. Такім чынам, ключавым з'яўляецца хэш-код дадзеных. І значэнне, у прыватнасці, мы гаварылі пра счаплення у відэа на хэш-табліцы, з'яўляецца тое, што звязаны спіс дадзеных што хэшы для гэтага HashCode. Права. Што пра іншае падыходзе Гэты метад, аднак? Што аб метадзе, дзе ключ гарантавана быць унікальным, у адрозненне ад хэш-табліцы, дзе мы маглі б у канчатковым выніку з двума кавалкамі дадзеных з той жа хэш-код. І тады мы маем справу з што альбо прамацванне або больш пераважна ланцужкі, каб выправіць гэтую праблему. 

Так што цяпер мы можам гарантаваць што наш ключ будзе унікальным. А што, калі наша кошт быў проста нешта, як лёгка а сапраўдным і ілжывым, які распавядае нам пра тое, або не тое, што частка інфармацыі, існуе ў структуры? Лагічнае можа быць як просты, як няшмат. Рэальна гэта, верагодна, байт часцей, чым няшмат. Але гэта нашмат менш, чым захоўвання, можа быць, радок 50 сімвалаў, напрыклад. 

Так спробаў, падобна на хеши, якія спалучаюць масівы і звязаны спіс, спрабуе аб'яднаць масівы, структуры, паказальнікі і разам для захоўвання дадзеных у цікавы спосаб гэта даволі адрозніваецца ад усё, што мы бачылі да гэтага часу. Цяпер мы выкарыстоўваем дадзеныя ў якасці плана перамяшчацца гэтую структуру дадзеных. І калі мы можам прытрымлівацца дарожная карта, калі мы можам прытрымлівацца дадзеныя пачатку да канца, мы будзем ці ведаеце, што дадзеныя існуюць у сінтаксічнага дрэва. 

І калі мы не можам прытрымлівацца карце ад значэння, каб скончыць наогул, дадзеныя не могуць існаваць. Зноў жа, ключы тут гарантавана быць унікальным. І так у адрозненне ад хэш-табліцы, мы ніколі не будзем мець справу са сутыкненнямі тут. І няма двух кавалкаў дадзеных маюць сапраўды такі ж план калі гэта дадзеныя не ідэнтычныя. 

Калі мы ўстаўляем Яна, дык мы шукаем Іаана. Гэта два аднолькавых кавалка Дадзеныя, правільна, мы шукаем праз. Але ў адваротным выпадку, любая дзве часткі дадзеных з'яўляюцца гарантавана мець унікальныя дарожныя карты праз гэтую структуру дадзеных. І мы збіраемся, каб зірнуць на візуальны гэта ў імгненне. 

Мы зробім гэта, спрабуючы стварыць новую структуру дадзеных, адлюстраванне наступныя пары ключ-значэнне. У гэтым выпадку, мы не збіраемся выкарыстаць што-то жа проста, як Boolean. Мы на самай справе будзе захоўваць радок. І, што радок будзе будзе імя універсітэта. 

І ключ будзе год калі была заснавана, што універсітэт. Усе гады для універсітэтаў будуць чатыры лічбы. І таму мы будзем выкарыстоўваць гэтыя чатыры лічбы ў перамяшчацца па гэтай структуры дадзеных. І мы ўбачым, зноў, як мы робім, што ўсяго на секунду. 

У канцы шляху, мы ўбачым імя універсітэта, які адпавядае для гэтай клавішы, гэтыя чатыры лічбы. Асноўная ідэя ў сінтаксічнага дрэва гэта ў нас ёсць цэнтральны маршрут. Так што думаю пра яго, як дрэва. І гэта падобна на пісьме і ў канцэпцыю да дрэва. Звычайна, калі мы думаем пра дрэвы ў рэальным свеце, яны маюць корань, які знаходзіцца ў зямля, і яны растуць уверх і яны маюць філіялы і яны маюць лісця. І ў асноўным ідэя Trie сапраўды гэтак жа, акрамя таго, што корань якар дзесьці ў небе. А лісце ў ніжняй часткі. 

Так што гэта накшталт як браць дрэва і проста гартаць яе ўверх дном. Але ёсць яшчэ філіялы. І гэта будуць нашы шляхі, тыя будуць нашы сувязі ад кораня да лісця. У гэтым выпадку тыя, трасы, тыя галіны пазначаныя лічбамі, якія кажуць нам у які бок ісці, дзе мы знаходзімся. 

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

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

А ўнутры гэтых дадзеных Структура ёсць дзве часткі. Мы збіраемся захоўваць найменне універсітэта. І мы збіраемся захоўваць масіў паказальнікаў на іншыя вузлы таго ж тыпу. Так, зноў жа, гэта такога роду паняцці ўсюды мы, мы на 10 можна месцы, якія мы можам пайсці. Калі мы бачым 0, мы ідзем па гэтай галіны. Калі мы бачым, што 1, гэтая галіна, і гэтак далей, і гэтак далей, і гэтак далей. Калі мы кажам, 9, спускаемся гэтую галінку. Такім чынам, у кожнай кропцы пераходу, мы можам пайсці 10 магчымых месцаў. Такім чынам, кожны вузел павінен утрымліваць 10 паказальнікаў на іншыя вузлы, да 10 іншых вузлоў. 

І дадзеныя мы захоўвання з'яўляецца толькі назва ВНУ. Такім чынам, давайце будаваць сінтаксічнага дрэва. Давайце ўставіць пару элементаў у нашу сінтаксічнага дрэва. Такім чынам, на самым версе, гэта наш каранёвай вузел. Гэта, верагодна, будзе нешта Вы збіраецеся глабальна аб'явіць. І вы збіраецеся падтрымліваць глабальна паказальнік на гэты вузел заўсёды. 

Вы збіраецеся сказаць, корань роўны, і вы збіраецца Таноса сабе Trie вузел. І вы ніколі не збіраецеся закрануць корань зноў. Кожны раз, калі вы хочаце, каб пачаць навігацыю па, ўсталяваць іншы паказальнік роўна пні, напрыклад, Trav, які з'яўляецца прыкладам я выкарыстоўваць у многіх з маіх відэа тут, на стэкаў і чэргаў і спісы спасылак і гэтак далей. 

Вы можаце ўсталяваць іншы паказальнік называецца трава для абыходу. І вы карыстаецеся для навігацыі TRAV праз структуры дадзеных. Такім чынам, давайце паглядзім, як гэта можа выглядаць. Так што цяпер, што робіць вузел выглядае? Ну, як нашых дадзеных Структура дэкларацыі паказана, у нас ёсць радок, якая У гэтым выпадку пусты. Там нічога няма. 

І масіў з 10 паказальнікаў. І зараз, мы толькі ёсць 1 вузел у гэтым сінтаксічнага дрэва. Там няма нічога ў ім. Такім чынам, усе 10 з тых, паказальнікі паказваюць на нуль. Гэта тое, што чырвоны азначае. 

Давайце ўставіць радок у Гарвардскі. Давайце ўставіць універсітэт Гарвардскі ў гэтым сінтаксічнага дрэва, якія была заснавана ў 1636 у год. Мы хочам выкарыстоўваць ключ, 1636, каб сказаць нам, дзе мы збіраецеся захоўваць у Гарвард ў сінтаксічнага дрэва. Цяпер, як мы маглі б гэта зрабіць? 

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

Куды мы, верагодна, хочаце каб пайсці, калі ключ 1636? Там сапраўды два варыянты. Права. Мы можам пабудаваць ключ з справа налева і пачаць з 6. Ці мы маглі б пабудаваць ключ з злева направа і пачаць з 1. 

Гэта, верагодна, больш інтуітыўнае, як чалавечай істоты каб зразумець, мы толькі налева направа. І таму, калі я хачу, каб ўставіць Гарвардскі ў гэтым сінтаксічнага дрэва, Я, верагодна, хочаце, каб пачаць ад пачынаючы з каранёвага, гледзячы на ​​мае 10 варыянтаў перада мной, і сказаў Я хачу, каб ісці па шляху 1. ДОБРА. 

Цяпер, 1 шлях у цяперашні час нуль. Так што, калі я хачу, каб працягнуць гэты шлях уніз ўставіць гэты элемент у сінтаксічнага дрэва, Я павінен Таноса новы вузел, ёсць 1 пазначыць там, і тады я добра ісці. 

Так што я ў асноўным знаходжуся ў кропка, дзе я стаю у корані дрэва або Trie і ёсць 10 філіялаў. Але кожная галіна мае Вароты перад ім. Права. Таму што няма нічога іншага, ёсць. Няма бяспечны праход. Гэта азначае, што няма нічога ўніз любы з гэтых галін. Калі я хачу, каб пачаць будаўніцтва то, я хачу, каб выдаліць вароты. Я хачу, каб выдаліць вароты перад нумарам 1. І я хачу, каб спусціцца, што. І я хачу, каб пабудаваць іншае месца для мяне, каб пайсці. 

І вось што я зрабіў тут. Так што 1 больш не паказвае на нуль. Я сказаў, што гэта бяспечна спусціцца тут і цяпер. Я пабудаваў іншы вузел. І калі я дабіраюся да гэтага вузла, я ёсць іншае рашэнне, каб зрабіць. Дзе я буду ісці далей? 

Ну, я пайшоў ужо ўніз 1. Так што цяпер я, верагодна, хочаце, каб спусціцца 6. Права. Зноў жа, у мяне ёсць 10 месцаў я магу выбраць. Дык няхай цяпер спусцімся нумар 6. Так што я ачысціць вароты перад нумарам 6. І я іду туды. І я пабудаваць яшчэ адзін вузел. І я дасягнуў іншую кропку пераходу. 

Зноў жа, у мяне ёсць 10 варыянтаў для таго, дзе я магу пайсці. Я пераехаў ад 1 да 6. Так што цяпер я, напэўна, хочаце, каб перайсці да 3. 3, няма нідзе я магу пайсці. Так што я, каб расчысціць шлях і пабудаваць сабе новую прастору. А потым ад 3, дзе я хачу пайсці? Я хачу, каб спусціцца 6. 

І, зноў жа, я павінен быў расчысціць шлях, каб зрабіць гэта. Так што цяпер я выкарыстаў свой ключ, каб ўставіць стварыць вузлы і пачаць будаваць гэтую сінтаксічнага дрэва. Я пачаў на корані. Я пайшоў уніз 1636. І зараз я на дне ёсць на гэтым вузле. І вы маглі б убачыць яго на экране. 

Гэта выдзелены жоўтым колерам. Вось дзе я ў цяперашні час знаходжуся. Мой ключ робіцца. Я вычарпаў кожную пазіцыю ў маёй ключа. Так што я не магу ісці далей. Так у гэтай кропцы, усё, што я сапраўды трэба зрабіць, гэта сказаць, добра. Гэта накшталт як глядзіць у зямлю, калі вы прадугледжваюць самі, як такога роду шляху з рознымі злучэннямі. Сартаваць гледзячы і накшталт афарбоўка распыленнем Гарвард на зямлі. Гэтае імя гэтага. Ведайце, што гэта тое, што ў гэтым месцы. Калі мы стартуем з кораня і ідзем ўніз 1, а затым 6, а затым 3, а затым 6, дзе мы? Ну, калі мы паглядзім ўніз і мы бачым, Гарвард, затым мы ведаем, што Гарвард быў заснавана ў 1636 годзе на аснове, як мы рэалізацыі гэтай структуры дадзеных. Так што, спадзяюся, быў просты. Мы збіраемся зрабіць яшчэ два ўстаўкі. І, спадзяюся, гэта дапаможа ў каб гэта было зроблена ў два разы больш. 

Цяпер, давайце ўставіць іншы універсітэт. Давайце ўставіць Йель ў гэтым сінтаксічнага дрэва. Ельскі была заснавана ў 1701 годзе. Такім чынам, мы пачнем на корань, як мы заўсёды робім. І мы павінны ўсталяваць паказальнік абыходу. Мы збіраемся выкарыстоўваць гэта, каб рухацца праз. Першае, што мы хочам, каб зрабіць, гэта пайсці па шляху 1. Гэта першая лічба нашага ключа. На шчасце, аднак, мы не павінны рабіць любую працу на гэты раз. 1-шлях ужо быў ачышчаны. Я ачысьціў яго раней, калі я ўстаўляў у Гарвард ў 1636 годзе. Так што я магу смела рухацца ўніз 1 і толькі туды. Калі можа рухацца ўніз 1. 

Цяпер, аднак, я хачу, каб перайсці да 7. Я расчысціў шлях у 6. Я ведаю, што магу спакойна перайсці ўніз па 6 шлях. Але мне трэба, каб перайсці на 7 шляху. Так што мне трэба рабіць? Ну, як і раней, я проста трэба каб ачысціць вароты, выйсці з Дарэчы, і пабудаваць новы вузел з 7 шляху. Гэтак жа, як гэта. 

Так што цяпер я пераехаў 1, а затым 7. А цяпер звярніце ўвагу, я накшталт з гэтай новай падгаліны. Права. Усё астатняе ад 16 , Я не хвалюе. Я не раблю нічога 16. Я раблю 17 рэчаў. 

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

Так што я Таноса новы вузел і маюць кропку 0 там. А потым яшчэ раз, я Таноса Новы вузел і маюць адну кропку там. Зноў жа, я вычарпаў свой ключ, 1701. Так я гляджу ўніз, і я развеяць фарбу Йель. Гэтае імя гэтага вузла. 

І вось зараз, калі я калі-небудзь спатрэбіцца, каб убачыць, калі Ельскім універсітэце у гэтым сінтаксічнага дрэва, я пачынаю ў корані, Я спускаюся 1701, і глядзець уніз. І калі я бачу Yale спрэй пафарбаваны на зямлю, то Я ведаю, Ельскі існуе ў гэтым сінтаксічнага дрэва. Давайце зробім яшчэ адзін. Давайце ўставіць Дартмут ў гэта Trie, якая была заснавана ў 1769 годзе. 

Пачатак у корані зноў. Мая першая лічба майго ключа 1. Я магу з упэўненасцю рухацца па гэтым шляху. Гэта ўжо існуе. Наступная лічба майго ключа 7. Я магу з упэўненасцю рухацца па гэтым шляху. Яна існуе, як добра. 

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

Так што я Таноса новы вузел, так што з што node-- шлях Колькасць 9-- і то цяпер калі я падарожнічаю 1769, і я з нецярпеннем ўніз. Там няма нічога пра сябе спрэй пафарбаваны там. Я магу напісаць Дартмут. І я ўставіў Дартмут ў сінтаксічнага дрэва. 

Дык вось ўстаўкі рэчы ў сінтаксічнага дрэва. Цяпер мы хочам, каб шукаць рэчы. Як мы шукаем рэчы ў сінтаксічнага дрэва? Ну, гэта ў значнай ступені тая ж ідэя. Цяпер мы проста выкарыстоўваць лічбы ключа каб убачыць, калі мы можам перамяшчацца ад кораня дзе мы хочам ісці ў сінтаксічнага дрэва. 

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

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

Цяпер, наступнае месца мы павінны пайсці 6. Ці існуе шлях 6 адсюль? Так, гэта так. Мы можам спусціцца 6 шлях. І мы ў канчатковым выніку тут. 

Ці можам мы пайсці ўніз 3 шляху адсюль? Ну, як высвятляецца, ды, таксама існуе. І мы можам атрымаць на шляху ад 6 тут? Так, мы можам. 

Мы не зусім адказаў пытанне пакуль. Там па-ранейшаму яшчэ адзін крок, які ў цяперашні час мы павінны глядзець уніз і ўбачыць, калі гэта actually-- калі мы шукаем Гарвардзе, з'яўляецца тое, што што мы знаходзім пасля вычарпання ключ? У прыкладзе мы выкарыстоўваем тут, гады заўсёды чатыры лічбы. Але вы маглі б выкарыстоўваць прыклад, у якім Вы захоўваеце слоўнік слоў. 

І так, замест таго, 10 паказальнікаў для майго месцазнаходжання, вы, магчыма, 26. Адзін для кожнай літары алфавіту. І ёсць некаторыя словы, як кажан, які з'яўляецца падмноствам партыі, напрыклад. І таму нават калі вы атрымаеце ў канец ключа і вы паглядзіце ўніз, Вы не маглі б убачыць, што Вы шукаеце. 

Такім чынам, вы заўсёды павінны прайсці ўвесь шлях, а затым калі б вы былі ў стане паспяхова прайсці ўвесь шлях, глядзець ўніз і зрабіць адну канчатковае пацверджанне. Гэта тое, што я шукаю? Ну, я гляджу ўніз пасля запуску у верхняй і збіраецца 1636. Я гляджу ўніз. Я бачу ў Гарвард. Так што, так, мне гэта ўдалося. Што рабіць, калі тое, што я шукаю не ў сінтаксічнага дрэва, хоць. Што рабіць, калі я шукаю Прынстане, якая была заснавана ў 1746 годзе. І так становіцца 1746 мой ключ для навігацыі па сінтаксічнага дрэва. Ну, я пачынаю ў корані. І ў першую чаргу я хачу каб спускаецца шлях 1. Ці магу я гэта зрабіць? Так, я магу. 

Ці магу я перайсці ўніз па 7 шляху адтуль? Так, я магу. Гэта таксама існуе. Але я магу пайсці па шляху 4 з тут? Гэта як задаць пытанне, можа Я зыходжу ўніз, што скверык што я вылучыў жоўтым? Там нічога няма. Права. 

Там няма спосабу наперад па шляху 4. Калі Прынстан быў у гэтым сінтаксічнага дрэва, што 4 быў бы ачышчаны для нас ужо. І таму на дадзеным этапе мы зайшлі ў тупік. Мы не можам ісці далей. І такім чынам, мы можам сказаць канчаткова, няма. Прынстан не існуе ў гэтым сінтаксічнага дрэва. 

Такім чынам, што ж ўсё гэта значыць? Права. Там вельмі шмат тут адбываецца. Там гэта паказальнікі паўсюль. І, як вы можаце бачыць проста з дыяграмы, ёсць шмат вузлоў, якія з'яўляюцца свайго роду палёт вакол. Але звярніце ўвагу, кожны раз, калі мы хацелі праверыць нешта было ў сінтаксічнага дрэва, у нас быў толькі зрабіць 4 хадоў. 

Кожны раз, калі мы хацелі ўставіць што-то ў сінтаксічнага дрэва, мы павінны зрабіць 4 перамяшчаецца, магчыма, mallocing некаторыя рэчы па шляху. Але, як мы бачылі, калі мы ўставілі Дартмут ў сінтаксічнага дрэва, Часам некаторыя з шляху ужо можа быць ачышчана для нас. І так як наш Trie становіцца ўсё больш і больш, у нас ёсць менш працы кожны раз, ўставіць новыя рэчы таму што мы ўжо пабудавана шмат прамежкавы філіялы па шляху. Калі мы толькі калі-небудзь павінны глядзець на 4 рэчы, 4 гэта проста канстанта. Мы сапраўды выгляд набліжаецца пастаянная ўстаўкі раз і пастаяннае пошук час. Кампраміс, вядома, у тым, што гэта Trie, як вы, верагодна, можа сказаць, велізарны. Кожны з гэтых вузлоў займае шмат месца. 

Але гэта кампраміс. Калі мы хочам сапраўды хутка устаўка, выдаленне вельмі хутка, і сапраўды хуткі пошук, мы павінны ёсць шмат дадзеных, якія лётаюць вакол. Мы павінны ўсталяваць у бок шмат месца і памяці для гэтай структуры дадзеных існаваць. 

І так гэта кампраміс. Але, падобна, мы магчыма, знайшлі яго. Мы маглі б знайсці, што Святы Грааль структур дадзеных з хуткай ўстаўкі, выдаленне і пошук. І, можа быць, гэта будзе адпаведная структура дадзеных выкарыстоўваць для якой-небудзь інфармацыі мы спрабуем захаваць. Я Дуг Лойд, гэта CS50.