# 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

- Is this tree a 2-3 tree Shape?

A

Yes

4

Q

- Is this tree a 2-3 tree shape?

A

No

5

Q

- Is this tree a 2-3 tree shape?

A

No

6

Q

- Is this tree a 2-3 tree shape

A

Yes

7

Q

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

A

- Each data item has a key and contains more than just a key(other information)
- All data is stored in the leaves
- The values of interior(non-leaf) nodes are just index values to guide a search to the correct leaf
- 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

- Search for the insertion key ki all the way to a leaf Lsearch
- Always insert the new data item in a new leaf (so go to leaves)
- If leaf Lserach contians insertion key ki, then the insert ends
- 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

- If a three-child parent
- Parent has no room for a new child, cannot have 3
- split the parent into two 2-child parents and push the middle index value up to the grand parent