Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

Discussion on Random Binary Search Trees

Discover the theory and implementation of random binary search trees and treaps. Learn about their expected height, priority hashing methods, and randomized algorithms for adding and removing elements. Understand how subtree sizes aid in efficient rank-based access and how these structures maintain balance and performance within Python data structures.

We'll cover the following...

Additional notes

Random binary search trees have been studied extensively. DevroyeL. Devroye. Applications of the theory of records in the study of random trees. Acta Informatica, 26(1):123–130, 1988. gives a proof of the lemmaThe lemma is about the length of search path in a binary search tree. and related results. There are much stronger results in the literature as well, the most impressive of which is due to ReedB. Reed. The height of a random binary search tree. Journal of the ACM, 50(3):306–332, 2003., who shows that the expected height of a random binary search tree is

αln⁡n−βln⁡ln⁡n+O(1)\alpha\ln n - \beta\ln\ln n + O(1) ...