# Difference between revisions of "data structures"

From Noah.org

m (e) |
m (→Data Structures) |
||

(One intermediate revision by the same user not shown) | |||

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 == | ||

Line 38: | Line 40: | ||

;Treap (tree + heap): randomized binary tree: | ;Treap (tree + heap): randomized binary tree: | ||

;Tree Map (Tree Dict): | ;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. |

## 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.