伸展操作的攤還分析（splay operations）
/ splay rhymes with play /
伸展樹是一棵完全不儲存平衡資訊的二元搜尋樹——沒有顏色，沒有高度欄位。它唯一的想法是：每次你碰到一個節點（搜尋、插入、刪除），你就「伸展」它：一步步旋轉，直到它成為根。這把最近用過的項目移到頂端附近，使它們再次取用很快。個別操作並不平衡，單一次伸展可能很慢，但對任何序列，這棵樹表現得和平衡樹一樣好。攤還分析是看清原因的唯一辦法。
伸展把被存取的節點 x 以叫做 zig-zig 與 zig-zag 的雙步（加上頂端的單步 zig）旋轉到根，沿途大致把存取路徑上每個節點的深度減半——與並查集路徑壓縮同樣的自我壓平精神。分析用位勢法配上巧妙的選擇：給每個節點一個權重，把「大小」s(x) 定義為 x 子樹中的總權重，「秩」r(x) = log2(s(x))，並令位勢 Phi 為所有節點 r(x) 之和。證明的核心是存取引理（Access Lemma）：伸展 x 的攤還成本至多 3*(r(根) - r(x)) + 1。因為秩是子樹大小的對數，這疊縮得很漂亮——昂貴的深層伸展正是那些大幅降低位勢的操作，替自己買單。對序列求和得到每操作攤還 O(log n)。
這個分析是位勢法的招牌應用，而且它帶來的不只是一棵普通平衡樹：伸展樹免費取得數個更強的攤還性質，如靜態最優定理（對任何存取序列，落在最佳固定二元搜尋樹的常數因子之內）以及對最近用過的鍵的快速存取。誠實的提醒：這裡每個界都是攤還的，所以某一次特定伸展在爬長路徑時可能花 Theta(n)；位勢的選擇（各子樹大小取對數之和）是沒有食譜可給你的困難創意步驟；而且儘管伸展樹在 O() 意義上與平衡樹相當，它們的常數因子與額外旋轉有時使它們在實務上比紅黑樹慢。
在一條長的右傾鏈中存取一個深層節點 x。伸展做一串 zig-zig 步驟，把 x 提到根並把它經過的每個節點深度減半。那一次存取很昂貴，但它留下的樹淺得多，所以接下來的存取便宜——位勢 Phi（子樹大小對數之和）急降，替那次昂貴的伸展付了款。
位勢 = 各節點 log(子樹大小) 之和；深而昂貴的伸展使它急降，所以每個操作攤還成 O(log n)。
伸展樹的 O(log n) 是攤還的，不是逐操作的最壞情況：單一次伸展仍可能是 Theta(n)。位勢（子樹大小對數之和）是讓證明成立的靈感選擇——沒有通用食譜能生出它。