2-3-4 Tree is a perfectly balanced tree (all leafs are on the same level) with O(log n) worst case time for find, insert and remove operations. As the name suggests every node of the tree has 2,3 or 4 children.
Operations
Find
Insert
Find a node with key k. If a node X with key k is found proceed to X's left until a leaf node is found. If a 3 key node is found we move the middle key up to its parent. Parent has at most two keys.
Fig:
Insertion may increase the depth of tree by one level.
Remove
Find the node X with key k to remove If X is a leaf, remove it ans return from function. If X is an internal node search for a leaf node Y with smallest key k' such that k" > k and replace Replace X with Y so that X is removed and Y takes its place.
If we find a one key node on the path of a leaf node we want to remove we continuously do the following 3 steps (except the root node):
- If X is an one key node that is not root move one key from its adjacent sibling by rotation.
Fig:
- If there is no adjacent sibling with more than one key take one key down from the parent. Internal nodes always have two or three keys. Moving down one key may trigger further operations if the parent is left with one key (verify).
Fig:
- If parent is root and there is no adjacent sibling with more than one key (1 and 2 fails) create a 3 key node to form the root. This is called a fusion operation. The tree level is decreased by one level.
Fig:
Remove may decrease the tree by one level.
Great blog!!!! Thanks for spending time with us.
ReplyDeleteHadoop Training in Chennai
Android Training in Chennai
Selenium Training in Chennai
Digital Marketing Training in Chennai
JAVA Training in Chennai
German Classes in chennai
Big Data Training in Chennai
Hadoop Training in Tambaram
Great Article The IEEE Xplore digital library is your gateway to trusted research—journals, conferences, standards, ebooks, and educational courses—with more than 3 million articles to help you fuel imagination, build from previous research, and inspire new ideas. Node Js Projects for Final Year IEEE will pave a new way in knowledge-sharing and spreading ideas across the globe. Project Centers in Chennai for CSE Node.js Corporate Training JavaScript Training in Chennai
Delete" you have been delivering a useful & unique information to our vision.keep blogging..
ReplyDeleteDigital Marketing Training Course in Chennai | Digital Marketing Training Course in Anna Nagar | Digital Marketing Training Course in OMR | Digital Marketing Training Course in Porur | Digital Marketing Training Course in Tambaram | Digital Marketing Training Course in Velachery
"
Interesting Blog! Very usable information has been shared.
ReplyDeleteDigital Marketing Training Course in Chennai | Digital Marketing Training Course in Anna Nagar | Digital Marketing Training Course in OMR | Digital Marketing Training Course in Porur | Digital Marketing Training Course in Tambaram | Digital Marketing Training Course in Velachery
Really it was an awesome article...very interesting to read..You have provided an nice article.keep it up!!
ReplyDeleteandroid training in chennai
android online training in chennai
android training in bangalore
android training in hyderabad
android Training in coimbatore
android training
android online training