[áá£á¡áááá¡ ááááá á] DOUG LLOYD: áá¡á á áá, á©ááá á£ááá á£áá®ááááááááá áá á£á¤á á áá®ááá¡, á áá á¬ááááá áá áááá áááááªááááá á¡á¢á á£á¥á¢á£á ááá, áá áá, á áá á©ááá á¨ááááá«ááá á©áááá á¨ááááá, á¬áá¨áá, áá áááááá§á£á ááá áá£ááááá áá áá¡. á£á¤áááá. á¡á¬áá áá áá ááááá á áááááá. á©ááá áááááá, á áá áá§áá¡ ááá  ááááááááá¡ á áá á«ááááá, á«ááááá á¡á¬á áá¤áá. 

áááá¥áá¡ áááááááá áá¥, á áááá¡ááª á©ááá áá¡áá£áá ááá áááá? áá¡á, ááááá á¨ááá®áááá. áá¡á á áá, á©ááá áááá®áá á áááááááá á¡á®ááááá¡á®áá áááááªáááá á¡á¢á á£á¥á¢á£á ááá á áá ááá£áááááááá¡ á á£ááááá¡ á.á¬. á«áá ááááá á¦áá ááá£ááááá¡ á¬á§áááá, ááááá¥á¢áááá¡ ááá áááá£áá ááá­áá á áááááªááááá áááááá áá á¡á®áá ááá­áá á áááááªááááá áá¡á á áá, á©ááá, á¡áá ááá¤áá áááªááá¡ á¡á¢á á£á¥á¢á£á á. 

áá¡á ááá¡ááá, ááááááááá, ááá¡áá¦ááá áá áá¡ ááááááá¢á¡ ááááá¥á¡á áá ááá¡ááá ááááááá¡áááá¡ 0 áá ááá¡ááá 1 áá áá¡á á¨ááááá. áá áááá¨ááááááá áááááªááááá á áá áá á¡ááááá¡ áá ááááááá¡. áá¡á á áá, á á áááá®ááá ááá¡ááá 0? á á áááá®ááá ááá¡ááá 1 á¯ááááá 0 áá 1, á ááááááª áá¥áááá ááá¡áá¦ááááá. 

áá ááá hash áááááá áá¡ áá ááááá á ááááá áááá. áá ááá hash áááááá, á©ááá áááá¥áá¡ áá¡ hash á¤á£áá¥áªáá, á ááááááª á¬áá ááá¨ááá¡ hash áááááá. áá¡á á áá, ááá¡áá¦ááá áá áá¡ hash áááá áááááªááááá¡. áá á¦áá ááá£áááá, áááá¡ááá£áá áááá á©ááá ááá¡áá£áá áá ááá¯áá­ááá¡ áá ááááá hash áááááááá, áá¡ áá áá¡, á áá á£áááá¨áá áááá á¡ááá¨á áááááªááááá á áá á°áá¨ááá á áá hashcode. á£á¤áááá. á ááª á¨ááá®ááá áááá á ááááááá áá¡ áááááá, áá£ááªá? á ááª á¨ááá®ááá áááááá¡, á¡ááááª ááá¡áá¦ááá áá áá¡ ááá ááá¢áá ááá£áá áá§áá¡ á£áááááá£á á, áááá¡á®ááááááá hash áááááá, á¡ááááª á¨ááááá«áá ááá¡á á£ááááá up áá ááá áá á áªááá áááááªááááá á ááááá¡ááª ááááá hashcode. áá ááá¨áá á©ááá á£ááá ááá£áááááááá á áá áá áª á¡ááªáááá áá ááá¢á á¡áá¡á£á ááááá ááá¯áá­ááá¡ ááá¤áá¥á¡áá ááá, á áá áá áááááá. 

áá¡á á áá, áá®áá á©ááá á¨ááááá«ááá áááááªááá á©áááá áááááá á áá¥áááá á£áááááá£á á. áá á á, áá£ á©áááá á¦áá ááá£áááá á£áá áááá á áá¦ááª á áááá áª ááá á¢ááá á áááá áª á­áá¨ááá áá¢á áá áªá á£ á ááááááª áááá£ááááá, áá£ áá á áá£ áá á, á áá ááá¤áá áááªáá áá á¡ááááá¡ á¡á¢á á£á¥á¢á£á á? áááááá£á á á¨ááá«áááá áá§áá¡ á áááá áª ááá á¢ááá, á áááá áª áªáá¢á. á áááá£á áá áá¡, ááááá, byte á£á¤á á ááá¢áá, áááá á áªáá¢á. áááá áá á áá áááá á ááá¢áá á, áááá á á¨áááá®ááá¡ áá¥ááá 50-á®áá¡ááááá¡ á¢áá¥á¡á¢á, ááááááááá. 

áá¡á á áá, áááá, áá¡áááá¡á hash áááááááá, á ááááááª ááá ááááááá¡ ááááá¥á¢áá ááá áá á£áááá¨áá áááá á¡áá, áááá áááá áááááááá ááá¡ááááá, á¡á¢á á£á¥á¢á£á ááá, áá ááááááááá¡ áá ááá á©áá¬áá áá áááááªááááá á¡áááá¢áá áá¡á áá¡á, á áá á¡áááááá áááá¡á®ááááááá áá áá¤áá á á©ááá áááá®áá á¯áá á¯áá áááá. áá®áá á©ááá ááá§ááááá áááááªáááááá¡ á¡ááááá á á£áá áááááááªáá áá áááááªáááááá¡ á¡á¢á á£á¥á¢á£á áá¡. áá áá£ á©ááá á¨ááááá«ááá ááááªááá¡ á¡ááááá á á£áá, á¨ááá«áááá áá£ áá á ááááªááá¡ áááááªááááá ááááááá ááááááá, á©ááá ááááááááááááá ááªáá áá£ áá á, á áá áááááªááááá áá á¡ááááá¡ trie. 

