[問題] AVL Tree: 如何偵測是否作了balance之動作
大家好, 在AVL tree裡面, 假設現在正在插入一個新的node, 使用的是recurrsive的方式,
那在critical node (balance factor <= -2 or >= 2)做完平衡之後, 從此critical node
以上的路徑上的node就都不用再作任何動作了(連深度都不用加減了), 不過問題來了, 要
怎麼偵測一個平衡樹的動作已經真實的發生過了呢???
看過幾種實作大概分成:
1. 額外的boolean parameter來檢查是否發生
2. 更新樹/子樹的高度, on the fly. 一個node需要一個額外的欄位
3. iterate, 用幾個額外的變數記下所須知訊息
那我想請問的是, 有沒有辦法在使用recurrsive的方式下, 不使用額外的變數, 純粹
使用現在這個node所擁有的訊息(bf, leftchild, rightchild)就能偵測出平衡樹的動作
已經發生了???
感謝各位的幫忙~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.202.36
※ 編輯: rifiz 來自: 114.43.185.171 (07/25 07:51)
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
