Tree Notes - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

Trees are a good way to store, summarize, and search dynamic data.

B-trees are at the heart of every database!

Many problems require storing additional data in a standard data structure.

Useful for summarizing and processing data

Basic methodology:

1. Choose underlying data structure (tree, hash table, linked list, stack, etc.)
2. Determine additional info needed.
3. Modify data structure to maintain additional info when the structure changes. (subject to insert/delete/etc.)
4. Develop new operations.

Basic methodology:

1. Choose underlying data structure: AVL tree
2. Determine additional info needed: Weight of each node
3. Maintained info as data structure is modified. Update weights as needed
4. Develop new operations using the new info. Select and Rank

https://www.zhihu.com/question/294774611

创建二叉树 avl的时间复杂度?是O(n)，最坏达到O(n^2)