[Data Structure][Tree] - Balanced Search Tree - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

2019 iT 邦幫忙鐵人賽

DAY 22

0

自我挑戰組

學習資料結構30天系列第 22 篇

[Data Structure][Tree] - Balanced Search Tree

2019鐵人賽 balanced search tree

2018-11-05 22:58:08

2936 瀏覽

分享至

前言

對一般的Binary Search Tree進行查詢、新增、刪除節點，所花費的時間會和Tree的height成正比，卻不會與Tree有幾個節點數量成正比。
在不平衡的樹中(ex:偏移樹)，要尋找目標節點，需要花費很長的時間。

所以，今天要講進化過的Binary Search Tree -> Balanced Search Tree。

平衡樹 Balanced Search Tree

主要目標 : 讓所有節點的高度都是O(log n)

|左子樹和右子樹的高度相減| <= 1
左子樹和右子樹必須是平衡樹

不平衡的Tree
平衡的Tree

旋轉 Rotate

不破壞Search Tree的左小右大特性，透過將Tree旋轉，讓其能趨近平衡。

Rotate 又分為 Right rotation和Left rotation。

<=>

[Data Structure][Tree] - Binary Search Tree &Heap

[Data Structure] - Hash Table

系列文

學習資料結構30天共 30 篇

目錄

RSS系列文訂閱系列文

28 人訂閱

完整目錄

直播研討會

{{ item.subject }}

{{ item.channelVendor }} {{ item.webinarstarted }} |

{{ formatDate(item.duration) }}

直播中

尚未有邦友留言

立即登入留言

參賽組數

1064 組

團體組數

40 組

累計文章數

22195 篇

完賽人數

600 人

15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js

IT邦幫忙