áá áá£ á©ááá áá  á¨áá£á«ááá ááááªááá¡ á á£áá áá®áá áááá¡ ááá¨áááá¡, á áá ááá¡á á£áááá¡ á§áááá, áááááªááááá áá  áá á¡ááááá¡. áá¡áá áá áá¡áá, ááá¡áá¦ááááá áá¥ ááá ááá¢áá ááá£áá á£ááá áá§áá¡ á£áááááá£á á. áá¡á á áá, áááá¡á®ááááááá hash áááááá, á©ááá áá áá¡áá áá¡ á£ááá ááá£áááááááá collisions áá¥. áá áá á áá á áªááá áááááªááááá áá£á¡á¢áá ááááá á¡ááááá á á£áá áá£ áá¡ áááááªááááá ááááá¢á£á áá. 

áá£ á©ááá á©áááá á¯áá, ááá¨áá á©ááá ááá«ááááá ááááá. áá¡ áá áá¡ áá á áá ááááá á áªááá áááááªááááá, á£á¤áááá, á©ááá ááá«ááá ááá¨áááááá. áááá áá á¡á®áá á¨áááá®ááááá¨á, áá á áªááá áááááªááááá ááá ááá¢áá ááá£áá áá¥áá¡ á£áááááá£á á á¡áááá¥áááá ááááá ááá¨áááááá áá áááááªáááááá¡ á¡á¢á á£á¥á¢á£á áá¡. áá á©ááá ááááá ááá á¨ááá®áááá áááá£ááá£á á áá¡ áá®áááá áá áá á¬á£ááá. 

á©ááá á§ááááá¤áá á¡ áááááááááá áá áªáááááá¡ á¨áá¥ááá áá®ááá áááááªáááááá¡ á¡á¢á á£á¥á¢á£á áá¡, á á£ááááá¡ á¨ááááá ááá¡áá¦ááá á¦áá ááá£áááá á¬á§áááá. áá á¨áááá®ááááá¨á, á©ááá áá  ááááá ááá, áááááá§áááá¡ á áá¦ááª ááá á¢áááá, á áááá áª áááááá£á á. á©ááá á áááá£á áá á¨áá¡áááá®áá á¡áááááááá. áá á áá á¡áááááááá áááá ááá¡ áá§áá¡ á¡áá®ááá á£ááááá á¡áá¢áá¢á¨á. 

áá ááá¡áá¦ááá áá¥áááá á¬ááá¡ á áááá¡ááª, á ááááááª áááá á¡áá. á§áááá á¬ááá¡ á£ááááá á¡áá¢áá¢ááá¨á ááááá ááá, á áá ááá®á áªáá¤á á. áá¡á á áá, á©ááá ááá§ááááá áá ááá®á áªáá¤á ááá áááááááªáá ááá¨áááááá áá áááááªáááááá¡ á¡á¢á á£á¥á¢á£á áá¡. áá á©ááá ááááááá®ááá, ááááá áá áá®áá, áá£ á áááá  á©ááá áááááááááá, á áá áá®áááá áááá á. 

ááááá¡ ááá, á©ááá ááááááá®ááá á¡áá®ááá á£ááááá á¡áá¢áá¢áá¡, á ááááááª á¨ááá¡ááááááá á áá ááá¡áá¦ááá, áá ááá®á áªáá¤á á. á«áá ááááá áááá á£ááá trie á©ááá áááá¥áá¡ áªááá¢á ááá£á á ááá á¨á á£á¢áá¡. áá¡á á áá, áá¤áá¥á áá, á áá, á áááá áª á®á. áá áá¡ áá áá¡ áá¡áááá¡á ááá ááá¬áá á áá ááááªáá¤áªáá á®á. á¡ááá ááá, á áááá¡ááª á©ááá ááá¤áá¥á áá á®áááá á áááá£á  á¡ááá§áá áá¨á, ááá áá¥áá á¤áá¡áá, á ááááááª áá áá¡ ááááááá áá ááá§ááá ááááá áá ááá áá¥áá á¤áááááááá áá ááá áá¥áá á¤áááááá. áá á«áá áááááá áááá trie áá áá¡ áá£á¡á¢áá ááááá, ááá áá áááá¡á, á áá root á£á«á¦áááá á¡ááá¦ááª áªáá¨á. áá á¤áááááá ááááá¨á. 

áá¡á á áá, áá¡ á¡áá®áá¡ á áááá áª áá¦áááá¡ á®á áá á£áá áááá flipping áá¡ áááááá§áá á. áááá áá á¯áá  ááááá áá á¡ááááá¡ á¤áááááá¨á. áá áá áá¥áááá á©áááá ááá, áá¡ áá¥áááá á©áááá áááá¨áá ááá á«áá á á¤áááááá. áá á¨áááá®ááááá¨á, áá áááááááá, áá á¤áááááá ááá ááá§áá áá ááá áªáá¤á ááá, á áá ááááá®á áá á ááááá áááá á¬áá®áááá, á¡ááááª á©ááá ááá á. 

