二叉查找树
1. 概念
二叉查找树（BST）是数据结构的一类。在一般情况下，查询效率比链表结构要高。
2. 特征
- 左子树所有节点的值小于根节点的值
- 右子树所有节点的值大于根节点的值
- 左右子树也皆为二叉查找树
例图：
3. 优缺点
优点：
例：查找12
步骤：
-
由于 12<20，在左子树查找到子节点 15
-
由于 12<15， 在左子树查找到子节点 10
-
由于 12>10，在右子树查找，匹配完成
结论：二叉查找树的查找的最大次数等于树的高度
缺点：
由于二叉查找树的特性，致使在特定的情况下，它会出现子节点位于一边的情况，形成线性结构，看起来就不平衡了。
例图：
主角出场：红黑树