2-3-4 TreesIntroductionIntroduction to 2-3-4 TreesPowerPoint PresentationSlide 5More Introductory stuffStill More Introductory stuffEven More Introductory stuffSlide 92-3-4 Tree OrganizationMore on 2-3-4 Tree OrganizationSearching a 2-3-4 TreeTry it: search for 64, 40, 65So, how do we Insert into this Structure?Node Split – a bit more difficult (1 of 2)Node Split – Insertion: more difficult – 2 of 2Insert: Here: Split is NOT the root node. Let’s say we want to add a 99 (from book)…Case 1 Insert: Split is NOT the root node (Let’s say we want to add a 99 (from book)…)If Root itself is full: Split the RootSplitting on the Way DownSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Efficiency ConsiderationsEfficiency Considerations for 2-3-4 TreesSlide 3412-3-4 Trees Chapter 10 – Part 12-3-4 Trees and Related Topics2Introduction•Multi-way Trees are trees that can have up to four children and three data items per node.•2-3-4 Trees: Very nice features–Are always balanced. (What does balanced mean??)–Reasonably easy to program . Serve as an introduction to the understanding of B-Trees!!•B-Trees: another kind of multi-way tree particularly useful in organizing external storage, like files. –B-Trees (later lectures) can have dozens or hundreds of children with hundreds of thousands of records!3Introduction to 2-3-4 Trees•Shape of nodes is a lozenge-shaped.•In a 2-3-4 tree, all leaf nodes are at the same level. (but data can appear in all nodes)5030 60 70 8010 20 40 55 62 64 66 75 83 86304•The 2, 3, and 4 in the name refer to how many links to child nodes can potentially be contained in a given node. • •For non-leaf nodes, three arrangements are possible:–A node with only one data item always has two children–A node with two data items always has three children–A node with three data items always has four children.•For non-leaf nodes with at least one data item ( a node will not exist with zero data items), the number of links may be 2, 3, or 4.5•Non-leaf nodes must/will always have one more child (link) than it has data items (see below); –Equivalently, if the number of child links is L and the number of data items is D, then L = D+1.5030 60 70 8010 20 40 55 62 64 66 75 83 86306More Introductory stuff•Critical relationships determine the structure of 2-3-4 trees:•A leaf node has no children, but can still contain one, two, or three data items ( 2, 3, or 4 links); cannot be empty. (See figure above) Because a 2-3-4 tree can have nodes with up to four children, it’s called a multiway tree of order 4.5030 60 70 8010 20 40 55 62 64 66 75 83 86307Still More Introductory stuff•Binary (and Red Black) trees may be referred to as multiway trees of order 2 - each node can have up to two children.•But note: in a binary tree, a node may have up to two child links ( but one or more may be null).•In a 2-3-4 tree, nodes with a single link are NOT permitted; –a node with one data item must have two links (unless it’s a leaf); –nodes with two data items must have three children; –nodes with three data items must have four children. •(You will see this more clearly once we talk about how they are actually built.)Even More Introductory stuff•These numbers are important. •For data items, a node with one data item: points to (links to) lower level nodes that have values less than the value of this item and a pointer to a node that has values greater than or equal to this value.•For nodes with two links: a node with two links is called a 2-node; a node with three links is called a 3-node; with four links, a 4-node. (no such thing as a 1-node).895030 60 70 8010 20 40 55 62 64 66 75 83 8630Do you see any 2-nodes? 3-nodes? 4-nodes?Do you see: a node with one data item that has two links? a node with two data items having three children; a node with three data items having four children?2-node2-node4-node102-3-4 Tree Organization•Very different organization than for a binary tree.•First, we number the data items in a node 0,1,2 and number child links: 0,1,2,3. Very Important. •Data items are always ascending: left to right in a node.•Relationships between data items and child links is easy to understand but critical for processing.11More on 2-3-4 Tree OrganizationA B CPoints to nodes w/keys < A ; Nodes with key between A and <B Nodes w/keys between B and < C Nodes w/keys > CSee below: (Equal keys not permitted; leaves all on same level; upper level nodes often not full; tree balanced!Its construction always maintains its balance, even if you add additional data items. (ahead) 5030 60 70 8010 20 40 55 62 64 66 75 83 86302-node2-node4-node12Searching a 2-3-4 Tree•A very nice feature of these trees.•You have a search key; Go to root. •Retrieve node; search data items; •If hit: –done.•Else –Select the link that leads to the appropriate subtree with the appropriate range of values.–If you don’t find your target here, go to next child. (notice data items are sequential – VIP later)– etc. Data will ultimately be ‘found’ or ‘not found.’13Try it: search for 64, 40, 655030 60 70 8010 20 40 55 62 64 66 75 83 86302-node2-node4-nodeNote: Nodes serve as holders of data and holders of ‘indexes’.Note: can easily have a ‘no hit’ conditionNote: the sequential nature after indexing…sequential searching within node.14So, how do we Insert into this Structure?•Can be quite easy; sometimes very complex.–Can do a top-down or a bottom-up approach…•Easy Approach:–Start with searching to find a spot for data item.•We like to insert at the leaf level, but we will take the top-down approach to get there… So, –Inserting may very likely involve moving a data item around to maintain the sequential nature of the data in a leaf.15Node Split – a bit more difficult (1 of 2)•Using a top-down 2-3-4 tree. •If we encounter a full node in looking for the insertion point.–We must split the full nodes.•You will see that this approach keeps the tree balanced.16Node Split – Insertion: more difficult – 2 of 2Upon encountering a full node (searching for a place to insert…)1. split that node at that