-Houraisan-Kaguya

摘要： 考慮一下 splay 的復(fù)雜度分析。 當(dāng)需要遞歸的子樹較大時(shí)，rotate 操作可以使勢能降低。 反之勢能會(huì)上升，但是次數(shù)不會(huì)超過 \(O(\log n)\)。 那么，當(dāng)需要遞歸的子樹較小的時(shí)候?yàn)槭裁床恢苯舆f歸呢？ 算法描述 當(dāng)我們需要插入一個(gè)數(shù)字 \(x\)，當(dāng)前節(jié)點(diǎn)為 \(a\) 時(shí)，進(jìn)行以下操 閱讀全文