Tries

[00:00:00]
>> Let's keep going. So we just did pathfinding. And now we're going to do, how do you think you would pronounce that? It's tries. And I did not make that up, that's actually the correct way to pronounce that. So I still call this tries despite the fact that it's spelled trie but let me explain to you why it's called a trie.

[00:00:29]
It's actually from the word from retrieve, right? So, this is in the middle of this right? So how do you say retrieve like that? So it's trie in the sense of retrieve. However, the funny thing too in order to implant the trie you must use tries as in like these kind of tries.

[00:00:48]
So, I just have a immense amount of disdain for whatever person thought that was a good name for that particular data structure. But here we are, that's what it's called. So what is a trie, beyond being just a trie. It's a trie that's optimized for searching, by prefix.

[00:01:09]
So almost exclusively, as far as I know, this is useful for like typeahead, I don't know if you've ever heard of typeahead. But it's the idea if I start typing S, A, N it's gonna auto-complete to San Francisco, San Diego, San Jose right, it's gonna start trying to guess what I'm doing.

[00:01:26]
The best way to implement those sorts of typeaheads is using this data structure called trie. Okay, so a trie starts with a root node which is typically just an empty string, right. Basically represents nothing. Then you'll have notes coming off for the first letter that someone might type.

[00:01:48]
So let's take a look at this one. That's B, right? So you'd have like an empty string, root node, then someone would type B, right? And then people, the typeahead was start trying to guess what the person's asking for. So let's say that they were trying to get to Boston, right?

[00:02:06]
They would type b-o, and then off of this, o node, there'd be s, t, o, n for Boston. But there would also be b-o-i-s-e for Boise so that's kind of the idea here with tries is trying to guess what the user is trying to do, so that you can kind of like help them with whatever they're trying to do.

[00:02:30]
So each one of these write b-o, the b the s, the t, the o they enter their own individual nodes. In this particular case there's probably not another US city that starts with b-o-s-t-o right? So there's probably only one end off of the Boston search term here, but some of them as you might imagine, there's lots of American cities that start with b-o, right.

[00:02:54]
So this is gonna have like 15 different sorts of notes hanging off of it. So, in fact, some of them that that can be kind of difficult is there's American cities that are self contained and other ones right. So that like there's a city called Sandy and there's a city called Sandy Springs but these are both valid cities.

[00:03:16]
So you can have to provide for both of those. So this is y here this y node, right, let's say that b-o-s-t was a valid city this t would have a complete flag on it that says that b-o-s-t is actually a valid city. But it would also say I also have children too, by the ways because Boston is also a valid city Cool.

[00:03:41]
What else? So like, let's take San Francisco and San Diego, those have a space in them, right? So it's san<space>, you would just treat that space as if it was a normal character, right? There's no special consideration given to spaces. And yeah, that's really about the entire idea here is you're just going to make these tries.

[00:04:07]
This b-o right this could have infinite amount of children there could be a b-o-i a b-o-s, a b-o-n, a b-o-f, right, as many as you have cities to justify. So let's talk about how you would build one of these.