áá£ á©ááá áá®ááááá 0 ááá¨ááááá áá á¤áááááá, áá£ á©ááá áá®ááááá 1 ááá¨ááááá áá á¤áááááá, áá áá¡á áá áá¡á á¨ááááá. áá¡á, á áá¡ ááá¨áááá¡ áá¡? áá¡á, áá¡ ááá¨áááá¡, á áá á§áááá ááááááááááá á¬áá á¢ááá áá á§áááá ááááá«áá¡ á¨á£á áá á§áááá á¤áááááá¨á, áá á¡ááááá¡ 10 á¨áá¡áá«áá áááááááá¨á, á áá á©ááá á¨ááááá«ááá á¬áááááá. áá¡á á áá, áá á¡ááááá¡ 10 ááááááááá¡ á§áááá ááááááááááá áááá. 

áá¡ áá áá¡ á¡ááááª áááá á¨áááá«áááá áááá¦áá áªáá¢á ááá¨áááááá¡ áááááá¡ ááá áá áá¡ ááá¯áááá áá  áá¥áá¡ áááá á áááááªáááááá áááááá£á¢áá á£á áááªáááá ááááá ááá á. áááá áá áááá ááá ááááª á¡áááááá ááá¡áááªáá áá. áá áá£ áá¥ááá ááá¥áá á¨ááá¡á, á áá áááááá áá£á¨áááá áá áá¥ááá áááá áá­á ááá-in áá áá¥á¡ááá ááááá¢á ááá, áá¡ááá ááá ááááª á¡áááááá á¡áááá¢áá áá¡á áááááªáááá á¡á¢á á£á¥á¢á£á áááá¡ áá£á¨áááá. áá£ áááááá, á áá á©áááá ááááááá¢á¡ á¨ááááá trie, á§áááá á©ááá á£ááá ááááááááá áá¨ááááá á¡á¬áá á ááá á«áá á á¤ááááá. áá á á á§áááá ááááá¯á ááá¡á¬áá áá ááá á¨ááá«áááá áááááá§á£á áááááá¡. á©ááá ááááá ááá, á áá áááá¡ááá¦áá áá¡ áá®ááá áááááªáááááá¡ á¡á¢á á£á¥á¢á£á á áá®ááá ááááá«áá¡ ááá£á¬ááá trie. 

áá á¨ááááá á áá áááááªááááá á¡á¢á á£á¥á¢á£á á áá á¡ááááá¡ áá á áªááá. á©ááá ááááá ááá, á áá á¨áá¡áááá®áá á¡áá®ááá á£ááááá á¡áá¢áá¢á¨á. áá á©ááá ááááá ááá á¨áá¡áááá®áá ááá¡ááá ááááá¢áá ááá á¡á®áá ááááá«áááá¡ ááááá á¢áááá¡. áá¡á á áá, ááááá áá áá®áá, áá¡ áá áá¡, á áá áá ááááá á ááááªáá¤áªááá¡ á§áááááá á©ááá ááá á, á©ááá 10 á¨áá¡áá«áá áááááááá¨á á©ááá á¨ááááá«ááá á¬áááááá. áá£ á©ááá áá®ááááá 0 ááá¨ááááá áá á¤áááááá¨á. áá£ á©ááá áá®ááááá 1, áá ááá ááá¡, áá áá¡á á¨ááááá áá áá¡á á¨ááááá áá áá¡á á¨ááááá. áá£ ááá¢á§ááá, 9, ááá¨ááááá áá á¤áááááá¨á. áá¡á á áá, á§áááá ááááááááááá á¬áá á¢ááá, á©ááá á¨ááááá«ááá á¬áááááá 10 á¨áá¡áá«áá áááááááá¨á. áá¡á á áá, á§áááá ááááá«áá¡ á£ááá á¨áááªááááá¡ 10 ááááááááá¡ á¡á®áá ááááá«áááá¡, 10 á¡á®áá ááááá«áááá¡. 

áá áááááªááááá á©ááá á¨áááá®ááá¡ áá áá¡ áá®áááá á¡áá®ááá¬ááááá á£ááááá á¡áá¢áá¢á¨á. ááááá áááá¨áááá trie. ááááá á©áááá áá á ááááááá á©áááá¡ trie. áá¡á á áá, á«ááááá ááááá, áá¡ áá áá¡ á©áááá á«áá áá£áá ááááá«áá¡. áá¡ áá áá¡ ááááá áá¥áááá á áá¦ááª áá¥ááá áááá ááá¡ ááááááá£á áá ááªá®áááááá. áá áá¥ááá ááááá ááá ááááááá£á áá á¨áááá á©á£áááá ááááªáá áá ááááá«áá¡ á§áááááááá¡. 

áá¥ááá ááááá ááá ááááááá, root á£áá áá¡, áá áá¥ááá ááááá áá malloc áááá¡ trie ááááá«á. áá áá¥ááá áá áá¡áá áá¡ á¨ááá®áá root áá áá®áá. á§áááá á¯áá áá áá¡á£á á áááá¬á§áá¡ á¡ááááááááªáá á¡áá¨á£áááááá, áá¥ááá áááááááá£áá áá áá ááá©áááááááá á£áá áá¡ á¤áá¡áá, á áááá ááªáá trav, á ááááááª áá áá¡ ááááááááá áá ááááá§ááááá áááá  á©ááá¡ áááááááá áá¥ stacks áá á ááááá áá ááá£áá á¡áááá áá áá¡á á¨ááááá. 

