CODEWITHSUNDEEP
performancetreebinary-treered-black-treeoperation
Spectraljump
Spectraljump

Reputation: 4637

Why are Red_Black trees better than 2-3 trees?

Apart from red-blacks being easier to implement.

All operations (insertion, deletion, lookup) seem to have a time complexity of O(log n), in both trees. Is there a certain difference between these operations that I'm missing?

If you google search "red-black" "2-3 tree", you don't find any comparison between the two..

I've come to understand that red-blacks are generally considered to be the best. (I've heard that one of the reasons [EDIT] why red-blacks are faster than AVL trees (same category)[/EDIT] is efficiency in "application to persistent data structures", because of rebalancing efficiency; but that doesn't answer my question..)

Upvotes: 3

Views: 840

Answers (2)

Justin Niessner
Justin Niessner

Reputation: 245419

Straight from the Wikipedia entry for B-Trees (of which the 2 3 tree is a type of):

Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.

Upvotes: 1

jon_darkstar
jon_darkstar

Reputation: 16768

I'm not familiar with 2-3 trees, but I am pretty sure that B-Trees are by far the preferred for persistent database/filesystems. Red/Black more often used in memory

Upvotes: 2

Related Questions