普林斯顿大学：平衡查找树（PPT讲稿）New Balanced Search Trees

Tree height Theorem. a rank-balanced tree built by m insertions intermixed with arbitrary deletions has height at most logo, m If m=n, same height as avl trees Overall height is mint(2g A \ Geny

Tree Height Theorem. A rank-balanced tree built by m insertions intermixed with arbitrary deletions has height at most logm. If m = n, same height as AVL trees Overall height is min{2lg n, logm}

Rebalancing frequency Theorem. In a rank-balanced tree built by insertions and d deletions the number of rebalancing steps of rank k is at most (m+d)/2k/) Exponentially better than o((m +d)/k) Good for concurrent workloads Similar result for red-black trees(b=21/2)

Rebalancing Frequency Theorem. In a rank-balanced tree built by m insertions and d deletions, the number of rebalancing steps of rank k is at most O((m + d)/2k/3). Exponentially better than O((m + d)/k) Good for concurrent workloads Similar result for red-black trees (b = 2 1/2)

Exponential analysis Exploit exponential structure of tree use an exponential potential function

Exponential analysis Exploit exponential structure of tree … use an exponential potential function!