áá¥ááá á¨ááá¥ááá ááááá áá áá ááá©áááááááá ááá£á¬ááá trav for ááá¡áááá¡. áá áá¥ááá áá§ááááá trav áááááááªáá ááá¨áááááá áááááªáááá á¡á¢á á£á¥á¢á£á áá¡. áá¡á á áá, áááá®áá, á áááá  á¨ááá«áááá áááááá§á£á áááááá¡. áá¡á á áá, áá®áá, á á ááá¯áááá ááááá«áá¡ á°áááá¡? áá¡ááá, á áááá áª á©áááá áááááªáááááá á¡á¢á á£á¥á¢á£á á áááááá ááªááá¨á áááááááá£ááá, á©ááá á¡áááááááá, á ááááááª áá á¨áááá®ááááá¨á áá áá¡ áªáá áááá. áá áá¤áá áá áá¥. 

áá ááá¡ááá 10 ááááááááá¡. áá áá®áá, á©ááá áá®áááá 1 ááááá«á¨á áá trie. áá¥ á¡á®áá áá áá¤áá á áá§á. áá¡á á áá, á§áááá 10 áá ááááá¢áá ááá áá¦áááá¨áá, á áá null. áá¡ áá áá¡ áá¡, á ááª á¬ááááá ááá£áááááá¡. 

ááááá á©áááá á¡áááááááá á°áá ááá ááá¡. ááááá á©áááá á£ááááá á¡áá¢áá¢áá¡ á°áá ááá ááá¡ áá trie, á ááááááª áááá á¡áá á¬ááá 1636. á©ááá áááááá, á áá áááááá§áááá ááá¡áá¦ááá, 1636, ááááá®á áá, á¡ááááª á©ááá ááá á áááá ááá¡ á¨áá¡áááá®áá á°áá ááá ááá¡ trie. áá®áá, á áááá  á¨ááá«áááá áááá¡ áááááááá? 

áá¡ á¨ááá«áááá á áá¦ááª áá¡áááá¡á. á©ááá áá¬á§ááá root. áá á©ááá áá 10 áááááááá¨á á©ááá á¨ááááá«ááá á¬áááááá. á«áá áá£áá áá¡ááá, á áááá áª ááááá¡áááá á á¡á®áá ááááá«áá¡ trie. áá á¡ááááá¡ 10 áááááááá¨á á©ááá á¨ááááá«ááá á¬áááááá áá¥áááá. 

á¡áá á©ááá ááááá á¡á£á á á¬áá¡ááá áá£ ááá¡áá¦ááá 1636? áá¥ ááááááááá áá á ááá áááá¢á. á£á¤áááá. á©ááá á¨ááááá«ááá áááá¨áááá ááá¡áá¦ááá ááá á¯áááááá ááá áªá®ááá áá áá¬á§ááá 6. áá á©ááá á¨ááááá«ááá áááá¨áááá ááá¡áá¦ááá ááá áªá®ááááá ááá á¯áááá áá áá¬á§ááá 1. 

áá¡, ááááá, á£á¤á á ááá¢á£ááªáá£á á, á áááá áª ááááááááá¡ á£ááá áááá¡ááááá¡, á áá á©ááá á£áá áááá ááá£á¢ááááááá ááá á¯áááá. áá¡á á áá, áá£ ááááá á©áááá á°áá ááá ááá¡ áá trie, áá, ááááá, ááááá, á áá áááá¬á§áá¡ ááá¬á§ááá£áá root, á¨ááá®ááááá á©ááá 10 ááá áááá¢á á©ááá¡ á¬áá, áá áááááªá®ááá, áá ááááá, á áá áááªáááá¡ 1 áááá¡. OK. 

áá®áá, 1 ááá áá áá¡ áááááááá£áá null. áá¡á á áá, áá£ áá¡á£á á áááá á«ááááá á¥ááááá á áá ááá á©áááá áá ááááááá¢áá¡ trie, áá á£ááá malloc áá®ááá ááááá«áá¡, 1 áá¦áááá¨áá, áá ááá¨áá áá ááá áá á¬áá¡ááá. 

áááá¢áá, áá á«áá áááááá ááá  á¡ááááá á¡ááááª áá ááááááá  áá áá á«áá á á®á áá trie áá áá á¡ááááá¡ 10 á¤áááááá¨á. áááá áá áááááá£áá á¤áááááá áá¥áá¡ ááá áááá¡ á¬áá. á£á¤áááá. áááá¡ áááá, á áá áá¥ á¡á®áá áá áá¤áá á áá á¡ááááá¡. áá áá áá¡ á£á¡áá¤á áá®á ááááá¡áá¡ááááá. áá¡ áááá¡ ááá¨áááá¡, á áá áá áá¤áá á á¥ááááá ááááá¡áááá á áá á¤áááááá¨á. áá£ ááááá, á áá áááá¬á§áá¡ á¨ááááá á áá¦ááª, ááááá ááááá¦áá ááá ááá­á. ááááá ááááá¦áá ááá ááá­á ááááá¬áá ááááá á 1. áá áá ááááá á¤áá®áá á¥ááááá á áá. áá ááááá áá¨ááááá á¡á®áá áááááá áá á¬áá¡ááá. 

