一、二叉排序树
1.二叉排序树性质
首先二叉排序树也是一棵二叉树，所谓二叉树，就是“任何节点最多只允许两个子节点”，这两个子节点称为左右子节点。
（1）、就是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
（2）、若它的右子树不空，则右子树上所有节点的值均大于其根节点的值。
（3）、换句话说就是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。
2.二叉排序树的查找原理
因为二叉排序树是可以看作是一个有序表，所以其查找过程和折半查找类似。
算法思想：
首先将待查关键字key与根节点关键字t进行比较：
a.如果key = t, 则返回根节点指针。
b.如果key < t,则进一步查找左子树。
c.如果key > t,则进一步查找右子树。
3.核心代码
-
public boolean searchBST(int key){
-
Node current = root;
-
while(current != null){
-
if(key == ())
-
return true;
-
else if(key < ())
-
current = ();
-
else
-
current = ();
-
}
-
return false;
-
}
4.平均查找长度
最差与顺序查找相同：ASL = (n+....+2+1)/n= (n+1)/2
最好和折半查找相同：ASL = log2(n)
二、平衡二叉树
1.平衡二叉树性质
平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
三、B树
树的性质
一棵m阶的B树满足下列条件：
树中每个结点至多有m个孩子。
除根结点和叶子结点外，其它每个结点至少有m/2个孩子。
根结点至少有2个孩子（如果B树只有一个结点除外）。
所有叶结点在同一层，B树的叶结点可以看成一种外部节点，不包含任何信息。
有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。