Talk:(a,b)-tree

Help, how should I contribute here?

I want to contribute to this article, but I’m not confident I would get the style right. (Very new here.)

First of all, I’d like to revise the introduction to (a,b)-trees. The point is that an (a,b)-tree is a multi-way search tree (more general than a binary search tree, where the keys in a node divide up the universe into ranges, so a search path travels between keys to the right node), with bounds on how many keys are allowed per internal node.

So when we define operations FIND, INSERT, and DELETE, we have to include the step of splitting or joining the nodes of the tree, to meet the (a,b) requirement.

Secondly, I think this could use a section on the amortized time complexity of these operations. This is covered in Martin Mareš' lecture notes on Data Structures: http://mj.ucw.cz/vyuka/dsnotes/03-abtree.pdf If I add this section, should I also include a proof, or should I just cite that source and give the amortized complexity as a fact?

Lastly, I see that there's also an article about B-trees, which are a special case of (a,b)-trees. Should this article be merged with that one?

Yipe! That's me (talk) 19:14, 10 June 2021 (UTC)