áá á áá áá¡, á áá¡ááª áá ááááááá áá¥. áá¡á á áá 1 áá¦áá  ááá£áááááá¡ null. áá áááááªá®ááá, á áá áá¡ á£á¡áá¤á áá®á áááªáááá¡ áá¥ áá áá¡. áá ááááá£áá á¡á®áá ááááá«áá¡. áá á áááá¡ááª áá, á áá ááááá«áá¡, áá áááá¥áá¡ ááááá áá áá ááááá¬á§ááá¢ááááá. á¡áá ááá  áá ááááá áá á¬áááááá áá¥áááá? 

áá¡á, áá á£ááá á¬ááááá á¥ááááá 1. áá¡á á áá, áá®áá áá ááááá ááááá á¥ááááá 6. á£á¤áááá. áá¡áá áá áá¡áá, áá ááá¥áá¡ 10 ááááááá¡ á¨áááá«ááá ááá á©ááá¡. ááááá áá®áá áááªáááá¡ 6. áá¡á á áá, áá ááá ááááá ááá ááá­á ááááá¬áá 6. áá á¤áá®áá á¥ááááá. áá áá áá¨ááááá á¡á®áá ááááá«áá¡. áá áá áááá¦á¬áá áááá á ááááááááááá á¬áá á¢ááá. 

áá áá®áá, ááá¥áá¡ 10 áá á©ááááá á¡áá á¨áááá«ááá á¬áá¡ááá. áá áááááááá 1-ááá 6. áá¡á á áá, áá®áá áá, ááááá, ááááá á¬áá¡ááá 3. 3, áá¥ áá á¡áá á¨áááá«ááá á¬áá¡ááá. áá¡á á áá, áá á£ááá ááá ááááá ááá áá áááá¨áááá áááá¡ áá®áá á¡ááá áªáá¨á. áá ááá¨áá 3, á¡ááááª áá  ááááá á¬áá¡ááá? áá ááááá á¥ááááá 6. 

áá, ááááá áá áá®áá, áá áá¥áááá ááá ááááá ááá áááá¡ áááááááá. áá¡á á áá, áá®áá áá áááááá§ááááá á©ááá ááá¡áá¦ááá á©áááá á¨áá¥ááá ááááá«áááá¡ áá áááá¬á§áá¡ áá¨ááááá áá trie. áá áááá¬á§á á«áá áá£áá. áá á¬ááááá á¥ááááá 1636. áá áá®áá áá ááááá¨á áá¥ á áá ááááá«áá¡. áá áá¥ááá á¨áá«áááá áá®áááá, á áá áá¥áááá¡ ááá áááá. 

áá¡ ááááá¨áá£ááá á§áááááá. á¡á¬áá áá áá¥, á¡ááááª áá áááááááá£áá ááá . á©ááá ááá¡áá¦ááá ááááááá. áá áááá¬á£á á á§áááá áááááªáá á©ááá ááá¡áá¦ááá. áá¡á á áá, áá áá  á¨áááá«ááá á áááá. áá¡á á áá, áá áá¢áááá, á§áááá áá ááááááááá á£ááá ááááááááá ááááááá, OK. áá¡ áá áá¡ á¡áá®áá¡ ááá¡á¬ááá¡ áá«ááá¡ á¥ááááá ááááááá, áá£ áá¥ááá ááááááá¡á¬áááááá áááá¡, á áááá áª áá¡ áá ááááá á ááá á¡á®ááááá¡á®áá áááá¨áá ááá. áááááááá áá«ááá¡ á¥ááááá áá á¡áá®áá¡ spray á¤áá á¬áá á á°áá ááá ááá¡ ááááááá. áá¡ áá áá¡ áá¡, á¡áá®ááá áá. áááªá, á áá áá¡, á ááª áá ááááááá¡. áá£ á©ááá áá¬á§ááá root áá ááá¨ááááá 1 áá á¨ááááá 6 áá á¨ááááá 3 áá á¨ááááá 6, á¡áá ááá á á©ááá? ááá ááá áá£ áááááááá ááááá, á¥ááááá áá á©ááá áá®ááááá, á°áá ááá ááá¡, ááá¨áá á©ááá áááªáá, á áá á°áá ááá ááá¡ áááá á¡áá 1636 á¬ááá¡ á¡áá¤á£á«ááááá ááá á©ááá áá®áá áªáááááá¡ áá áááááªáááááá¡ á¡á¢á á£á¥á¢á£á áá¡. áá¡á á áá, áááááá ááá ááááá á. á©ááá ááááá ááá, á áá ááááá áá á ââá©áááá áááá. áá áááááá áá¡ áááá®ááá ááá áá®áááá áá áááááááá¡ áá á¯áá  ááá¢á. 

áá®áá, ááááá á©áááá á¡á®áá á£ááááá á¡áá¢áá¢á¨á. ááááá á©áááá Yale áá trie. ááááá¡ áááá á¡áá 1701. áá¡á á áá, á©ááá áá¬á§ááá root, á áááá áª á§áááááááá¡. áá á©ááá áááá¡áá®áá ááá¡áááá¡ ááá©áááááááá. á©ááá ááááá ááá, á áá áááááá§áááá, á áá áááááááááááá ááá¨áááááá. ááá áááá, á ááª á©ááá áááááá á¬áááááá¡ á¥ááááá 1 áááá¡. áá¡ áá áá¡ ááá áááá áªáá¤á á á©áááá ááá¡áá¦ááá. á¡áááááááá áá, ááá£á®áááááá áááá¡á, á áá á©ááá áá  áá¥áá¡ á áááá á¡ááá£á¨ááá¡ áá áá áá¡. 1 ááá á£ááá ááá¬áááááá¡. áá ááááááááá£áá áá¡ ááá á, á ááªá áá§á á©áá¡áá á°áá ááá ááá¡ at 1636. áá¡á á áá, á¨áááá«ááá á£á¡áá¤á áá®áá ááááááááá¡ down 1 áá áá®áááá áá¥. áá£ á¨ááá«áááá á¥ááááá 1. 

