2-3 Search Tree

Question 1

What is a 2-3 search tree?

Answer 1

Tree that is either empty or
* a 2-node, with one key and two links
* A 3-node with two keys and three links

Question 2

at is

What are the amount of compares for Search and Insert in the worst case?

Answer 2

lg N

Question 3

How do we search a 2-3 tree?

Answer 3

Self explanitory

Question 4

How do we insert into a 2-node?

Answer 4

Replace node with 3 node containing its key and new key to be inserted

Question 5

How do we insert into a 3 node?

Answer 5

There are three cases:
* Single 3-node: Create 4 -node, splut into 2-3 tree where middle key is at root.
* 2-node parent: Same as above, move middle up to create a new 3-node
* 3-node parent: Split up into parent, perform operation on parent