4張GIF 圖幫助你理解二叉查找樹

二叉查找樹（Binary Search Tree），也稱二叉搜索樹，是指一棵空樹或者具有下列性質的二叉樹：

任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；

任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；

任意節點的左、右子樹也分別為二叉查找樹；

沒有鍵值相等的節點。

二叉查找樹相比於其他數據結構的優勢在於查找、插入的時間複雜度較低。為O(log n)。二叉查找樹是基礎性數據結構，用於構建更為抽象的數據結構，如集合、multiset、關聯數組等。（摘自維基百科）

下面 4 張 GIF 動圖，是 penjee 官博製作分享。正好伯小樂最近看到，分享給大家。

圖1：查找 BST 中的某個元素

在二叉搜索樹b中查找x的過程為：

若b是空樹，則搜索失敗，否則：

若x等於b的根節點的數據域之值，則查找成功；否則：

若x小於b的根節點的數據域之值，則搜索左子樹；否則：

查找右子樹。

圖2 ：從有序數組構造一個二叉查找樹

GIF/73K

GIF/338K

圖3 ：往 BST 中插入元素

向一個二叉搜索樹b中插入一個節點s的演算法，過程為：

若b是空樹，則將s所指結點作為根節點插入，否則：

若s->data等於b的根節點的數據域之值，則返回，否則：

若s->data小於b的根節點的數據域之值，則把s所指節點插入到左子樹中，否則：

把s所指節點插入到右子樹中。（新插入節點總是葉子節點）

GIF/118K

圖4 ：BST 轉成有序數組

GIF/493K

來源：伯樂在線 - 伯小樂

【寬客網路課堂】石破天驚之作：可量化的期貨基本面策略

本課程為台灣著名專家林洸興先生的傾力之作。與目前市場上大多數泛泛而論的期貨分析課程不同，「深刻」、「邏輯」兩個詞可以概括本課程的特點。結合量化的需求與特點，林先生特意在本系列課程中將可量化的基本面因素提煉出來講述。從這樣一個獨特的角度講解期貨策略，相信本課程是一個石破天驚的課程。

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！