áá®áá, áá£ááªá, áá ááááá á¬áá¡ááá 7. áá ááá¬áááááá¡ ááá at 6. áá áááªá, á áá á¨áááá«ááá á£á¡áá¤á áá®áá áááá á«ááááá á¥ááááá 6 áááá¡. áááá áá áá á£ááá ááááá á«áááá 7 áááá¡. áá¡á á áá, á á á£ááá ááááááááá? áá¡á, áá¡ááá, á áááá áª ááá á, áá á£áá áááá á£ááá ááá ááááá ááá ááá­á, áááááááá ááááá, áá áááá¨áááá áá®ááá ááááá«áá¡ 7 áááá¡. á áááá áª áá¡. 

áá¡á á áá, áá®áá áá áááááááá 1 áá á¨ááááá 7. áá áá®áá á¨áááá©ááá, áá áá ááááá á á¡áá¥áá áááááá¡ áá áá®ááá subbranch. á£á¤áááá. á§ááááá¤áá á ááááá á©ááá 16 , áá áá  áááá¢áá áá¡ááá¡. áá áá  ááááááá¡ 16 áá áá¤áá á. áá ááááááá 17 ááá á¡ááááá. 

áá¡á á áá, áá®áá 17 á¬ááá¡, ááá¥áá¡ áá ááááá á Blaze áá®ááá ááá á¨á á£á¢ááá áá¥. á¨áááááá áªáá¤á á á©ááá ááá¡áá¦ááá áá áá¡ 0. áá áá¨ááá áá ááá  áááá¦áá¡ á¡áááá. áá á£áá áááá ááááá£áá áá¡ ááááá«á. áá¡á á áá áá áááªá, á áá áá  áá á¡ááááá¡ áááááááá á¬áá áá¥. áá¡á á áá, áá á£ááá áááá¦áá¡ áá á áááá¡. 

áá¡á á áá, áá malloc áá®ááá ááááá«áá¡ áá 0 áá¢áááá. áá ááá¨áá ááááá áá áá®áá, áá malloc áá®ááá ááááá«áá¡ áá áá á áááááá¢á¨á áá  áá á¡ááááá¡. áá¡áá áá áá¡áá, áá áááá¬á£á á á©ááá ááá¡áá¦ááá, 1701. áá¡á á áá, áá áááááá§á£á ááá á¥ááááá áá áá spray á¡áá¦ááááá Yale. áá¡ áá áá¡ áá¡, á¡áá®ááá áá ááááá«á¨á. 

áá¡á á áá, áá®áá áá£ áá áááá¡áá á£ááá áááááá®áá¡, áá£ Yale áá áá¡ áá trie, áá áá¬á§ááá root, áá á¥ááááá 1701, áá áááááá§á£á ááá á¥ááááá. áá áá£ áá ááá  áá®áááá Yale spray ááá®áá¢á£áá ááááá¢ááá ááááááá, ááá¨áá áá áááªá, Yale áá á¡ááááá¡ áá trie. ááááá ááááááááá ááááá áá áá. ááááá á©áááá Dartmouth áá trie, á ááááááª áááá á¡áá 1769 á¬ááá¡. 

áá¬á§ááá root áá áá®áá. á©ááá ááá áááá áªáá¤á á á©ááá ááá¡áá¦ááá áá áá¡ 1. ááááááá á¨áááá«ááá á¥ááááá, á áá ááá. á ááááááª á£ááá áá á¡ááááá¡. á¨áááááá áªáá¤á á á©ááá ááá¡áá¦ááá 7. ááááááá á¨áááá«ááá á¥ááááá, á áá ááá. áá¡ áá á¡ááááá¡, áá¡ááá. 

á©ááá áááááááá 6. áá¥, á¡ááááª áá áááááááá£áá ááá  á§áááááá áá¥ á áá á¨á£á ááááá«áá¡, 6 ááááááá ááá®á£á á£áá off. áá£ ááááá á¬áá¡ááá á¥ááááá á áá ááá, áá á£ááá áááá¨áááá áááá¡. áá¡á á áá, áá malloc áá®ááá ááááá«áá¡ áá 6-áá£áá¥á¢áááá áá á¡ááááá¡. á¨ááááá, ááááá áá áá®áá, áá á¡á áááá áá®ááá ááááááááá¡ áá¥. 

áá¡á á áá, áá malloc áá®ááá ááááá«áá¡ áá¡á, á áá á áá ááááá«áá¡ áááá¡ ááááá á 9- áá ááá¨áá áá®áá áá£ áá áááááááá ááá 1769, áá áá á¥ááááá. áá áá¤áá áá áááááááá£áá spray ááá®áá¢á£áá áá á¡ááááá¡. á¨áááá«ááá á¬áá á Dartmouth. áá áá á©áá¡áá£áá DARTMOUTH á¨ááááá trie. 

