A4Q2

[Chris Jones]

Hello,

I am confused about the properties of 2-3-4 trees as they relate to
all the possibilities in Q2.

I know a level can have 1,2, or 3 keys and 2,3, or 4 children,
respectively
I know the children have the properties <a, a-b,b-c,>c

Are all leaves the same distance from the root, or is that only for
balanced 2-3-4 trees? Can we have an unbalanced 2-3-4 tree?

Are all leaves of one key, or can it have 1,2 or 3 keys?

Am I missing any other relevant properties of a 2-3-4 tree?

Thanks in advance,

Chris

[Chris Jones]

Also, I think this is covered by the balance 2-3-4 tree part, but can
you have a level with N keys and < N children. eg. Partial leaf

[cs240]

I'm not sure I understand your questions, can you give me a specific
example?

If by a level, you actually meant a node, then no, a node with N keys can
only have N+1 child nodes.

Vivian
CS240 Tutor

Post by Chris Jones
Also, I think this is covered by the balance 2-3-4 tree part, but can
you have a level with N keys and < N children. eg. Partial leaf

[cs240]

Hi Chris,

B-Trees are strictly balanced trees, which means that all leaf nodes are
at the same level. 2-3-4 trees are just B-tree of minimum degree 2,
therefore they are always balanced as well. Leaf nodes in a 2-3-4 tree can
have 1,2, or 3 keys.

Vivian
CS240 Tutor

Post by Chris Jones
Hello,
I am confused about the properties of 2-3-4 trees as they relate to
all the possibilities in Q2.
I know a level can have 1,2, or 3 keys and 2,3, or 4 children,
respectively
I know the children have the properties <a, a-b,b-c,>c
Are all leaves the same distance from the root, or is that only for
balanced 2-3-4 trees? Can we have an unbalanced 2-3-4 tree?
Are all leaves of one key, or can it have 1,2 or 3 keys?
Am I missing any other relevant properties of a 2-3-4 tree?
Thanks in advance,
Chris

[acchow]

So then a non-leaf node with N keys can ONLY have N+1 children (it can't
have N children, or N-1 children?), yet a leaf node with N keys will
(since it's a leaf) have no children?

Post by cs240
Hi Chris,
B-Trees are strictly balanced trees, which means that all leaf nodes are
at the same level. 2-3-4 trees are just B-tree of minimum degree 2,
therefore they are always balanced as well. Leaf nodes in a 2-3-4 tree
can have 1,2, or 3 keys.
Vivian
CS240 Tutor

Post by Chris Jones
Hello,
I am confused about the properties of 2-3-4 trees as they relate to
all the possibilities in Q2.
I know a level can have 1,2, or 3 keys and 2,3, or 4 children,
respectively
I know the children have the properties <a, a-b,b-c,>c
Are all leaves the same distance from the root, or is that only for
balanced 2-3-4 trees? Can we have an unbalanced 2-3-4 tree?
Are all leaves of one key, or can it have 1,2 or 3 keys?
Am I missing any other relevant properties of a 2-3-4 tree?
Thanks in advance,
Chris

[cs240]

Yes, that's right. A review of the basic B-tree properties (slide 95) is a
good preparation for the midterm.

Vivian
CS240 Tutor

So then a non-leaf node with N keys can ONLY have N+1 children (it can't have
N children, or N-1 children?), yet a leaf node with N keys will (since it's a
leaf) have no children?

Post by cs240
Hi Chris,
B-Trees are strictly balanced trees, which means that all leaf nodes are
at the same level. 2-3-4 trees are just B-tree of minimum degree 2,
therefore they are always balanced as well. Leaf nodes in a 2-3-4 tree
can have 1,2, or 3 keys.
Vivian
CS240 Tutor

Post by Chris Jones
Hello,
I am confused about the properties of 2-3-4 trees as they relate to
all the possibilities in Q2.
I know a level can have 1,2, or 3 keys and 2,3, or 4 children,
respectively
I know the children have the properties <a, a-b,b-c,>c
Are all leaves the same distance from the root, or is that only for
balanced 2-3-4 trees? Can we have an unbalanced 2-3-4 tree?
Are all leaves of one key, or can it have 1,2 or 3 keys?
Am I missing any other relevant properties of a 2-3-4 tree?
Thanks in advance,
Chris