1 折半查找法

了解二叉查找树之前，先来看看折半查找法,也叫二分查找法
在一个有序的整数数组中（假如是从小到大排序的），如果查找某个元素，返回元素的索引。
如下：

int[] arr = new int[]{1,3,4,6,8,9}; 在 arr 数组中查找6这个元素，查到返回对应的索引，没有找到就返回-1

思想很简单:
1 先找到数组中间元素target与6比较
2 如果target比6大，就在数组的左边查找
3 如果target比6小，就在数组的右边查找

java实现代码如下：

    private static int binarySearch(int[] data, int target) {         int l = 0;         int r = data.length - 1;          while (l <= r) {             //int mid = (l + r) / 2;             //这句代码理论上是没有问题的，但是是有bug的             //如果因为 l + r 会超过整数的最大值，就会溢出             //所以换成下面的写法，最小边界，加上差的一半，就是中间索引              //最小边界，加上差的一半，就是中间值             int mid = l + (r - l) / 2;               if (data[mid] > target) { //如果中间的值比target大,r向右移动。                 r = mid - 1;             } else if (data[mid] < target) { //如果中间的值比target小，l向左移动                 l = mid + 1;             } else {                 return mid; //如果中间的值与target相等，就返回下标             }         }          //没有找到就返回-1         return -1;     }

测试代码如下：

 public static void main(String[] args) {         int[] data = new int[]{1,3,4,6,8,9};         System.out.println(binarySearch(data, 6));     }

输出

3

折半查找的关键是数组必须有序，一次过滤掉一半的数据，时间复杂度为O（logN）。
上面是以2为底的，N为数组的元素个数.

折半查找和下面的要讲的二分搜索树是有一样的思想

2 二分搜索树定义

二分搜索树定义双叫二分查找树，其定义如下
1 若它的左子树不为空，则左子树上所有的节点的值均小于根结点的值
2 若它的右子树不为空，则右子树上所有的节点的值均大于根结点的值
3 它的左右子树也分别为二分搜索树

由二叉搜索树的定义可知，它前提是二叉树，并且采用了递归的定义方式
。再得，它的节点满足一定的关系，左子树的节点一定比父节点的小，
右子树的节点一定比父节点的大。

构造一棵二叉搜索树的目的，其实目的不是为了排序，是为了提高查找，删除，插入关键字的速度。

下面我们用图和代码来解释二叉树的查找，插入，和删除。比如下图就是一个二叉搜索树

2.0 二叉搜索树的定义和节点的定义

二叉搜索树中存放的都是key。先看下二叉树的定义

    //key必须继承Comparable，可以比较大小的     public class QBST<K extends Comparable<K>, V> {         ...     }

二叉树中节点的定义

   //QNode是作为QBST的内部类的。后面会有完整的源码    class QNode {         //key,也相当于上图中的数字，只不过不一定是数字         //只要能比较大小就行了。这里的key，是继承Comparable的         K key;                       //节点中的value         V value;                  //左子树         QNode left;                  //右子树         QNode right;          //根据key,value构造一个节点         QNode(K key, V value) {             this.key = key;             this.value = value;             this.left = null;             this.right = null;         }          //根据一个节点，构造另一个新节点         QNode(QNode node){             this.key = node.key;             this.value = node.value;             this.left = node.left;             this.right = node.right;         }     }

类的定义和类中节点的定义都有了。
二分搜索树的定义如下：

                    

                        
关键字：