áá¡á á áá, á©áá¡áá á áá á¨ááááá trie. áá®áá á©ááá áááááá ááá«ááááá ááááááá. á áááá  á£ááá ááá«ááááá á áá trie? áá¡á, áá¡ á¡áááááá áááá á ááááá áááá. áá®áá á©ááá á£áá áááá áááááá§áááá áªáá¤á ááá, á áá ááá¡áá¦ááá áá£ á©ááá á¨ááááá«ááá áááááááªáá á«áá á á¡ááááª á©ááá áááááá, á áá á¬áááááá¡ trie. 

áá£ á©ááá ááá®ááá á©áá®á ááááá¡áááá  á¬áá á¢ááá¨á, ááá¨áá á©ááá áááªáá, á áá ááááááá¢á¡ áá  áá á¡ááááá¡ áááá, á áá áááááá á£ááá ááá¬áááááá¡. áá£ á©ááá, á ááá áá¡ á§áááá ááá áá ááááá¡, á§áááá á©ááá á£ááá ááááááááá áá áá¡ áááááá§á£á ááá á¥ááááá áá áááá®áá, áá£ áá¡ ááááááá¢á¡ á©ááá ááá«ááá. áá£ áá¡ áá áá¡, á¬áá ááá¢ááá. áá£ áá¡ áá¡á áá  áá áá¡, ááá . 

ááááá á«áááá á°áá ááá ááá¡ áá trie. á©ááá áá¬á§ááá root. áá ááááá áá áá®áá, á©ááá ááááá ááá á¨áá¥ááá ááá¡áááá¡ ááá©áááááááá ááááááááá á©áááá ááááá¯ááá á©ááááááá¡. á«áá á á©ááá áááªáá, á áá ááá ááá á ááá¨á, á©ááá á£ááá á¬áááááá, 1 á¨ááááá«ááá áááá¡ áááááááá? áááá®, á©ááá á¨ááááá«ááá. áá£ á£á¡áá¤á áá®áá áá á¡ááááá¡. á©ááá á¨ááááá«ááá á¬áááááá áá¥. 

áá®áá, áááááááá á ááá¨á, á©ááá á£ááá á¬áááááá 6. áá£ áá á 6 ááá áá á¡ááááá¡ áá¥? á°á, áá¡ áá¡áá. á©ááá á¨ááááá«ááá áááªáááá¡ 6 áááá¡. á©ááá ááá¡á á£ááááá ááá áá¥. 

ááá  ááá¨ááááá 3 ááá áá¥? áá¡á, á áááá áª áá ááááá, áááá®, áá á¡ááááá¡ á«ááááá. áá ááááá¦ááá 6 ááá áá¥? áááá®, á©ááá á¨ááááá«ááá. 

á©ááá áá  á¡áááááá á£ááá¡á£á®á áááá®áá ááááááá. áá á¡ááááá¡ ááááá áá áá ááááá¯á, á ááááááª áá®áá á©ááá á£ááá á¨ááá®áááá á¥ááááá áá áááá®áá, áá£ á áá á¡áááááááááá¨á áá£ á©ááá ááá«ááá á°áá ááá ááá¡, áá¡ áá áá¡, á áá á á á©ááá ááá¡ á¨ááááá, á ááª á©ááá áááááááááá¥áá ááá¡áá¦ááá? áááááááá¨á á©ááá ááááá§áááááá áá¥, ááááááááááá¨á á§áááááááá¡ ááá®á áªáá¤á á. áááá áá áá¥ááá á¨ááá«áááá ááááá§áááááá, ááááááááá, á¡ááááª áá¥ááá á¨áááá®ááá¡ ááá¥á¡ááááá á¡áá¢á§áá. 

áá¡á á áá, áááªáááá, á áááááááª 10 ááááááááá¡ á©ááá ááááááááááá áááá, ááááá 26. áá áá áááááá£áá á¬áá ááá áááááá. áá áá á¡ááááá¡ á¡áá¢á§áááá, á áááá ááªáá á¬áá, á ááááááª áá áá¡ subset á¡á£á áááááá¡, ááááááááá. áá¡á á áá, ááá¨ááááª áá, áá£ áá¥ááá áááá¦ááá ááááá¡ ááá¡áá¦ááá áá áá¥ááá áááááá§á£á ááá á¥ááááá, áá¥ááá áá  á®ááááá á á áá¥ááá áá«ááá. 

áá¡á, á áá áá¥ááá á§áááááááá¡ á£ááá áááááá ááááá ááá áá ááá¨áá áá£ áá§á á¬áá ááá¢áááá á¨áá£á«áááá traverse ááááá ááá, á¨áá®áááá á¥ááááá áá áááá¡ áá á-áá áá á¡áááááá ááááá¡á¢á£á ááá. áá¡ áá áá¡, á áá áá¡, á ááª áá ááá«áá? áá¡á, áá áááááá§á£á ááá á¥ááááá ááá¬á§áááá¡ á¨ááááá áááá áá áááá ááá¡ 1636. áá áááááá§á£á ááá á¥ááááá. áá áá®áááá á°áá ááá ááá¡. áá¡á á áá, áááá®, áá á¨áá«áá. á á ááá®áááá, áá£ áá¡, á ááª áá ááá«áá áá  áá áá¡ trie, áá£ááªá. á á ááá®áááá, áá£ ááá«áá Princeton, á ááááááª áááá á¡áá 1746 á¬ááá¡. áá¡á á áá, 1746 á®áááá á©ááá ááá¡áá¦ááá áááááááªáá ááá¨áááááá trie. áá¡á, áá áá¬á§ááá root. áá, ááá ááá á ááá¨á, ááááá, á áá ááááá¡ á¥ááááá 1 áááá¡. á¨áááá«ááá áááá¡ áááááááá? áááá®, áá áá  á¨áááá«ááá. 

