資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時尚研究
法律研究資料結構中 Splay 樹的最優性
動態最優性猜想
除了對 Splay 樹的已證明的效能保證外，還有一個尚未證實的猜想備受關注。動態最優性猜想指的就是這個猜想。令 B 為任意二叉搜尋樹演算法，該演算法訪問元素 y 時的開銷為 d(y) + 1，並在訪問之間以每旋轉一次 1 的開銷進行樹中的任何旋轉操作。記 B(s) 為 B 執行訪問序列 s 時的開銷，則 Splay 樹執行相同訪問時的開銷為 O[n+B(s)]。
動態最優性猜想有很多推論，但這些推論仍然未得到證明
遍歷猜想兩棵 Splay 樹 t1 和 t2 包含的相同元素。將透過前序（即深度優先搜尋順序）訪問 t2 中元素而獲得的序列假設為 s。在 t1 上執行訪問序列 s 時的全部開銷為 O(n)。
雙端佇列猜想定義一系列 s 的 p 個雙端佇列操作（進棧、出棧、插入、彈出）。則在 Splay 樹上執行序列 s 的開銷為 O(p+n)。
分離猜想令 s 為 Splay 樹元素的任意排列。則按順序 s 刪除元素的開銷為 O(n)。
更新時間： 07-01-2020
95 檢視
廣告