最佳化二元搜尋樹

計算器科學中, 一個最佳二叉搜尋樹BST),有時也被叫做重量平衡二叉樹, 是有可能在已知的一串序列中得到最短搜尋時間的一棵二叉搜尋樹(或期望的搜尋時間)。 最最佳化二叉搜尋樹可分為兩種:靜態的和動態的。

基本介紹

  • 中文名:最佳化二元搜尋樹
  • 外文名:Optimal binary search tree
簡介,樹旋轉,期望值,

簡介

計算器科學中,一個最佳二叉搜尋樹BST),有時也被叫做重量平衡二叉樹,是有可能在已知的一串序列中得到最短搜尋時間的一棵二叉搜尋樹(或期望的搜尋時間)。最最佳化二叉搜尋樹可分為兩種:靜態的和動態的。
靜態的最最佳化問題中,在完全被創建好之前,這棵樹是不能被修改的。在這狀況中,在這棵樹中的每個節點都存在特定的設計,這些設計是依照每個節點被訪問的機率去設計出會得到最短的搜尋時間。不同的算法能依照每筆數據所給的訪問機率去創建或逼近地做出一個靜態的最最佳化樹。
動態的最最佳化問題中,這棵樹可以在任何時間被修改,是允許運行樹旋轉的。這棵樹有一個從樹的根開始的指針,他可以借著移動並使用他去修改一棵樹。在這狀況里,一定會有一連串序列是有著最小的花費,使得這個指針要去走訪整棵樹去找出這個序列。伸展樹被推測和動態最最佳化樹在任何的情況下都有一個常量比率存在,雖然這還沒有被證明出來。

樹旋轉

離散數學中,樹旋轉(英語:Tree rotation)是在二叉樹中的一種子樹調整操作, 每一次旋轉並不影響對該二叉樹進行中序遍歷的結果. 樹旋轉通常套用於需要調整樹的局部平衡性的場合。

期望值

機率論統計學中,一個離散性隨機變數期望值(或數學期望、或均值,亦簡稱期望,物理學中稱為期待值)是試驗中每次可能的結果乘以其結果機率的總和。換句話說,期望值像是隨機試驗在同樣的機會下重複多次,所有那些可能狀態平均的結果,便基本上等同“期望值”所期望的數。需要注意的是,期望值並不一定等同於常識中的“期望”——“期望值”也許與每一個結果都不相等。(換句話說,期望值是該變數輸出值的平均數。期望值並不一定包含於變數的輸出值集合里。)

熱門詞條

聯絡我們