á¨áááá«ááá á¥ááááá 7 ááá áá á¡ááááá¡? á°á, áá áá  á¨áááá«ááá. á áá áá á¡ááááá¡ á«ááááá. áááá áá á¨áááá«ááá á¥ááááá 4 ááá áá¥? áá¡ áááááá á¡áááá¡ áááá®ááá¡, á¨áá£á«ááá áá áááá á«ááááá á¥ááááá á áá ááá¢áá á áááááááá á áá áá ááááá¨áá£ááá á§áááááá? áá¥ áá áá¤áá áá. á£á¤áááá. 

áá  áá á¡ááááá¡ ááá, á¬áá á¥ááááá 4 áááá¡. áá£ Princeton áá§á áá trie, á áá 4 áá  áááá¬ááááá á©ááááááá¡ á£ááá. áá¡á á áá, áá áá¢áááá á©ááá á©áá®á¨á. á©ááá áá  á¨ááááá«ááá á áááá. áá¡á á áá, á¨ááá«áááá ááá¥ááá¡, á¡ááááááá, áá . áá ááá¡á¢áááá¡ áá  áá á¡ááááá¡ áá trie. 

áá¡á á áá, á áá¡ ááá¨áááá¡? á£á¤áááá. áá á¡ááááá¡ áááá á á®áááá áá¥. áá á¡ááááá¡ ááááááááá¡ ááááá áááááá. áá, á áááá áª á®ááááá áá®áááá áá áá¤ááááá, áá á¡ááááá¡ áááá á ááááá«áááá¡ á áá á áááááááª á¡áá®áá¡ á¡áá¤á ááá ááá á¨ááá. áááá áá á¨áááá©ááá, á§áááá áá áá¡, á©ááá áááááááá, á áá á¨ááááá¬ááá áá áá¡ áá£ áá á á áá¦ááª trie, á©ááá áá®áááá á£ááá áááááááááááá 4 ááááááá¡. 

á§áááá áá áá¡, á©ááá áááááááá, á áá á©áááá á ááá trie, á©ááá á£ááá áááá¦áá¡ 4 ááááááá¡, á¨áá¡áá«ááá, mallocing á áá¦ááªááá ááááá. áááá áá, á áááá áª áááá®áá, á áááá¡ááª á©ááá á©áá¡áá£áá DARTMOUTH á¨ááááá trie, áááá¯áá  áááá¡ á¨ááá«áááá á£ááá áááá£áááááááá á©ááááááá¡. áá¡á á áá, á©áááá trie áá¦ááá¡ á£á¤á á áááá áá áááá, á©ááá áááááááá áá£á¨áááá¡ á§áááá á¯áá áá á©áááá áá®ááá á áá áááá¢áá, á áá á©ááá á£ááá áá¨áááá áááá á á¨á£ááááá£á á á¤áááááááá ááááá. áá£ á©ááá áá®áááá áááá¡áá á£ááá á¨ááá®áááá 4 á áá, 4 áá áá¡ áá£ááááá. á©ááá ááááááááá á¡áá®áá¡ áá®ááááááá áá£ááááá áá á á©áá¡áá áá áá£ááááá áá á á¡áá«áááááá. áááá, á á áá¥áá á£ááá, áá¡ áá áá¡, á áá áá trie, á áááá áª áá¥ááá ááááá áááá®á áá, ááááá. áááááá£áá áá ááááá«áááá¡ ááááááá¡ áááá á á¡ááá áªáá¨á. 

áááá áá áá¡ tradeoff. áá£ áááááá, ááá ááááª á¡á¬á áá¤á á©áá¡áá, ááá ááááª á¡á¬á áá¤á á¬áá¨ááá¡, áá ááá ááááª á¡á¬á áá¤á á«áááá, á©ááá á£ááá áá¥áá¡ áááá á áááááªááááá á¡áá¤á ááá ááá á¨ááá. á©ááá á£ááá áááááááá¡á¬ááááá£ááá áááá á á¡ááá áªá áá ááá®á¡ááá áááá¡, á áá áááááªááááá á¡á¢á á£á¥á¢á£á á áá á¡ááááá. 

áá áá¡á, á áá tradeoff. áááá áá á áááá áª á©ááá¡, á©ááá á¨ááá«áááá áááááá¡ ááá. á©ááá á¨ááá«áááá áá  áá¦áááá©ááá, á áá á¬ááááá áá áááá áááááªáááá á¡á¢á á£á¥á¢á£á ááá á¡á¬á áá¤á á©áááá áá, á¬áá¨áá, áá á¡áá«áááááá. áá, á¨áá¡áá«ááá, áá¡ áá¥áááá á¨áá¡áááááá¡á áááááªááááá á¡á¢á á£á¥á¢á£á á ááááá§ááááá ááááá¡áááá á ááá¤áá áááªáá á©ááá ááªáááááá, á áá ááá¦áááá. áá Doug Lloyd, áá¡ áá áá¡ CS50.