Skip Lift: A Probabilistic Alternative to Red-Black Trees

DOI10.1007/978-3-642-19222-7_23zbMath1326.68109OpenAlexW2020287344MaRDI QIDQ3000510

Karim Douïeb, Prosenjit Bose, Pat Morin

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_23

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A balanced search tree O(1) worst-case update time
• Biased skip lists
• Updating a balanced search tree in 0(1) rotations
• Randomized search trees
• Organization and maintenance of large ordered indexes
• Rank-Balanced Trees
• Biased Search Trees
• Two New Kinds of Biased Search Trees
• Randomized binary search trees
• A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
• Power balance and apportionment algorithms for the United States Congress
• Optimal finger search trees in the pointer machine

This page was built for publication: Skip Lift: A Probabilistic Alternative to Red-Black Trees