数据结构-树(五)

二叉搜索树又称二叉查找树，亦称二叉排序树，如下图所示：

它主要用于搜索。 它或者是一棵空树，或者是具有下列性质的二叉树：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3. 左、右子树也分别为二叉排序树。

平衡二叉树

平衡二叉树(平衡二叉树又被称为 AVL 树 )是基于二分法的策略提高数据的查找速度的二叉树的数据结构。

特点：平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据，用这个树形结构的数据减少无关数据的检索，大大的提升了数据检索的速度；平衡二叉树的数据结构组装过程有以下规则：

1. 非叶子节点只能允许最多两个子节点存在。

2. 每一个非叶子节点数据分布规则为左边的子节点小于前节点的值，右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的，比如 hash 值)。