display | more...

Definition: A binary search tree(BST) with the property of being a linked list with extra overhead.

Searching in a tree with BST disease takes O(n) time in the worst case (see: Big-oh Notation) as compared to O(log n) for a well balanced tree. To easily create a binary search tree with this disease, sort your data by keyvalue before inserting.

Data structures such as the AVL Tree, which is locally balanced, and the splay tree, which moves recently accessed nodes to the top, or root of the tree, were created to combat unbalanced trees -- BST disease is the extreme condition of unbalance.

The quad-tree analogue of the BST is the point quadtree. It too is affected by BST disease. Other trees (and tries) can be affected to a lesser degree -- inserting data into a point-region quadtree when the data is very clustered can create a tree of unpredictable but finite depth.

Log in or register to write something here or to contact authors.