最近一段时间，一时兴起，重新刷了leetcode，顺便重新温习二叉搜索树相关的知识，对它的理解更上一层楼。二叉搜索树是非常优雅的数据结构，有非常出色的时间复杂度，而且应用也非常广泛！
每种数据结构都有它独特的特性。跟数组和链表相比， 二叉搜索树的优势在哪里？ 那么二叉搜索树的用途是什么？ 最后一个比较深刻的问题： 二叉搜索树的本质是什么？
要回答这个问题， 我们先看看数组、链表、二叉搜索树有哪些特性，以及它们的比较。
下面， 考虑一个场景：
一组已顺序排序的整数序列， 分别用 数组， 链表， 二叉搜索树 存储， get, insert, delete 操作的时间复杂度分别是多少。
现在定义如下函数：
get（int value);
insert(int value);// 插入一个值，整数序列仍然是顺序排序
delete(int value);// 删除一个值，整数序列仍然是顺序排序
不同的存储结构，时间复杂度分别如下：
数组：时间复杂度O(log2n), insert时间复杂度O(n),delete时间复杂度O(n)
链表：get时间复杂度O(n), insert时间复杂度O(n),delete时间复杂度O(n)
二叉搜索树：get时间复杂度O(log2n), insert时间复杂度O(log2n),delete时间复杂度O(log2n)（这里有一个前提：该二叉搜索树是平衡的）
对于顺序序列的数据操作， 二叉搜索树简直吊打数组和链表。
但是仔细分析，其实二叉搜索树是数组和链表的集大成者， 吸收其精华！
数组最大的特性是连续存储， 基于这个特性， 可以利用二分查找， 使get复杂度为O(log2n)。 而二叉搜索树的get操作从本质上来说也是二分查找， 从这一点来说和数组的二分查找有异曲同工之妙！
而二叉搜索树利用了链表的特性（已知一个节点，insert和delete的时间复杂度为O(1)）， 使得insert和delete时间复杂度都为O(log2n)。
所以， 二叉搜索树的本质是： 集成了数组和链表的优势， 是一种艺术的平衡！
正是因为二叉搜索树有太优秀的时间复杂度， 具有广泛的应用。 如：基于二叉树的红黑树和AVL树，在操作系统， 数据库等领域有广泛的应用。
如有错误，烦请批评指正，不胜感激！转载请明确标注转载并附上文章具体网址，谢谢！
