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.
