数据结构之二叉搜索树(Binary Search Tree)

数据结构可视化演示链接，也就是图片演示的网址

---

系列文章目录

数据结构之AVL Tree
数据结构之B树和B+树
数据结构之Radix和Trie

---

---

示例图

二叉

线形(顺序插入就变成了线性树，例如插入顺序为：1，2，3，4，5，6)

---

定义

二叉搜索树也是一种树，适用与一般二叉树的全部操作，但二叉搜索树能够实现数据的快速查找。

二叉搜索树满足的条件

1. 非空左子树的所有键值小于其根节点的键值
2. 非空右子树的所有键值大于其根节点的键值
3. 左右子树都是二叉搜索树

应用场景

如果是没有退化称为链表的二叉树，查找效率就是lgn，效率不错，但是一旦退换为链表，要么使用平衡二叉树，或者之后的RB树(红黑树)，因为链表就是线性的查找效率。