Data Structures: Difference between revisions
| (10 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Common data structures you should know | |||
==Lists== | ==Lists== | ||
| Line 20: | Line 20: | ||
===AVL=== | ===AVL=== | ||
===Red-Black=== | ===Red-Black=== | ||
===2-3=== | [[Wikipedia: Red–black tree]]<br> | ||
[https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/ Geeks for geeks introduction]<br> | |||
[https://www.geeksforgeeks.org/red-black-tree-set-2-insert/ Geeks for geeks insertion]<br> | |||
[https://www.geeksforgeeks.org/red-black-tree-set-3-delete-2/ Geeks for geeks deletion]<br> | |||
A red-black tree follows the following rules | |||
# Each node is either red or black. | |||
# The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis. | |||
# All leaves (NIL) are black. | |||
# If a node is red, then both its children are black. | |||
# Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. | |||
====Intuition==== | |||
Consider any tree with a left and right child. | |||
From rule 4, we see that at most n/2 nodes are red. At least half will be black. | |||
Red nodes or levels are those interspersed between black levels. | |||
If the left child has <math>m</math> levels then at most the right child can have <math>2m</math> levels. | |||
Intuitively, this is more relaxed than AVL trees so they will have fewer operations for insert/delete but will be less balanced (i.e. longer search).<br> | |||
Red-black trees are used in in C++ (ordered_map, ordered_set) and Java (TreeMap, TreeSet). | |||
====Complexity==== | |||
<math>2\log (n+1)</math> height.<br> | |||
<math>O(\log n)</math> search, insert, delete | |||
===B-tree=== | |||
[[Wikipedia: B-tree]]<br> | |||
[https://www.cs.usfca.edu/~galles/visualization/BTree.html B-tree visualization]<br> | |||
A very popular data structure for filesystems and memory indexes since the maximum size of a node in the B-tree can be configured to the size of a page of memory. | |||
====2-3==== | |||
A B-tree of order 3 | |||
====B+ Tree==== | |||
====B* Tree==== | |||
===Treap=== | ===Treap=== | ||
A tree and a heap. O(logn) with high probability. | A tree and a heap. O(logn) with high probability. | ||
The main benefits are that it is very easy to implement. | |||
====Insertion==== | ====Insertion==== | ||
Insert using BST insert and then heapify using AVL rotations. | Insert using BST insert and then heapify using AVL rotations. | ||
===Splay Tree=== | ===Splay Tree=== | ||
===Segment Trees=== | |||
[[Wikipedia: Segment tree]]<br> | |||
[https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/ Geeksforgeeks 1 sum of range] | |||
* This is a binary tree for holding segments.<br> | |||
* Leaves hold something called "elementary intervals" and internal nodes hold the union of elementary intervals of its children. | |||
* In addition, each leaf or node v also holds intervals which span their segment, i.e. <math>\{X \mid Int(v) \in X\}</math> | |||
==Spatial Data Structures== | ==Spatial Data Structures== | ||