20.3

[Tory S. Anderson]

Can someone please explain to me what the binary search tree described by:
    12 / \ 8 23 /\ / \ 1 9 15 29
is? I don't understand that notation.

[JD]

[Conclusory !]

You can look at it as a binary search tree where, for the root (top) node, the key is 12, its left is 8, and its right is 23.

For the left branch:  Key = 8, left = 1, right = 9

For the right branch: Key = 23, left = 15, right = 29

For the leaves (the ones at the bottom, or 1,9,15,29), the left and right values are empty binary search trees.

Remember that, for a BST, the key for the left is always lesser than the parent node key and the right is always larger.  Also, we do not have to enforce this, but assume that this is always the case (which it is in Jay's provided tree).

I hope that helps.

--

Kevin C.

[Joe Larson]

Can someone explain what a "node" is. I don't know what it means by
"What is the fewest number of new nodes that must be created..."

[Tory S. Anderson]

Thanks! And, if I understand correctly, the initial value for each of these keys should be a string containing the Japanese version of the number? Japanese 8, Japanese 1, etc?

[Jay McCarthy]

BST it = new Node( 12, "十二", new Node( 8, "八", new Node( 1, "一", mt,
mt ), new Node( 9, "九", mt, mt ) ), new Node ( 23, "二十三", new Node(
15, "十五", mt, mt ), new Node( 29, "二十九", mt, mt ) ) )

2011/6/15 JD <bian...@gmail.com>:

--
Jay McCarthy <j...@cs.byu.edu>
Assistant Professor / Brigham Young University
http://faculty.cs.byu.edu/~jay

"The glory of God is Intelligence" - D&C 93

[Conclusory !]

There are two parts to each node, besides the left and right: the key (an int) and the value (a String).

In the assignment, we are looking for a key and updating the value associated with it.

And you are welcome :-)

--

Kevin C.

[Conclusory !]

Thanks Jay.  I was about to look those up.

--

Kevin C.

[Conclusory !]

Look at the previous emails in this thread.

A node is the unit of each part of the BST.  You can think of it as "OneMoreBST", if that helps.

--

Kevin C.

[Jay McCarthy]

And the very first assignment about BST defined them that way.

2011/6/15 Conclusory ! <concl...@gmail.com>:

--

[Cody Johnson]

I copied this and the symbols didn't copy over. They came across
as ??. Should I just make up symbols?

On Jun 14, 8:10 pm, Jay McCarthy <jay.mccar...@gmail.com> wrote:
> BST it = new Node( 12, "十二", new Node( 8, "八", new Node( 1, "一", mt,
> mt ), new Node( 9, "九", mt, mt ) ), new Node ( 23, "二十三", new Node(
> 15, "十五", mt, mt ), new Node( 29, "二十九", mt, mt ) ) )
>

> 2011/6/15 JD <bianc...@gmail.com>:

>
> >     12
> >    /  \
> >  8     23
> > /\   /   \
> > 1 9 15   29
>
> --
> Jay McCarthy <j...@cs.byu.edu>

> Assistant Professor / Brigham Young Universityhttp://faculty.cs.byu.edu/~jay

[Jay McCarthy]

That's only an example, you don't need to do anything with it for the assignment

2011/6/15 Cody Johnson <codybea...@gmail.com>:

[Tory S. Anderson]

What's the best way to depict / toString() a BST? At the moment I have it printing
    一十二 : 八 : 一 : ! : ! : 九 : ! : ! : 二十三 : 十五 : ! : ! : 二十九 : ! : !

which works to see if a certain value has been changed, but is hardly readable for the structure of the tree. Should I just spit out the code for it (ex. "new Node(....))" Or is the way I am doing it sufficient?

[Diego (TA)]

The toString method is for your own convenience, so it's sufficient if you it helps you the way you want it to. You could also have it spit out the code for new Node(...), again, depending on what you want it to do for you.

[Tory S. Anderson]

Okay. So there is no standardized way of representing a node without resorting to ASCII art, and there won't be any problem if I perform my comparisons and store tracking in the above format?

[Jay McCarthy]

The format you picked isn't very good because it doesn't show the
structure. For situations like this, I like to use the constructor
format so it looks like Java code, i.e. new Node( ..., ..., ... )

Jay

2011/6/15 Tory S. Anderson <torys.a...@gmail.com>:

--

[Tory S. Anderson]

Oops. didn't see this in time.