Difference between revisions of "data structures"

From Noah.org
Jump to: navigation, search
m (Trees)
m (Data Structures)
 
Line 22: Line 22:
 
;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.
 +
;Bloom filter: Used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not.
 +
;Locality-sensitive hashing: Hashing method that attempts to give similar data similar hash values. This property is almost exactly the opposite of a cryptographic hash algorithm.
  
 
== Trees ==
 
== Trees ==

Latest revision as of 13:29, 10 August 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.
Bloom filter
Used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not.
Locality-sensitive hashing
Hashing method that attempts to give similar data similar hash values. This property is almost exactly the opposite of a cryptographic hash algorithm.

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)
Skip List
allows fast probabilistic searching through an ordered sequence.
Skip Graph
based on Skip Lists, provides all features of a balanced tree with the ability to tolerate loss of nodes.