iT邦幫忙

1

【小馬的資結演算法秘笈】(14) AVL tree簡介,會自動平衡的BST

哈囉~ 大家好,
上回【小馬的資結演算法秘笈】(13) Binary Search Tree,方便二分查找的樹中,
跟大家介紹一種很有用的資料結構- Binary Search Tree(簡稱BST),
可以達到方便二分查找的的效果

但是普通的BST有其缺點,
就是當插入元素的順序不好的時候,
BST有可能會非常的「傾斜」,
就是樹的高度可能很接近節點數量,如圖:
https://ithelp.ithome.com.tw/upload/images/20200601/20117114MoQh13IaI3.png

為了克服這個問題,
可以使用一種特別的資料結構叫作 AVL tree,
AVL tree其實就是一種BST,
只不過每次在插入新的節點時,
該樹會自動偵測是否出現很不平衡的情形

如果出現不平衡的情形,樹便會做一些調整,
使得樹的每個節點的左、右子樹高度最多差1

本文只是做一個簡介、概略性的介紹,
這邊附上參考資料供大家學習細節

參考資料

  1. geeksforgeeks- AVL Tree | Set 1 (Insertion)

尚未有邦友留言

立即登入留言