演算法 日更 第四十五期 靜態二叉排序樹(建立)

2022-11-24 17:26:16 字數 1101 閱讀 6261

▎前言

小編雖然已經會了二叉排序樹,但是卻不明白靜態二叉排序樹和二叉排序樹有什麼關係。

結合平衡二叉排序樹(例如:紅黑樹)食用本篇部落格,效果更佳哦~

傳送門(同時也內含二叉排序樹的相關知識)

▎靜態二叉排序樹

☞『引入』

這個東西要從線段樹說起,別問我為什麼扯這麼遠。

戳這裡快速上手線段樹。

不得不說,線段樹是個好東西,每次都會把一個區間劈成左右兩半,運用了分治的思想。

比如說:線段樹總是定義過多的l,r,mid指標來指向區間,這就是冗餘資訊;

再比如說:線段樹的節點是用來儲存區間的,而在處理點的問題時,是不需要的,這就是冗餘資訊。

還有:在處理點時,線段樹的區間一分為二,是通過一個分割點的,只要保留這個分割點就可以了。

像這樣的冗餘資訊不止這些,但是如果我們換成二叉排序樹就不同了。

☞『定義』

個人認為二叉排序樹和靜態二叉排序樹在定義上沒有區別。

☞『特點』

用例子來說吧:

比如說現在有這樣一組資料:3,6,9,2,5,4,1。

先明確一下位置關係:

假設當前節點為i,那麼左子樹編號為i×2,右子樹編號為i×2+1,所以我們用陣列進行儲存的時候就是按照這個規律來儲存的。

先建立一個對映x=(說白了就是排序一遍)。

接著用這個對映按照二叉排序樹的性質開始填入:

發現規律了嗎?1,2,3,4,5,6,9恰好是這棵樹的中序遍歷順序。

也就是說靜態二叉排序樹插入點是靠中序遍歷的,但是二叉排序樹不一樣,插入方式和搜尋時很像。

▎靜態二叉排序樹的查詢

這個很簡單吧,直接上**:

1

void build(inti)2

▎靜態二叉排序樹的優點

容易看出,靜態二叉排序樹及其相似滿二叉樹,有時就是!

所以靜態二叉排序樹天生就是平衡樹。