now we find a note that has E, and we didn't update our pointer into the key

character, because we didn't find a match.

So, we're still looking at the E, and now, now we can match that E, so we go

down the middle link. Now we're looking at the A in the search

key, and that's less than L, so we go to the left.

now we're still looking at the A in the search key, and that's a match and it's

the last character in key, so, we return, the value associated with the last

character in the key. So, it's the same basic algorithm, that

we used for trie's except, we just have a different way to decide whether we match

the character. We explicitly store characters in nodes.

We follow middle link on a match, and update the pointer in our key character.

Otherwise, we, we follow the left or right link, because we know that the key

is going to be found in the left or right sub-tree.

And each node has exactly three links. So here's a example of search in a TST,

again this is the example I just talked about in a dynamic form, form.

So, if S is the first character in the key, matches the S in the first node of

tree, so we take the middle link, and move on to the second character in the

key which is e. Compare that against h, it's not a match

in fact it's less, so we go left. So, now we're still looking at e and c,

and it's a match with the character in the node that we're currently processing.

So, we take the middle, and now we move to the next character in the key which is

a. And now we take a compared to l, and a is

less, so we go left, we're still looking at the a, didn't updated it, 'cuz it's

not a match, and now it is a match. and it's the last character in the key,

so we look at the value, and that's the value we return.

what about unsuccessful search? well, let's see how that works.

So, for shelter, it starts with an S, so we take the middle link, second, and move

to the second character. Second character's an h, and that's a

match. So, we take the middle link, and move to

the next character. Third character's an e and third

character, and that, that's also a match. So again, we take the middle link, and

move to the next character. the fourth character's an l, that's also

a match. So, again, we take the middle link, and

move to the next character. Now the next character is a t, which is

not a match, so we want to move to the right but moving to the right takes us to

a null link. So that means that shelter is not in the

TST and, and so we return null. Again, in every, in every step what we do

is completely well-defined. and any search for a key that in the TST,

it's going to return it's associated value.

Any search for any other key, is either going to, go out on a null link, or end

on a node that involves a mismatch. so, with that basic idea, let's take a

more detailed look in the demo, of how the tree gets constructed.

and following through this demo, will give you a pretty good feeling for how

these trees are constructed. So, we're going to associate the value 0

with a string, SHE. so, again every time we move to a new

letter, we have to create a new node, until we get to the end of the key.

And at which case, we put the, associated the value with the node that contains the

last character in the key. so, that's the starting point.

key is a sequence of characters down the middle links that [COUGH] goes to from

the root to some node. And the value is in the node that

corresponds to the last character. so, how do we put a new one in this tree

so the in this Ternary search trie. Our first character is S, so we go down

the middle. Our next character is not a match so

[COUGH] we go to the left, and it's a null link but we have a node that we want

to put there. That's the one corresponding to the

second letter, in sell's so we do that, and then we make nodes with middle links,

going until we get to the last character in sell's, and we associate that with the

value 1. So, what about SEA, let's see how that

one works. so, first character is S, so I take the

middle link, second character is e which is less than h and not a match so we move

to the left and continue looking for the e.

now this node we find the e, so we take a middle link, and move to the next node

[COUGH] next character which is a, a is less than l.

it's not a match so we go to the left, that's a null linl, and that's where we

put our a, and we associate it with the value 2.

OK, here's sh, shells so we have a match at s, go to the middle link, and go to

the next letter, match h middle link next letter.

and then we go down and add the three nodes corresponding to the last three

letters and put a three at the node corresponding to the last letter.

OK? now B Y we look at S not a match it's

less, so we're going to go to the left, that's a null link.

That's where we put our first character, and then we go down the middle link to

add the node for the last character,and then ah,associate the value for there.

and then B is a similar thing on the right.

And then go for the t and h and e, and that gets our share with the value 5.