Stack Overflow
Stack Overflow

Questions tagged [2-3-4-tree]

A 2–3–4 tree (also called a 2–4 tree) is a self-balancing data structure that is commonly used to implement dictionaries. The numbers mean a tree where every node with children (internal node) has either two children (2-node) and one data element or three children (3-node) and two data elements or four children (4-node) and three data elements.

A 2–3–4 tree (also called a 2–4 tree) is a self-balancing that is commonly used to implement dictionaries.

The numbers mean a where every node with children (internal node) has either two children (2-node) and one data element or three children (3-node) and two data elements or four children (4-node) and three data elements.

2–3–4 trees are s of order 4; like B-trees in general, they can search, insert and delete in O(log n) time. One property of a 2–3–4 tree is that all external nodes are at the same depth.

33 questions
48
votes
1 answer

What additional rotation is required for deletion from a Top-Down 2-3-4 Left-leaning Red Black tree?

I have been implementing an LLRB package that should be able to operate in either of the two modes, Bottom-Up 2-3 or Top-Down 2-3-4 described by Sedgewick (code - improved code, though dealing only with 2-3 trees here, thanks to RS for…
kortschak
  • 755
  • 5
  • 21
11
votes
1 answer

Converting a 2-3-4 tree into a red black tree

I'm trying to convert a 2-3-4 Tree into a Red-Black tree in java, but am having trouble figuring it out. I've written these two basic classes as follows, to make the problem straightforward, but can't figure out where to go from here. public class…
user3745602
  • 315
  • 1
  • 3
  • 12
9
votes
3 answers

Why dont we use 2-3 or 2-3-4-5 trees?

I have a basic understanding of how 2-3-4 trees maintain the height balance property operation after operation to make sure even the worst case operations are O(n logn). But I do not understand it well enough to know why only 2-3-4? Why not 2-3 or…
Lazer
  • 90,700
  • 113
  • 281
  • 364
6
votes
1 answer

How are red-black trees isomorphic to 2-3-4 trees?

I have a basic understanding of both red black trees and 2-3-4 trees and how they maintain the height balance to make sure that the worst case operations are O(n logn). But, I am not able to understand this text from Wikipedia 2-3-4 trees are an…
Lazer
  • 90,700
  • 113
  • 281
  • 364
5
votes
2 answers

Finding the minimum value of a 2-3-4 tree

First off, this question isn't homework. I'm currently reading the book "Data Structures and Algorithms 2nd Edition" by Robert Lafore. In chapter 10, we learned about 2-3-4 trees and are then asked to write a method to find the minimum value in said…
Alex
  • 2,145
  • 6
  • 36
  • 72
5
votes
2 answers

Why the node split when inserting into 2-3-4 tree?

In the depicted 2-3-4 tree below (from Data Structures & Algorithm in Java, 2nd ed), why does inserting 99 cause the node split of 83/92/104 when it seems like 99 could've been inserted into the right child (the C child, into the spot immediately…
tony19
  • 125,647
  • 18
  • 229
  • 307
4
votes
1 answer

Usage, pros and cons for binary search tree, 2-3 tree and B-tree

i was reviewing the materials from my data structure class and i am kind of confused with the usage of these three kinds of trees. so what are the situations that we should better use binary search tree, 2-3 tree and B-tree respectively? and what…
user3337625
  • 91
  • 1
  • 3
  • 7
2
votes
1 answer

Real-World Performance of Red-Black vs. 2-3-4 trees, especially considering cache performance?

A single node of a 2-3-4 tree could be constructed with 8 pointers: pointers to up to four child nodes, pointers to up to 3 actual records containing keys that will either match a search key or will determine which of 4 child nodes to recurse to,…
Swiss Frank
  • 1,985
  • 15
  • 33
2
votes
1 answer

234-Tree insertion method issues

I am having an issue adding values that would create a new level in my 234 tree beyond the first level. My method creates children on the root object but fail to create children for any other node. I am able to create and insert a given number of…
Sinil
  • 87
  • 10
1
vote
2 answers

Search for words with telephone numbers from 2-3-4 tree

I have a dictionary of words put in an 2-3-4 tree. Words have different lengths. Using a telephone keypad i need to find all possible words that can be responding to a specific phone number. Given the keypad: for instance the number 26678837 could…
Chris Costa
  • 653
  • 4
  • 15
1
vote
1 answer

Using a 2-3-4 tree instead of a splay tree

I'm in a data structures course right now and we learned about 2-3-4 trees and splay trees. I was wondering in what circumstances would you use a 2-3-4 tree instead of a splay tree? They're both self balancing and sorted so I don't see that much…
user479988
  • 56
  • 5
1
vote
1 answer

in 2,3,4 tree do you insert a 3rd element only in a leaf node?

Suppose I am entering 3 elements into a top-down 2,3,4 tree. Would all the three elements go into root? For subsequent inserts would a 3rd element be inserted into a node only if its a leaf node (or into a node when a key kicked up when you…
Foo
  • 4,206
  • 10
  • 39
  • 54
1
vote
0 answers

BST and 2-3-4 Tree heights

I have the following problem: Suppose T1 is a binary search tree and T2 is a 2-3-4 tree and they have each been formed from the same number of keys S. Let H1 be the height of T1 and H2 be the height of T2. i. Briefly explain why H1 is less than or…
Diana
  • 1,417
  • 5
  • 25
  • 48
1
vote
1 answer

Deletion of an internal node in 2-3-4 tree

I want to delete the 15 from the following 2-3-4 tree. I thought of simply moving the 17 up, but I don't know whether that is correct since it has to be complete. Delete 15 from the following tree: How will the 2-3-4 tree look like after deletion?…
user3125591
  • 113
  • 5
  • 13
1
vote
1 answer

inserting into 2-3-4 tree number of nodes

I am implementing 2-3-4 tree for some kind of memory managment.During init of my application I want to insert there some number of integers (get it as input - say n) What is a complexity of such an insert? O(nloglog(n))?
YAKOVM
  • 9,805
  • 31
  • 116
  • 217
1
2 3