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

2019-09-04 14:27:36

(點選上方公眾號,可快速關注)

來源:伯樂線上 - 伯小樂 

連結:http://blog.jobbole.com/101366/


二叉查詢樹(Binary Search Tree),也稱二叉搜尋樹,是指一棵空樹或者具有下列性質的二叉樹:


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

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

  • 任意節點的左、右子樹也分別為二叉查詢樹;

  • 沒有鍵值相等的節點。

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


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


圖1:查詢 BST 中的某個元素


在二叉搜尋樹b中查詢x的過程為:


  1. 若b是空樹,則搜尋失敗,否則:

  2. 若x等於b的根節點的資料域之值,則查詢成功;否則:

  3. 若x小於b的根節點的資料域之值,則搜尋左子樹;否則:

  4. 查詢右子樹。


圖2 ↓ :從有序陣列構造一個二叉查詢樹



圖3 ↓:往 BST 中插入元素


向一個二叉搜尋樹b中插入一個節點s的演算法,過程為:


  1. 若b是空樹,則將s所指結點作為根節點插入,否則:

  2. 若s->data等於b的根節點的資料域之值,則返回,否則:

  3. 若s->data小於b的根節點的資料域之值,則把s所指節點插入到左子樹中,否則:

  4. 把s所指節點插入到右子樹中。(新插入節點總是葉子節點)


圖4 ↓:BST 轉成有序陣列


已同步到看一看



熱點新聞