# LeafBased23Trees Flashcards

1
Q

What is a 2-3 tree? What is it’s guarantee? How does it compare to a Binary Tree?

A
2
Q

What is the recursive definition of a 2-3 Tree

A

A 2-3 tree of height h is defined as follows:

• if h = 0: The tree is the empty tree
• if h = 1: The tree is a single leaf
• if h > 1: The tree has one of two forms

Note: each child of the root is a 2-3 tree and all the children have the same height (the leaves are all on the same level)

3
Q
1. Is this tree a 2-3 tree Shape?
A

Yes

4
Q
1. Is this tree a 2-3 tree shape?
A

No

5
Q
1. Is this tree a 2-3 tree shape?
A

No

6
Q
1. Is this tree a 2-3 tree shape
A

Yes

7
Q

In general how is information stored in a 2-3 tree?

A
1. Each data item has a key and contains more than just a key(other information)
2. All data is stored in the leaves
3. The values of interior(non-leaf) nodes are just index values to guide a search to the correct leaf
1. searches do not stop at an interior node, must end at a leaf
8
Q

Draw an interior node v with two children Tl and Tr

A
9
Q

Draw an interior node v with three children Tl and Tr

A
10
Q
A

12! just count the leaves, they are the only thing that can store data

11
Q
A
12
Q

In general how do you search in a 2-3 tree?

A
13
Q
A
14
Q
A
15
Q

In general how does an insert work with a 2-3 tree?

A
1. Search for the insertion key ki all the way to a leaf Lsearch
2. Always insert the new data item in a new leaf (so go to leaves)
3. If leaf Lserach contians insertion key ki, then the insert ends
4. If Two-child parent of leaf Lsearch
• parents can have three childrend
• so this parent has room for the new leaf containing the new data item
5. If a three-child parent
1. Parent has no room for a new child, cannot have 3
2. split the parent into two 2-child parents and push the middle index value up to the grand parent
16
Q

How would this tree change when pi is added?

A
17
Q

How does a two-child parent insert work if the new leaf’s key is < Lsearch’s key?

A
18
Q
A
19
Q
A
20
Q
A
21
Q
A
22
Q

Draw how you would insert 43 into the following tree:

A
23
Q

What is the solution to the following?

A
24
Q

Draw what the insert would look like for the following tree:

A
25
Q

Draw what the first two insertions into an empty 2-3 tree?

A
26
Q

Draw (iteratively) inserting 1,2,3…8 into a 2-3 tree

A
27
Q
A
28
Q

How do you traverse a leaf-based 2-3 tree?

A
29
Q

What is the Psudo code for traversing a leaf-based 2-3 tree in sorted order?

A
30
Q
A
31
Q

What is the height of a 2-3 tree containing n keys?

A
32
Q

Draw the following:

A
33
Q

What is the efficiency of a search, insert, deletion of a 2-3 tree?

A