A tree where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements.
Questions tagged [2-3-tree]
22 questions
5
votes
1 answer
Preference between an AVL tree and a 2-3 tree
can someone tell me if using an AVL is preferred over using a 2-3 tree or vice-versa and why so?
Thx
Melvic
- 51
- 1
- 4
4
votes
1 answer
Some doubts about Prolog implementation of 2-3 Dictionary
I am learning Prolog using SWI Prolog and I have some doubts about how work this implementation of the 2-3 dictionary in Prolog.
I know the theory of the 2-3 dictionary that are trees whose internal nodes can generate 2 or 3 subtrees having the…
AndreaNobili
- 40,955
- 107
- 324
- 596
2
votes
1 answer
Time complexity of insertion and removing in 2-3 trees
Why do insertion and removing operations in 2-3 tree always have complexity of O(logn), is there a mathematical proof?
Аяз Хуснутдинов
- 95
- 1
- 6
1
vote
1 answer
What is the best-case performance of the insertion operation in 2-3 tree, in Big-O notation?
I had the following question on my data structures midterm.
What is the best-case performance of the insertion operation in a 2-3 tree, in Big-O notation?
I gave as answer:
O(1), assuming that the tree is empty
It was marked as wrong. The answer…
summrs
- 11
- 2
1
vote
1 answer
Finding the number of nodes in 2-3 tree while left sub-tree of the root has 3 children,right sub-tree of the root has 2 children
Suppose there is a 2-3 tree with n nodes.
Each node in the left sub-tree of the root has 3 children. (except the leaves).
Each node in the right sub-tree of the root has 2 children. (except the leaves).
How am I supposed to find how many nodes exist…
Algo
- 185
- 6
1
vote
1 answer
recursion not navigating all child nodes
I need to navigate my 23Tree and print all the levels and corresponding elements. However, my recursion goes in any one direction and does not return and perform other calls. Any help would be much appreciated.
Here is my node class:
class Node
Ahmad Shafique
- 27
- 2
- 8
1
vote
1 answer
Finding the correct ancestor in a 2-3 Tree
So I am having trouble finding the correct ancestor in a 2-3 Tree. In a 2-3 Tree of arbitrary height, there are a couple of cases to look for.
My nodes are designed as follows:
template
struct node{
Node *child1;…
Saggitori
- 19
- 2
1
vote
0 answers
How to know if it's a 2-node or 3-node in a 2-3 tree?
I have a binary search tree, and I created a struct for the node that represents one element and the child to its left, yet, I cannot figure out the mechanism on how to check if it's a 2 node, with one element and two children or if it's 3 node,…
Hoang Minh
- 1,066
- 2
- 21
- 40
0
votes
0 answers
show that n insertions in a 2-3 tree can be done in order O(n)
I have to probe that n insertions in a 2-3 tree can be done in order O(n). I know that one insertion in the worst case is O(log2(n)), but what happens when I try n insertions...
I don't know what to do, help
0
votes
0 answers
Best way to find the number of elements in a 2-3 tree
I tried finding the total number of values in a 2-3 tree using inorder traversal and instead of printing the values in the node, I tried incrementing the initalised int value everytime there is a value; however, this method didn't seem to work.
Is…
Xenotion
- 13
- 3
0
votes
1 answer
Job interview question in 2-3 trees (B trees)
This is a part of job interview question which got harder in its second part.
Given two 2-3 trees T1 and T2 such that for each tree h in known (h for height) and m, M for each tree are known too (m for minimum and M for maximum), Plus that each node…
user14826913
0
votes
1 answer
What kind of decisions to consider while choosing the type of a self-balanced BST?
For instance I know the concept and ideas of 2-3 tree and Red-black tree, but could you give me some situations where one of them is better then the other? What questions should I be asking to myself?
As the question is not just about 2-3 tree and…
Alk
- 313
- 4
- 13
0
votes
0 answers
2-3 (two-three) tree inserting method c#
I have problem implementing a 2-3 tree insert method in C#. I have working B tree simple implementantion and on that basis i need to create inserting method for 2-3 tree. I watched videos how 2-3 tree work but i don't know how to implement that in…
Pavle
- 9
- 2
0
votes
1 answer
Iterator object for a 2-3 Tree
I needed help with the iterator for a 2-3 Tree. The way I am implementing right now is a recursive approach which is almost similar to DFS. I initialize the traversal from the root, visit it's left branch until I hit a leaf node, and then add it to…
codecode
- 27
- 8
0
votes
0 answers
Deletion from root in a 2-3 tree
i have the following 2-3 Tree:
D I P X,Y
i need to delete "L" and then "X" from it, but i cant find material regarding…
Tim von Känel
- 301
- 2
- 12