先看一个需求
给你一个数列{7, 3, 10, 12, 5, 1, 9},要求能够高效的完成对数据的查询和添加
解决方案
使用数组
- 数组未排序
- 优点:直接在数组尾添加,速度快.
- 缺点:查找速度慢
- 数组排序
- 优点:可以使用二分查找,查找速度块
- 缺点:为了保证数组有序,在添加新数据时,找到插入位置后,后面的数据需要整体移动,速度慢.
使用链式存储
- 不管链表是否有序,查找速度都慢,添加速度比数组快,不需要数据整体移动.
使用二叉排序树 - 能提高数据存储,读取的效率,比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
二叉排序树介绍
二叉排序树:对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大
特别说明如果有相同的值,可以将该节点放在左子节点或右子节点
比如针对前面的数据{7,3,10,12,5,1,9},对应的二叉排序树为:
