LeafBased23Trees Flashcards
What is a 2-3 tree? What is it’s guarantee? How does it compare to a Binary Tree?
What is the recursive definition of a 2-3 Tree
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)
- Is this tree a 2-3 tree Shape?
Yes
- Is this tree a 2-3 tree shape?
No
- Is this tree a 2-3 tree shape?
No
- Is this tree a 2-3 tree shape
Yes
In general how is information stored in a 2-3 tree?
- 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
Draw an interior node v with two children Tl and Tr
Draw an interior node v with three children Tl and Tr
12! just count the leaves, they are the only thing that can store data
In general how do you search in a 2-3 tree?
In general how does an insert work with a 2-3 tree?
- 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
How would this tree change when pi is added?
How does a two-child parent insert work if the new leaf’s key is < Lsearch’s key?
Draw how you would insert 43 into the following tree:
What is the solution to the following?
Draw what the insert would look like for the following tree:
Draw what the first two insertions into an empty 2-3 tree?
Draw (iteratively) inserting 1,2,3…8 into a 2-3 tree
How do you traverse a leaf-based 2-3 tree?
What is the Psudo code for traversing a leaf-based 2-3 tree in sorted order?
What is the height of a 2-3 tree containing n keys?
Draw the following:
What is the efficiency of a search, insert, deletion of a 2-3 tree?
