什么是BST二叉查找树，以及查找流程详解

什么是二叉查找树呢？

二叉查找树（BST）具备以下特性：

1. 左子树上所有结点的值均小于或等于它的根结点的值。
2. 右子树上所有结点的值均大于或等于它的根结点的值。
3. 左、右子树也分别为二叉排序树。

二叉搜索树 BST的完美情况

一般人们理解的二叉树（又叫二叉搜索树 BST）会出现一个问题，完美的情况下，它是这样的：

二叉搜索树的查找流程

如何查找值为7的节点？
1.查看根节点8，因为7<8，所以再查看它的左子节点6
2.查看左子节点6，因为7>6，所以再查看它的右子节点7
3.查看右子节点7，因为7=7，所以就找到啦，

二叉搜索树的极端情况

二叉查找树是有缺点的，在不断插入的时候，有可能出现这样一种情况：很容易“退化”成链表，

如果bst 树的节点正好从大到小的插入，此时树的结构也类似于链表结构，这时候的查询或写入耗时与链表相同。

退化成为了 链表的特殊BST

一颗特殊BST，退化成为了 链表，如下图：

它和链表一样，搜索的时候，最坏情况的时间复杂度O(n) 。

那么我们怎么避免这种情况呢？

为了避免这种特殊的情况发生，引入了平衡二叉树（AVL）和红黑树（red-black tree）。

AVL 、rbt 都是通过本身的建树原则来控制树的层数和节点位置，

因为rbtree是由AVL演变而来，所以我们从了解AVL开始。