二叉查找树的高度决定了二叉查找树的查找效率。
和普通的二叉树相比，二叉查找树的节点是有序的。
二叉查找树的插入过程如下：
若当前的二叉查找树为空，则插入的元素为根节点;
若插入的元素值小于根节点值，则将元素插入到左子树中;
若插入的元素值不小于根节点值，则将元素插入到右子树中。
4.1、二叉查找树的实现
节点类：因为要比较节点大小，所以继承Comparable类
/** * 二叉查找树节点 * * @param <T> */ class BSTNode<T extends Comparable<T>> { T key; // 关键字(键值) BSTNode<T> left; // 左孩子 BSTNode<T> right; // 右孩子 BSTNode<T> parent; // 父结点 //省略构造方法、getter、setter }插入：插入需要比较插入节点和当前节点的大小
/** * 将结点插入到二叉树中 * * @param bst 二叉树 * @param z 插入的节点 */ private void insert(BSTree<T> bst, BSTNode<T> z) { int cmp; BSTNode<T> y = null; BSTNode<T> x = bst.mRoot; // 查找z的插入位置 while (x != null) { y = x; //与当前节点比较 cmp = z.key.compareTo(x.key); //比当前节点小，插入为左孩子 if (cmp < 0) { x = x.left; } else { //比当前节点大，插入为右孩子 x = x.right; } } z.parent = y; if (y == null) bst.mRoot = z; else { cmp = z.key.compareTo(y.key); if (cmp < 0) { y.left = z; } else { y.right = z; } } } /** * 新建结点(key)，并将其插入到二叉树中 * @param key 插入结点的键值 */ public void insert(T key) { BSTNode<T> z = new BSTNode<T>(key, null, null, null); //插入新节点 if (z != null) { insert(this, z); } }查找:查找的节点比当前节点大就去查找右子树，比当前节点小就去查找左子树。
/** * (递归实现)查找"二叉树x"中键值为key的节点 * @param x * @param key * @return */ private BSTNode<T> search(BSTNode<T> x, T key) { if (x == null) { return x; } int cmp = key.compareTo(x.key); if (cmp < 0) { return search(x.left, key); } else if (cmp > 0) { return search(x.right, key); } else { return x; } } public BSTNode<T> search(T key) { return search(mRoot, key); } /** * (非递归实现)查找"二叉树x"中键值为key的节点 * @param x * @param key * @return */ private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) { while (x != null) { int cmp = key.compareTo(x.key); if (cmp < 0) { x = x.left; } else if (cmp > 0) { x = x.right; } else { return x; } } return x; } public BSTNode<T> iterativeSearch(T key) { return iterativeSearch(mRoot, key); }其余操作遍历，删除，清空等这里不再赘言。
5、平衡二叉树
二叉查找树查找算法的性能取决于二叉树的结构，而 二叉查找树的形状则取决于其数据集。
如果数据呈有序排列，则二叉排序树是线性的，查找的时间复杂度为O(n); 反之，如果二叉排序树的结构合理，则查找速度较快，查找的时间复杂度为 O(log~2~n)。
树的高度越小，查找速度越快——从树的形态来看，就是使树尽可能平衡。
有资料将平衡二叉树和AVL视作一体，本文采用了AVL树是平衡二叉树的一种的说法。
5.1、AVL树