(data structure)
Definition: (1) A BB(α) tree where the weights are the number of searches down that path. (2) A height-balanced binary tree that divides regions along their boundaries to serve as a spatial access method.
Generalization (I am a kind of ...)
(1) BB(α) tree (2) binary tree, spatial access method, height-balanced tree.
Note: (1) Short for "dynamic tree".
Author: PEB
(1) Kurt Mehlhorn, Dynamic Binary Search, SIAM Journal on Computing, 8(2):175-198, May 1979. Abstract, article, and references.
(2) Jianliang Xu, Baibua Zheng, Wang-Chien Lee, and Dik Lun Lee, The D-tree: An Index Structure for Planar Point Queries in Location-Based Wireless Services, IEEE Transactions on Knowledge and Data Engineering, 16(12):1526- 1542, December 2004.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 8 June 2006.
HTML page formatted Mon Sep 11 09:46:02 2006.
Cite this as:
Paul E. Black, "D-tree", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 8 June 2006. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/DTree.html
