定义：

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：

二叉搜索树时一个用于查找操作的搞笑数据结构，因为在最坏的情况下只要查找其中一个分支上的数据就可以了。复杂度为O（nlg n），n为二叉树元素的个数。所以在实际使用中，尽可能的保证二叉树的平衡，这样对搜索来说是最高效的。

二叉树的实现和分析

前面提到，只有当二叉树搜索树保持平衡时对搜索来说才是最高效的，如何保持平衡，实际上很难得。在实际运用中使用最多的就是AVL树，专门在百度百科上专门搜索了下。下面是概述：

********************************************************************************

概述

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。

AVL 节点数计算

高度为 h 的 AVL 树，节点数 N 最多2^h 1； 最少 （其中）。

最少节点数 n 如以费伯纳西数列可以用数学归纳法证明：

Nh= F【h+ 2】 - 1 (F【h+ 2】是 Fibonacci polynomial 的第h+2个数）。

即：

N0 = 0 （表示 AVL Tree 高度为0的节点总数）

N1 = 1 （表示 AVL Tree 高度为1的节点总数）

N2 = 2 （表示 AVL Tree 高度为2的节点总数）

Nh= N【h 1】 + N【h 2】 + 1 （表示 AVL Tree 高度为h的节点总数）

换句话说，当节点数为 N 时，高度 h 最多为。

节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

操作

AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运做的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL 旋转"。