一种在每个节点有四个分支的树。四叉树用于构建一些多维数据库（例如，制图学、计算机图形学和图像处理）。对于一个
维树，对于
，已知成功和不成功搜索的所有整数对的预期比较次数的解析解，对于
，则已知数值解。
四叉树
使用 Wolfram|Alpha 探索
参考文献
de Berg, M.; van Kreveld, M.; Overmans, M.; 和 Schwarzkopf, O. "Quadtrees: Non-Uniform Mesh Generation." Ch. 14 in Computational Geometry: Algorithms and Applications, 2nd rev. ed. Berlin:Springer-Verlag, pp. 291-306, 2000.Finkel, R. A. 和 Bentley, J. L. "Quad Trees, a Data Structure for Retrieval on Composite Keys." Acta Informatica 4, 1-9, 1974.Flajolet, P.; Gonnet, G.; Puech, C.; 和 Robson, J. M. "Analytic Variations on Quadtrees." Algorithmica 10, 473-500, 1993.Flajolet, P.; Labelle, G.; Laforest, L.; 和 Salvy, B. "Hypergeometrics and the Cost Structure of Quadtrees." Random Structure Alg. 7, 117-144, 1995. http://algo.inria.fr/flajolet/Publications/publist.html.Gonnet, G. H. 和 Baeza-Yates, R. Ch. 3 in Handbook of Algorithms and Data Structures in Pascal and C. Reading, MA: Addison-Wesley, 1991.Lauwerier, H. Fractals: Endlessly Repeated Geometric Figures. Princeton, NJ: Princeton University Press, pp. 11-13, 1991.Samet, H. Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS. Reading, MA: Addison-Wesley, 1989.Samet, H. The Design and Analysis of Spatial Data Structures. Reading, MA: Addison-Wesley, 1990.在 Wolfram|Alpha 上被引用
四叉树请引用为
Weisstein, Eric W. "四叉树。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Quadtree.html