Difference between revisions of "data structures"

From Noah.org
Jump to navigationJump to search
m (Created page with 'Category: Engineering Lowest Common Ancestor = Data Structures = ;Linked List: ;Stack: ;Queue: ;Heap: ;Priority Queue: ;Union Find: ;Hash Table: ;Tree Map: ;Suffix Array: …')
 
m (e)
Line 12: Line 12:
 
;Union Find:
 
;Union Find:
 
;Hash Table:
 
;Hash Table:
;Tree Map:
+
;Associative array (dictionary, map, symbol table): A collection that associates a unique Key with a Value.
 
;Suffix Array:
 
;Suffix Array:
 
;Dynamic Suffix Array:
 
;Dynamic Suffix Array:
Line 19: Line 19:
 
;Suffix Automaton:
 
;Suffix Automaton:
 
;Heavy-Light Decomposition:
 
;Heavy-Light Decomposition:
;Aho-Corasick: string searching algorithm:
+
;Aho-Corasick: string searching algorithm
 
;Rope: data structure that uses a tree to store a string in order to make subsequent manipulation of the string more efficient. This data structure is frequently found in text editors and makes it possible to efficiently delete and insert blocks of text.
 
;Rope: data structure that uses a tree to store a string in order to make subsequent manipulation of the string more efficient. This data structure is frequently found in text editors and makes it possible to efficiently delete and insert blocks of text.
 
;Dancing Links: Used to solve '''exact cover''' problems.
 
;Dancing Links: Used to solve '''exact cover''' problems.
Line 25: Line 25:
 
== Trees ==
 
== Trees ==
  
;Binary Search Tree
+
;Binary Search Tree:
;Huffman Tree
+
;Huffman Tree:
;Segment Tree
+
;Segment Tree:
;Binary Indexed Tree
+
;Binary Indexed Tree:
;Range Tree
+
;Range Tree:
;Trie (prefix tree)
+
;Trie (prefix tree):
;Radix Tree
+
;Radix Tree:
;K-d tree
+
;K-d Tree:
;Link-Cut Tree
+
;Link-Cut Tree:
;Splay Tree
+
;Splay Tree:
 
;Palindromic Tree
 
;Palindromic Tree
;Treap: randomized binary tree (heap + tree + heap)
+
;Treap (tree + heap): randomized binary tree:
 +
;Tree Map (Tree Dict):

Revision as of 11:33, 29 July 2015


Lowest Common Ancestor

Data Structures

Linked List
Stack
Queue
Heap
Priority Queue
Union Find
Hash Table
Associative array (dictionary, map, symbol table)
A collection that associates a unique Key with a Value.
Suffix Array
Dynamic Suffix Array
Sparse Table
Lowest Common Ancestor
Suffix Automaton
Heavy-Light Decomposition
Aho-Corasick
string searching algorithm
Rope
data structure that uses a tree to store a string in order to make subsequent manipulation of the string more efficient. This data structure is frequently found in text editors and makes it possible to efficiently delete and insert blocks of text.
Dancing Links
Used to solve exact cover problems.

Trees

Binary Search Tree
Huffman Tree
Segment Tree
Binary Indexed Tree
Range Tree
Trie (prefix tree)
Radix Tree
K-d Tree
Link-Cut Tree
Splay Tree
Palindromic Tree
Treap (tree + heap)
randomized binary tree:
Tree Map (Tree Dict)