Biased 2-3 Trees

We describe a new data structure for maintaining collections of weighted items. The access time for an item of weight w in a collection of total weight W is proportional to log(W/w) in the worst case (which is optimal in a certain sense), and several other useful operations can be made to work just, as fast. The data structure is simpler than previous proposals, but the running time must be amortized over a sequence of operations to achieve the time bounds.

Authors

• Samuel W. Bent
• Daniel Dominic Sleator
• Robert Endre Tarjan

Keywords

• Dictionaries
• Data structures
• Tree data structures
• Computer science
• Contracts
• Proposals
• Binary search trees
• Costs
• Data Structure
• Total Weight
• Operation Time
• Root Of The Tree
• Subtree
• Tree Search
• Ideal Time
• Recursive Algorithm
• Implementation Performance
• Operator Splitting
• Balanced Tree
• Insertion Operator
• Lighter Ones
• Joining Algorithm
• Number Of Chips