Balanced 3-Way Search Tree Structure Overview
Explore the concept of a balanced 3-way search tree structure with internal nodes as 2-nodes or 3-nodes and leaf nodes containing one or two data elements. Learn about the differences between Binary Search Trees and 2-3 Trees, their characteristics, and advantages. Discover the features and insertion methods of 2-3 Trees for efficient data organization and searching.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
What you need Just paper today https://www.cs.usfca.edu/~galles/visualization/BTree.html To check your answer
CSCE-221 2-3 Trees Emil Thomas 04/05/19 Prof. Lupoli 11/5/20
General Concept of the Structure Balanced 3-Way(Up to 3 children/node) Search Tree. Each internal node is a 2-node or 3-node 2-node : Two children and one data element (Also called Keys) 3-node : Three children and 2 data elements Leaf Nodes have no children and can hold one or two data elements
Why do I care? - Binary Search Tree vs 2-3 Tree Binary Search Tree 2-3 Tree In BOTH cases, crappy unfortunately ordered data arrives
Internal 2 Node k1 T1 T2 One Data Element (k1) All keys in first subtree T1, All keys in the Last subtreeT2, : keys(T1) < k1 : keys(T2) >= k1
Internal 3-Node k1 k2 T3 T T1 T2 k1 < k2 (Sorted keys) All keys in first subtree T1, All keys in the 2nd Subtree T2, All keys in last subtree T3, : keys(T1) < k1 : k1 <= keys(T2) < k2 : keys(T3) >= k2
Features Each internal node has either 2 or 3 children All leaves are at the same level The keys in the node is in sorted order Balanced with height O(log N)
Binary Search Tree vs 2-3 Tree Binary Search Tree Both trees has the same data. Which of these can search for 32 faster ? Why ? 2-3 Tree
Inserting Items Insert 37 Starting from the root, search for the leaf node to insert the value By Comparing the value to insert with the keys in the node Insert in the found Leaf and fix if the leaf is overcrowded(3 keys)
Inserting Items Insert 36 Split the overcrowded leaf and move the median value up to parent; insert in leaf Continue splitting (if overcrowded) recursively to the root overcrowded node
Inserting Items ... still inserting 36 Split the overcrowded node into two 2-nodes, move median value up to parent, attach children to smallest and largest result
Inserting Items Create a new root if necessary Tree grows at the root
Short Exercise & Demo Construct a 2-3 tree with the following values: {12, 4, 9, 20, 2, 17, 6} . Try on your own first, then view the solution here
Insertion with Bottoms up Splitting Complexity of Insertion : O(log N) Source : wikipedia
Searching a key in 2-3 Tree Iterator search(root, key) Searching Complexity : O(log N) Similar to searching an item in BST Start from the root; Compare the keys in each node with key If the key is in that node we are done and return the iterator to it If not identify the subtree to recurse down by comparing key to nodes keys. 1 comparison for 2-node and 2-comparisons for 3-node. Continue searching till leaf IF the key is not in leaf, we return key not found (i.e end iterator)
Demonstration of insertion into 2-3 Tree https://www.cs.usfca.edu/~galles/visualization/BTree.html
Exercise Handout Draw each step of inserting these numbers into a 2-3 Tree Please write down the numbers below 87, 78, 77, 27, 64, 91, 93, 24, 30, 2, 45, 16
References http://www.cse.iitd.ac.in/~mohanty/col106/Resources/234-Trees.pptx https://www.cs.usfca.edu/~galles/visualization/BTree.html https://en.wikipedia.org/wiki/2%E2%80%933_tree
