依題意來說, 一個點之編號為 t 他的意思應該是該點在整個 tree 中的編號為 t, 而不是指它是在該 level 中的第 t 個點
以下的 log 皆以 d 為底 假設編號為 t 的點在 level h, 因為 t <= (d^h-1)/(d-1), 整理一下可得 h = ceiling(log(t(d-1)+1))
因為在 level h 中編號小於 t 的點總共有 t-1-(d^(h-1)-1)/(d-1) 個點, 因為每個點都有 d 個 child, 所以編號 t 的點的第 i 個child是在level h+1裡的第 d*(t-1-(d^(h-1)-1)/(d-1)) + i 個點, 其編號為 (d^h-1)/(d-1) + d*(t-1-(d^(h-1)-1)/(d-1)) + i, for i=1,2,...,d
都只會解二元樹的題目，遇到這提就不會了，想了很久還是想不出來
求t點之子點範圍
回覆刪除t點的最後一個子點為t*d
t點的前面一個interal node為t-1
其子點為(t-1)*d
所以t點之子點範圍為(t-1)*d+1 ~ t*d
作者已經移除這則留言。
回覆刪除依題意來說, 一個點之編號為 t
回覆刪除他的意思應該是該點在整個 tree 中的編號為 t,
而不是指它是在該 level 中的第 t 個點
以下的 log 皆以 d 為底
假設編號為 t 的點在 level h,
因為 t <= (d^h-1)/(d-1),
整理一下可得 h = ceiling(log(t(d-1)+1))
因為在 level h 中編號小於 t 的點總共有
t-1-(d^(h-1)-1)/(d-1)
個點, 因為每個點都有 d 個 child,
所以編號 t 的點的第 i 個child是在level h+1裡的第
d*(t-1-(d^(h-1)-1)/(d-1)) + i
個點, 其編號為
(d^h-1)/(d-1) + d*(t-1-(d^(h-1)-1)/(d-1)) + i,
for i=1,2,...,d
抱歉 助教 我寄信給你 你沒有幫我加入 Blog 不得已留在這裡 讓你看到 需要我寄學生證號碼 請在此留言 現在蠻緊急的 可以的話 請盡快處理
回覆刪除同學您好, 因為那個email不是我在收, 所以不好意思我沒有辦法馬上幫你處理, 請您在稍候一下, 如果您確定您有將姓名與學號寄過去了, 那應該不久之後就會收到信, 如果是已經等了好幾天還是沒有通過認證, 再請你留個言給我, 我再幫您詢問一下狀況
回覆刪除