資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學資料結構中的範圍樹
範圍樹被定義為一種有序的樹形資料結構，用於儲存一系列點。它允許高效地檢索給定範圍內的所有點，通常在二維或更高維度中實現。它與kd樹類似，但查詢時間更快，為O(logd n + k)，但儲存空間更差，為O(n logd-1 n)，其中d表示空間維度，n表示樹中的點數，k表示給定查詢檢索到的點數。範圍樹可以與區間樹區分開來：區間樹不是儲存點並允許高效檢索給定範圍內的點，而是儲存區間並允許高效檢索包含給定點的區間。
資料結構
一維範圍樹示例。除葉子節點外，每個節點都儲存其左子樹中的最大值。
一組一維點上的範圍樹被視為這些點上的平衡二叉搜尋樹。儲存在樹中的點儲存在樹的葉節點中；每個內部節點儲存其左子樹中包含的最大值。一組d維點上的範圍樹是一個遞迴定義的多層二叉搜尋樹。資料結構的每一層都被視為d維中一個維度的二叉搜尋樹。第一層是d個座標中第一個座標的二叉搜尋樹。這棵樹的每個頂點v都包含一個關聯結構，該結構是v的子樹中儲存的點的最後(d−1)個座標的(d−1)維範圍樹。
操作
構建
一組n個點的一維範圍樹是一個二叉搜尋樹，可以在O(n log n)時間內構建。更高維度的範圍樹是透過遞迴地構建點第一個座標的平衡二叉搜尋樹來構建的，之後，對於這棵樹中的每個頂點v，在v的子樹中包含的點上構建一個(d−1)維範圍樹。這樣構建範圍樹需要O(n logdn)時間。
更新於：2020年1月8日
3K+ 次瀏覽
廣告