Heap, Tree, Treap
Self Balanced Binary Search Tree:
Automatically balances height in case of arbitrary insertion or deletion.
Red-Black Tree:
By rearranging and repainting each node either red or black the balance is preserved.
AA Tree:
The red nodes can be added only as a right sub-child. Thus, every left child level is one less than parent, and that for right child is equal or one less. Every node of level more than one has 2 children.
Red-black tree is more consistent, but AA tree provide better search time.
2-3.
Special AA tree.
Internal Nodes : Data 1 && Children 2 || Data 2 && Children 3
Leaf: Data 1 || Data 2
B-Tree:
Internal node have more than 2 child and contain number of keys. For example, a three child node will have 2 keys, all values in left most sub-trees will be less than one key, same for the right most sub-tree for the other key. Middle sub-tree values range between the keys. If the branching factor of a node is d then the maximum keys node can hold is 2(d-1).
B+ Tree:
Internal nodes only have copies of the keys, keys and records are stored in leaves. For moving objects, an efficient query and update enabled version is used called Bx tree. Self Tuning Bx-Tree can self tune all the way for skewing and rotations with efficient tuning algorithms. UB-Tree is another B+ tree good for multidimensional data. It calculates a bitwise interlacing of keys to order data which is termed as Z-order.
B* Tree:
Instead of splitting maintains densely packed internal neighbors by sharing keys when a new nodes are required, making a 2/3rd full rather 1/2 as in B-Tree.
Order Statistic Tree:
Variant of B-Tree that supports operations, 1. find the smallest element at certain level, 2. find the index of an element if transferred to a sorted array. besides the typical 3, insertion, look-up and deletion. The Python package blist uses order statistic B-trees to implement lists with fast insertion at arbitrary positions.
2-4 tree (B-trees of order 4):
1 data && (Internal?2 child:Leaf)||
Good for Dictionaries, hashing.
(a,b) tree:
IF a and b are integers && 2 le a le (b+1)/2 THEN
AVL tree:
A self-balancing binary search tree where the heights of the 2 child sub-trees of any node can differ at most by 1. Whenever it changes to >1 a re-balancing and rotating happens.
Dancing Tree:
B+ tree where balancing happens after only a certain event, more precisely whenever a WRITE operation takes place on the disk.
H-Tree:
Specialized B-Tree with higher fanout factor and better handling of hash collision. Linux ext2 and ext3 file systems use H-Tree.
Interval Tree:
Efficiently find all intervals which overlap with any given interval. Geospatial solutions such as in a GPS or higher dimensional operations like virtual reality can be based on such tree algorithms.
Scapegoat Tree:
Always height-balanced, unlike both height and weight balance BST. No color information like red-black tree or balance values as saved in AVL nodes. Acts somewhat lazily per-need basis calculation.
Splay Tree (Tarjan):
Searched element is brought up to the root by rotating. This process of tree search and rotating to get that as root together is called splaying.
Supports, sequential access property, dynamic fingering property, work-set property and unified property. Dynamic optimality can be proven on spay trees, but the problem is termed NP-hard.
T-Tree:
Optimized DS with many commercial use, most popular MySQL. T-trees contain pointers to the actual data fields kept in main memory, saving space. A T-tree node contains, pointer to the parent, pointers to left and right child and an ordered array of pointers to data with additional pointers for control data. Internal nodes have 2 sub-trees. Half-leaf nodes have 1 sub-tree. Leaf node has none.
Treap:
Rearrangement of a Self Balanced BST must always be heap-ordered so priority lowers as depth increases.
Binary Heap:
Balanced BST where each internal node is filled with 2 children and Leaf must fill in as left-child first. Max-heap, values lower with depth. Min-heap, opposite also known as Priority Queue.
Leftist Heap:
A priority queue where right descendant always has lower s-value. (Highly unbalanced)
Skew Heap:
Special case of L-Heap with better merging algorithm.
vEB tree:
Basically implements an array with m-bit integer keys. (??)
Suffix (Position) Tree:
Contains all the suffixes of a given text as keys and the position in the text as their values - hence very efficient for many string operations.
Radix Tree:
Each node with only one child can become a sub-tree of an internal node, creating a smaller sub-set for better string queries with degree of radix r.
Hash Tree:
A persistent DS stores hashes with actual keys and values in the final node. (Definition somewhat indicates a version of B+Tree).
Ternary Search Tree:
Common use spell-checking and auto-completion. Faster than hash table.
Cartesian Tree:
A heap-ordered BST where in-order walk always returns the original sequence.
R-tree:
R stands for Rectangle - useful for maps and location search. Find a nearby gas station - creates a defined rectangle based on the actual query location and then goes by points to determine the existence of the query.
Automatically balances height in case of arbitrary insertion or deletion.
Red-Black Tree:
By rearranging and repainting each node either red or black the balance is preserved.
AA Tree:
The red nodes can be added only as a right sub-child. Thus, every left child level is one less than parent, and that for right child is equal or one less. Every node of level more than one has 2 children.
Red-black tree is more consistent, but AA tree provide better search time.
2-3.
Special AA tree.
Internal Nodes : Data 1 && Children 2 || Data 2 && Children 3
Leaf: Data 1 || Data 2
B-Tree:
Internal node have more than 2 child and contain number of keys. For example, a three child node will have 2 keys, all values in left most sub-trees will be less than one key, same for the right most sub-tree for the other key. Middle sub-tree values range between the keys. If the branching factor of a node is d then the maximum keys node can hold is 2(d-1).
B+ Tree:
Internal nodes only have copies of the keys, keys and records are stored in leaves. For moving objects, an efficient query and update enabled version is used called Bx tree. Self Tuning Bx-Tree can self tune all the way for skewing and rotations with efficient tuning algorithms. UB-Tree is another B+ tree good for multidimensional data. It calculates a bitwise interlacing of keys to order data which is termed as Z-order.
B* Tree:
Instead of splitting maintains densely packed internal neighbors by sharing keys when a new nodes are required, making a 2/3rd full rather 1/2 as in B-Tree.
Order Statistic Tree:
Variant of B-Tree that supports operations, 1. find the smallest element at certain level, 2. find the index of an element if transferred to a sorted array. besides the typical 3, insertion, look-up and deletion. The Python package blist uses order statistic B-trees to implement lists with fast insertion at arbitrary positions.
2-4 tree (B-trees of order 4):
1 data && (Internal?2 child:Leaf)||
2 data && (Internal?3 child:Leaf)||
3 data && (Internal?4 child:Leaf)
Good for Dictionaries, hashing.
(a,b) tree:
IF a and b are integers && 2 le a le (b+1)/2 THEN
if node = root && !leaf has children ge 2 &&
le b
if node = internal has children ge a && le b
if node = leaf then path from root is a constant
AVL tree:
A self-balancing binary search tree where the heights of the 2 child sub-trees of any node can differ at most by 1. Whenever it changes to >1 a re-balancing and rotating happens.
Dancing Tree:
B+ tree where balancing happens after only a certain event, more precisely whenever a WRITE operation takes place on the disk.
H-Tree:
Specialized B-Tree with higher fanout factor and better handling of hash collision. Linux ext2 and ext3 file systems use H-Tree.
Interval Tree:
Efficiently find all intervals which overlap with any given interval. Geospatial solutions such as in a GPS or higher dimensional operations like virtual reality can be based on such tree algorithms.
Scapegoat Tree:
Always height-balanced, unlike both height and weight balance BST. No color information like red-black tree or balance values as saved in AVL nodes. Acts somewhat lazily per-need basis calculation.
Splay Tree (Tarjan):
Searched element is brought up to the root by rotating. This process of tree search and rotating to get that as root together is called splaying.
Supports, sequential access property, dynamic fingering property, work-set property and unified property. Dynamic optimality can be proven on spay trees, but the problem is termed NP-hard.
T-Tree:
Optimized DS with many commercial use, most popular MySQL. T-trees contain pointers to the actual data fields kept in main memory, saving space. A T-tree node contains, pointer to the parent, pointers to left and right child and an ordered array of pointers to data with additional pointers for control data. Internal nodes have 2 sub-trees. Half-leaf nodes have 1 sub-tree. Leaf node has none.
Treap:
Rearrangement of a Self Balanced BST must always be heap-ordered so priority lowers as depth increases.
Binary Heap:
Balanced BST where each internal node is filled with 2 children and Leaf must fill in as left-child first. Max-heap, values lower with depth. Min-heap, opposite also known as Priority Queue.
Leftist Heap:
A priority queue where right descendant always has lower s-value. (Highly unbalanced)
Skew Heap:
Special case of L-Heap with better merging algorithm.
vEB tree:
Basically implements an array with m-bit integer keys. (??)
Suffix (Position) Tree:
Contains all the suffixes of a given text as keys and the position in the text as their values - hence very efficient for many string operations.
Radix Tree:
Each node with only one child can become a sub-tree of an internal node, creating a smaller sub-set for better string queries with degree of radix r.
Hash Tree:
A persistent DS stores hashes with actual keys and values in the final node. (Definition somewhat indicates a version of B+Tree).
Ternary Search Tree:
Common use spell-checking and auto-completion. Faster than hash table.
Cartesian Tree:
A heap-ordered BST where in-order walk always returns the original sequence.
R-tree:
R stands for Rectangle - useful for maps and location search. Find a nearby gas station - creates a defined rectangle based on the actual query location and then goes by points to determine the existence of the query.
Comments
Post a Comment