Types
There are many types of binary search trees. AVL trees and red-black trees are both forms of self-balancing binary search trees. A splay tree is a binary search tree that automatically moves frequently accessed elements nearer to the root. In a treap (tree heap), each node also holds a (randomly chosen) priority and the parent node has higher priority than its children. Tango trees are trees optimized for fast searches.
Two other titles describing binary search trees are that of a complete and degenerate tree.
A complete tree is a tree with n levels, where for each level d <= n - 1, the number of existing nodes at level d is equal to 2d. This means all possible nodes exist at these levels. An additional requirement for a complete binary tree is that for the nth level, while every node does not have to exist, the nodes that do exist must fill from left to right.
A degenerate tree is a tree where for each parent node, there is only one associated child node. What this means is that in a performance measurement, the tree will essentially behave like a linked list data structure.
Read more about this topic: Binary Search Tree
Famous quotes containing the word types:
“The wider the range of possibilities we offer children, the more intense will be their motivations and the richer their experiences. We must widen the range of topics and goals, the types of situations we offer and their degree of structure, the kinds and combinations of resources and materials, and the possible interactions with things, peers, and adults.”
—Loris Malaguzzi (1920–1994)
“The bourgeoisie loves so-called “positive” types and novels with happy endings since they lull one into thinking that it is fine to simultaneously acquire capital and maintain one’s innocence, to be a beast and still be happy.”
—Anton Pavlovich Chekhov (1860–1904)
“He’s one of those know-it-all types that, if you flatter the wig off him, he chatter like a goony bird at mating time.”
—Michael Blankfort. Lewis Milestone. Johnson (Reginald Gardner)