Data Structures: Difference between revisions
| (One intermediate revision by the same user not shown) | |||
| Line 47: | Line 47: | ||
===B-tree=== | ===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. | 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. | ||
| Line 53: | Line 54: | ||
A B-tree of order 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=== | ||