5,337
edits
Data Structures: Difference between revisions
→Splay Tree
(→2-3) |
|||
| Line 62: | Line 62: | ||
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 \st Int(v) \in X\}</math> | |||
==Spatial Data Structures== | ==Spatial Data Structures== | ||