Tree

tags: Algorithm,Tree,Graph source: https://en.wikipedia.org/wiki/Minimum%5Fspanning%5Ftree

tags: Tree

tags: Binary Tree,Tree A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

tags: Heap (data structure),Data Structures,Complete Binary Tree,Tree source: https://en.wikipedia.org/wiki/Binary%5Fheap Binary tree with two additional constraints: Shape property: complete binary tree. Heap property: the key stored in each node is greater or equal(max-heaps) to or less than or equal to(min-heaps) the keys in the node’s children, according to some total order. Heap operations Insert Steps to add an element to a heap: Add element to the bottom level of the heap at the leftmost open space. Compare to its parent, if they are in the correct the order, stop. If not, swap element with its parent and return to the previous step. Extract: Delete the root from heap Replace the root of heap with the last element on the bottom level. Compare the new root with its children; if they are in the correct order, stop. If not, swap the element with one of its children and return to the previous step. Search Delete Decrease or increase key Heap implementation with array each element a at index i has ...

tags: Data Structures,Tree WHAT is a heap? Tree-based data structure which is essentially an almost complete tree that statifies the heap property. Max heap For any given node C, if P is a parent node of C, then the key(the value) of P is greater than or equal to the key of C. Min heap The P is less than or equal to the key C. When to use a heap? Priority queue. Heapsort.

tags: Binary Search Tree,Binary Tree,Tree

tags: Data Structures,Binary Tree,Tree

tags: Binary Search Tree, AVL Tree,Tree

tags: Tree 日志结构合并树（Log-Structured Merge-Tree）：基于合并和压缩排序文件原理的存储引擎通常都被称为 LSM 存储引擎。 压缩排序文件基于排序字符串表：SSTables。 LSM-Tree 基本思想：保存在后台并合并的排序字符串表：SSTables。即使数据集远远大于可用内存，仍然能够正常工作。 基于有序的特性，可以有效的执行区间查询，并且由于磁盘是顺序写入，所以 LSM-Tree 可以支持非常高的写入吞吐量。 性能优化 通过布隆过滤器优化 LSM-Tree 查找不存在的键性能低下的问题。 通过大小分级和分层压缩优化 SSTables 压缩和合并时的具体顺序和时机。 大小分级：较新和较小的 SSTables 被连续合并到较旧和较大的 SSTables。 分层压缩：键的范围分裂成多个更小的 SSTables，就数据被移动到单独的“层级”，这样压缩可以逐步进行并节省磁盘空间。