Data Structures: Difference between revisions

(7 intermediate revisions by the same user not shown)

Line 1:

~~Data Structures from CMSC420 and more.~~

Common data structures you should know

==Lists==

Line 39:

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.

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

Red-black trees are used in in C++ (ordered_map, ordered_set) and Java (TreeMap, TreeSet).

====Complexity====

<math>2\log (n+1)</math> height.

<math>O(\log n)</math> insert, delete

<math>O(\log n)</math> search, insert, delete

===B-tree===

[[Wikipedia: B-tree]]

[[Wikipedia: B-tree]]

[https://www.cs.usfca.edu/~galles/visualization/BTree.html B-tree visualization]

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 2-3 tree of order 3

A B-tree of order 3

====~~Variants~~====

====B+ Tree====

* B+

====B* Tree====

* B*

===Treap===

A tree and a heap. O(logn) with high probability.

The main benefits are that it is very easy to implement.

====Insertion====

Insert using BST insert and then heapify using AVL rotations.

===Splay Tree===

===Segment Trees===

[[Wikipedia: Segment tree]]

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

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

@@ Line 1: / Line 1: @@
-Data Structures from CMSC420 and more.
+Common data structures you should know
 ==Lists==
@@ Line 39: / Line 39: @@
 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.<br>
+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> insert, delete
+<math>O(\log n)</math> search, insert, delete
 ===B-tree===
-[[Wikipedia: 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 2-3 tree of order 3
+A B-tree of order 3
-====Variants====
+====B+ Tree====
-* B+
+====B* Tree====
-* B*
 ===Treap===
 A tree and a heap. O(logn) with high probability.
+The main benefits are that it is very easy to implement.
 ====Insertion====
 Insert using BST insert and then heapify using AVL rotations.
 ===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==