線段樹 (儲存區間)

维基百科,自由的百科全书
(重定向自线段树
跳转至: 导航搜索

線段樹英语:Segment tree)是一種二元樹形資料結構,1977年由Jon Louis Bentley發明[1],用以儲存區間線段,並且允許快速查詢結構內包含某一點的所有區間。

一個包含個區間的線段樹,空間複雜度為,查詢的時間複雜度則為,其中是符合條件的區間數量。

此資料結構亦可推廣到高維度。

結構[编辑]

本處以一維的線段樹為例。

線段樹結構示意,其儲存的線段顯示在圖片的下方。

令S是一維線段的集合。將這些線段的端點坐標由小到大排序,令其為。我們將被這些端點切分的每一個區間稱為「單位區間」(每個端點所在的位置會單獨成為一個單位區間),從左到右包含:

線段樹的結構為一個二元樹,每個節點都代表一個坐標區間,節點N所代表的區間記為Int(N),則其需符合以下條件:

  • 其每一個葉節點,從左到右代表每個單位區間。
  • 其內部節點代表的區間是其兩個兒子代表的區間之聯集。
  • 每個節點(包含葉子)中有一個儲存線段的資料結構。若一個線段S的坐標區間包含Int(N)但不包含Int(parent(N)),則節點N中會儲存線段S。

參考資料[编辑]

  1. ^ de Berg 等人 2000,p.229)