基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找表：用于查找的数据结合称为查找表，它是由同一类型的数据元素（记录）组成，可以是一个数组或链表等数据类型。静态查找表：只用于查找某个元素和检索满足某个条件的数据元素的各种属性的查找表称为静态查找表。动态查找表：在静态查找表基础上，需要动态地插入和删除元素的查找表称为动态查找表。

适合静态查找表的查找方法有：顺序查找、折半查找和散列查找等。适合动态查找表的查找方法有：二叉查找树的查找和散列查找等。关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。比如一个学生数据集合，学号便是这个学生数据集合的关键字，可以唯一标识该学生学生数据集合。

平均查找长度ASL：在查找过程中，一次查找的长度为该次查找需要比较的关键字次数。而ASL是指在所有数据元素的查找过程中，关键字比较次数的平均值。平均查找长度是衡量算法查找效率的最主要的指标。

n表示查找表的长度，Pi表示查找第i个元素的概率，一般认为每个数据元素的概率是相等的，即Pi=1/n。而Ci表示查找到第i个元素的所需的关键字比较次数。因此，查找算法的时间复杂度为ASL和问题规模n的函数关系式的数量级。即查找过程中数据元素关键字的比较次数是分析查找算法时间复杂度的关键指标。

顺序查找

顺序查找又称线性查找，主要用于在线性表中从前往后依次进行查找。顺序查找一般分为无序线性表的顺序查找和有序线性表的顺序查找。顺序查找对于顺序表和链表都适用，不分顺序存储和链式存储的存储结构。

无序线性表的顺序查找

无序线性表的顺序查找是最直观最普通的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在查找表中的位置。若已经查找到表的另一端，还没有查找到符合给定条件的元素，则查找失败。下面以数组为例，顺序查找的代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

using System;

namespace Search
{
    class Client
    {
        // 顺序查找
        public static int SeqSearch(int[] a, int key)
        {
            // 提前把数组的长度提取出来，避免在for循环里多次获取长度消耗性能
            int len = a.Length;
            for (int i = 0; i < len; i++)
            {
                if (a[i] == 6)
                {
                    return i;
                }
            }
            // 返回-1表示查找失败
            return -1;
        }

        public static void Main(string[] args)
        {
            // 1、顺序查找
            int[] a = { 1, 4, 5, 6, 0, 3, 8};
            int b = SeqSearch(a, 6);
            Console.WriteLine(b);
        }
    }
}

// 输出结果：3

这是大多数人都会写的普通写法，但是当数据量比较大时，for循环每次执行完都要和数组长度作比较，这样会造成一定的性能消耗。我们可以通过引入”哨兵“，这样就不必每次循环时都去判断数组是否越界，减少比较次数，提高查找效率。引入”哨兵“进行优化后的代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 顺序查找
public static int SeqSearch(int[] a, int key)
{
    int len = a.Length;
    int i = len;
    // 如果a[0]就是我们要查找的元素，就直接返回0这个位置
    if (a[0] == key)
    {
        return 0;
    }
    // 不是我们要查找的元素，就将a[0]作为”哨兵“
    a[0] = key;
    while (a[i - 1] != key)
    {
        i--;
        // 如果查找到a[0]时还没找到key，就返回-1表示查找失败
        if (i == 1)
        {
            return -1;
        }
    }
    return i;
}

如果a[0]没有存放有效数据，则直接将a[0]作为”哨兵“。在实际开发中，数组下标从0开始，如果查找失败就返回0容易产生歧义，因为它有可能是我们数组中的第一个元素。因此需要做一个判断，查找失败时返回-1。从上面的代码可以看出，引入”哨兵“后，不再需要判断数组是否越界。在数据量比较大时，可以节省一部分性能开销。

有序线性表的顺序查找

在有序线性表的顺序查找中，查找成功的ASL与无序线性表的顺序查找一样。唯一的区别是查找失败时，不用把所有元素查找完。比如，一个有序序列为：10，20，30，40。我们要查找25，当比较完10，20，30时，就直接返回-1表示查找失败。因为该序列是递增的，30以后的数都比25大，不可能查找到25。而无序线性表的顺序查找则必须把剩下的元素比较完，才能得出查找失败的结论。因此，有序线性表的顺序查找效率比无序线性表的顺序查找表效率更高一些。

综上所述，顺序查找的时间复杂度为O(n)。顺序查找的缺点是当问题规模n比较大时，时间复杂度较高，查找效率低。优点是对数据元素的存储结构没有要求，顺序存储和链式存储都可以。此外，对于数据元素的有序性也没有要求，有序无序线性表都可以进行顺序查找。注意，对于线性链表只能使用顺序查找。

折半查找

**折半查找又称二分查找，只适用于有序的顺序表。**折半查找运用了二分法的思想，即在一个有序的顺序表中，通过依次对半查找缩小查找范围，直到查找到目标元素为止。比如，一个有序序列为：10，20，30，40，50，60，70。现在要查找元素20，首先与该有序序列的中间位置(1+7)/2=4对应的元素40进行比较，比40小，所以20应该在序列的左半边。在位置1到位置3这个范围的子序列中，继续与该子序列的中间位置(1+3)/2=2对应的元素进行比较，如果元素相等，则表示查找成功返回元素20在序列中的位置。

折半查找的过程可以用一棵二叉树来表示，这个二叉树称为判定树。判定树中的结点表示一个数据元素，结点中的值表示该数据元素对应的值。查找成功时的查找长度为根节点到目标结点的路径上的结点数。为了使查找过程更加形象，我们添加额外的方形叶结点用于表示查找失败的情况。以刚才查找元素20为例，对应的判定树如下：

从上述分析可知，折半查找法查找成功的关键字比较次数不会超过树的高度。已知n个元素的二叉树的高度近似为log2n，因此折半查找的时间复杂度为O(logn)，平均情况下比顺序查找的效率高。由于折半查找过程中需要方便地定位到中间位置的元素，因此适合折半查找的数据集合必须支持随机存取的特性，即折半查找只适合于采用顺序存储的线性表，不支持采用链式存储的线性表。而且必须要求顺序表有序，不然二分法无法奏效。

由于折半查找的过程是一棵二叉树，因此折半查找的代码实现也分为递归实现和非递归实现。下面是上图中示例的两种折半查找实现代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

using System;

namespace Search
{
    class Client
    {
    		// 折半查找-递归实现
        public static int BinarySearchDiGui(int[] a, int key, int low, int high)
        {
            // 如果key不在要查找的有序序列中或者序列的下界超过上界时，就表示查找失败直接返回-1。
            if (key < a[low] || key > a[high] || low > high)
            {
                return -1;
            }

            // 中间位置mid为下界和上界之和再除以2并进行向下取整后得到的结果
            // int mid = (low + high) / 2;
            int mid = low + (high - low) / 2;
            if (key < a[mid])
            {
                // 如果在序列的左半边，则将序列上界置为mid-1，则原序列变为只有左半边的子序列。
                MidFindDiGui(a, key, low, mid - 1);
            }
            if (key > a[mid])
            {
                // 如果在序列的右半边，则将序列下界置为mid-1，则原序列变为只有右半边的子序列。
                MidFindDiGui(a, key, mid + 1, high);
            }
            return mid;
        }

        // 折半查找-非递归实现
        public static int BinarySearch(int[] a, int key)
        {
            int low = 0;
            int high = a.Length - 1;
            int mid = 0;
            if (key < a[low] || key > a[high] || low > high)
            {
                return -1;
            }
          
            // 当序列的下界等于上界时，此时序列中只有一个元素。如果再进行折半查找low就会大于high，而此时序列中所有元素已经查找完了。如果还没有查找到元素，就直接退出循环，并返回-1表示查找失败。
            while (low <= high)
            {
                //mid = (low + high) / 2;
                mid = low + (high - low) / 2;
                if (key > a[mid])
                {
                    low = mid + 1;
                }
                if (key < a[mid])
                {
                    high = mid - 1;
                }
                return mid;
            }

            return -1;
        }

        public static void Main(string[] args)
        {
            // 2、折半查找
            int[] a = { 10, 20, 30, 40, 50, 60, 70 };
            // 递归实现
            int b1 = BinarySearchDiGui(a, 20, 0, a.Length-1);
            Console.WriteLine(b1);
            // 非递归实现
            int b2 = BinarySearch(a, 20);
            Console.WriteLine(b2);
        }
    }
}

从上面的代码中可以看到，折半查找的中间位置mid的计算有两种方法：mid = (low + high) / 2 和 mid = low + (high - low) / 2，把第二种计算方式的括号打开就变成了第一种方式。但在极端情况下，第一种计算方式会造成int类型溢出。假如数组长度特别大，而元素恰好在low=high-1和high之中，如果采用第一种计算方式，则(low+high)将是一个非常大的数，很有可能会超过int类型所能表示的最大数，这时程序就会报错int类型溢出。因此，推荐使用mid = low + (high - low) / 2来计算中间位置mid的值。

对于递归和非递归的实现，优先推荐使用非递归的实现，除非是找不到更好的方法或者特定情况下才使用递归。因为递归的运行效率较低，在递归过程中，每一次函数调用都会产生额外的开销，函数调用时要为局部变量和参数开辟内存空间。此外，递归需要借助递归工作栈，来存储每一层中函数的返回点和局部变量等数据。如果递归深度过大，会造成系统栈溢出。

此例中递归实现和非递归实现的时间复杂度都是一样的为O(logn)。但非递归实现的空间复杂度为O(1)，而递归实现所需要的空间复杂度为O(logn)。综上所述，折半查找的优点是查找效率较高。缺点是只适用于有序的顺序表，但顺序表插入和删除的时间复杂度较高为O(n)。因此，折半查找属于静态查找，不适合需要动态插入和删除元素的查找表。

插值查找

插值查找是二分查找的改进版，只适用于分布均匀的有序顺序表。二分查找每次都是从有序序列中间查找，这种机械式的对半分是有序序列的通用查找方法。但对于分布均匀的有序序列还有更好的查找方法，那就是插值查找。比如，我们查英文词典时，查China，绝对不会每次都从词典中间开始找。有索引当然先看索引再找，如果不看索引直接查找，我们会习惯性地想C开头的词肯定在词典前面部分，直接翻到前面部分进行查找，这就是插值查找的原理。

插值查找和二分查找唯一的区别就是中间位置mid的计算。二分查找中中间位置mid = low + 1/2 * (high - low)，而插值查找中间位置的计算方式为：mid = low + (key - a[low])/(a[high] - a[low]) * (high - low)。即插值查找将二分查找中的(high - low)的系数由1/2改成了(key - a[low])/(a[high] - a[low])。这样每次查找时就不用机械式地对半分，而是根据key在有序序列中的大概位置进行比较查找，从而减少关键字的比较次数，提高查找效率。

对于分布均匀的有序顺序表，插值查找的时间复杂度为O(log(logn))。但如果有序序列分布不均匀，插值查找的效率还不如二分查找。比如下面这个分布不均匀的有序序列：1，2，3，4，1000，2000，1000000，10000000。如果我们要查找1000，那么按刚才的计算方式mid = 0 + (1000 - 1) / (10000000 - 1) * (7 - 0) = 0，比0位置上的1大，更新low = mid + 1 = 1，继续计算mid = 1 + (1000 - 2) / (10000000 - 2) * (7 - 1) = 0，结果还是0。

依次类推，插值查找要比较5次才能找到1000，而二分查找只需要3次对半分就可查找到1000。如果这个分布不均的有序序列很大，插值查找的效率将会更低。因此，只有当有序序列分布均匀时，才能使用插值查找，因为这样才可以根据比例确定key在有序序列中的大致范围。

斐波拉契查找

斐波拉契查找也是二分查找的改进版，也只适用于有序的顺序表。谈到斐波拉契，首先想到斐波拉契数列。斐波那契数列（Fibonacci sequence），又称黄金分割数列。因为随着数列的递增，斐波拉契数列中的前项与后项的比值越来越接近于黄金比例0.618。黄金比例又称黄金分割，是指将一个整体一分为二，较大部分与整体部分的比值和较小部分与较大部分的比值相等，比值约为0.618。

斐波拉契数列的递归定义为：F(1) = 1，F(2) = 1，F(n) = F(n-1) + F(n-2)（n>=3，n∈N*），即从斐波拉契数列的第三项开始，每一项的值都是前两项之和。而斐波拉契查找就是运用黄金分割的理念在数列中选择查找点进行查找。斐波拉契查找要求查找表的元素个数为n = F[k] - 1，如果待查找的元素个数不够，就把它们的最大值放在查找表末尾凑成一个长度为F[k] - 1的新查找表，然后再进行斐波拉契查找。具体的划分方法如下图所示：

与二分查找一样，也是比较key和mid（mid = low + F[k-1] - 1）对应的元素大小，从而修改low或high的大小。只不过在斐波拉契查找中，还需要修改k的值。如上图所示，如果key>a[mid]，则low = mid + 1，k -= 2。因为，当key大于a[mid]时，说明元素在有序序列黄金分割的后半段共有F[k-2]-1个元素。接着在长度为F[k-2]-1的子序列中继续进行黄金分割，分成F[k-3]-1、mid、F[k-4]-1三部分。这时mid = low + F[k-3] - 1，与起始mid相比，k多减了一个2。因此，key>a[mid]时，还额外需要k -= 2。同理可得，如果key < a[mid]，则high = mid - 1，k -= 1。如果key = a[mid]，还需要判断mid是否在填充位置，是就直接返回查找表的末尾位置，不是就返回mid。

通过上面的分析，现在知道了为什么斐波拉契查找的元素个数必须为F[k]-1。因为mid位置占了一个元素，总元素个数就变成了F[k]-2，而F[k]-2 = F[k-1] + F[k-2] - 2 = (F[k-1] - 1) + (F[k-2] - 1)，刚好可以黄金分割成两段。而分成的两段又都与起始元素个数F[k]-1形式上一致，这样每一段又可以继续进行黄金分割，我们编写代码时只需要修改k的值，十分方便。具体的代码实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

using System;

namespace Search
{
    // 斐波拉契查找类
    class FibSearch
    {
        // 斐波拉契数组最大长度
        const int max_size = 20;

        // 构造斐波拉契数组
        private int[] Fib()
        {
            int[] F = new int[max_size];
            F[0] = 1;
            F[1] = 1;
            // 通过递推而不是递归的方式，使构造斐波拉契数组的时间复杂度降低为O(n)
            for (int i = 2; i < max_size; i++)
            {
                F[i] = F[i - 1] + F[i - 2];
            }
            return F;
        }

        public int Search(int[] a, int key)
        {
            int n = a.Length;
            int low = 0;
            int high = n - 1;
            int mid = 0;
            int[] F = Fib();
            int k = 0;
            while (n >= F[k] - 1)  
            {
                // 如果起始元素个数刚好为某个斐波拉契数-1，可以直接黄金分割，不需要进行填充。
                if (n == F[k] - 1)
                {
                    break;
                }
                k++;
            }

            // 由于数组长度必须为F[k]-1个才能进行黄金分割，因此新建一个临时数组temp用来存放已有的元素，空余的位置用最大值（数组a的最后一个元素）填充。
            int[] temp = new int[F[k]-1];
            Array.Copy(a, temp, n);
            for (int i = n; i < F[k]-1; i++)
            {
                temp[i] = a[n - 1];
            }

            while (low <= high)
            {
                mid = low + F[k - 1] - 1;
                if (key < temp[mid])
                {
                    high = mid - 1;
                    k -= 1;
                }
                else if (key > temp[mid])
                {
                    low = mid + 1;
                    k -= 2;
                }
                else
                {
                    // 如果mid超出了原有数组的范围，则表示该元素为最大值，直接返回原有数组的末尾位置。
                    if (mid >= n)
                    {
                        return n - 1;
                    }
                    return mid;
                }
            }

            return -1;
        }
    }

    class Client
    {
        public static void Main(string[] args)
        {
            // 4、斐波拉契查找
            int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            FibSearch fs = new FibSearch();
            int i = fs.Search(a, 6);
            Console.WriteLine(i);
        }
    }
}

// 输出结果：5

斐波拉契查找的时间复杂度为O(logn)，而且是只用加减法的二分查找。二分查找的效率与使用加减法还是乘除法没有直接关系。因为乘除法完全可以用位运算来代替，而位运算的速度远高于乘除法的运算速度。此外，斐波拉契查找依然只适用于有序的顺序表，并且与顺序表是否分布均匀无关。因为，无论顺序表是否分布均匀，斐波拉契查找都是运用黄金比例来寻找mid的位置。

分块查找

分块查找又称索引顺序查找，结合了顺序查找和折半查找各自的优点，既有动态结构，又适合于快速查找。分块查找的基本思想：将查找表分为若干子块，块内无序，块间有序。即第一个块中的最大关键字小于第二块中的所有关键字，第二块中的最大关键字小于第三块中的所有的关键字，依次类推。再建立一个索引表，索引表中的各个元素都含有各个块中的最大关键字和各块中第一个元素的地址，索引表按关键字有序排列。以下图为例，查找表和索引表的对应关系如下：

分块查找的ASL为索引查找的ASL和块内查找的ASL之和。设将长度为n的查找表分为b块，每块有s个元素，如果索引查找和块内查找都采用顺序查找时，则当且仅当s = n的算术平方根时，分块查找的ASL最小，即效率最高。下面是以上图为例的分块查找代码实现：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

using System;
using System.Collections.Generic;

namespace Search
{
    // 分块查找类
    class BlockSearch
    {
        // 索引表
        private int[] index;
        // 索引表长度
        private int len;
        // 索引表对应的块数组
        private List<int>[] block;

        // 初始化索引表
        public BlockSearch(int[] elements, int[] index)
        {
            this.index = index;
            this.len = index.Length;
            int num = elements.Length;
            this.block = new List<int>[len];
            // 初始化每个块
            for (int i = 0; i < len; i++)
            {
                block[i] = new List<int>();
            }
            // 对所有元素进行分块
            for (int i = 0; i < num; i++)
            {
                Insert(elements[i]);
            }
        }

        // 用二分查找对分块元素进行索引定位
        private int BlockIndex(int key)
        {
            int start = 0;
            int end = len - 1;
            int mid = 0;
            while (start <= end)
            {
                mid = start + (end - start) / 2;
                if (key < index[mid])
                {
                    end = mid - 1;
                }
                if (key > index[mid])
                {
                    start = mid + 1;
                }
                if (key == index[mid])
                {
                    return mid;
                }
            }
            return start;
        }

        // 插入元素
        public void Insert(int key)
        {
            int start = BlockIndex(key);
            block[start].Add(key);
        }

        // 删除元素
        public void Delete(int key)
        {
            int start = BlockIndex(key);
            block[start].Remove(key);
        }

        // 具体的分块查找，块内采用顺序查找
        public int Search(int key, out int start)
        {
            start = BlockIndex(key);
            int num = block[start].Count;
            for (int i = 0; i < num; i++)
            {
                if (block[start][i] == key)
                {
                    return i;
                }
            }
            return -1;
        }

        // 输出所有元素
        public void Print()
        {
            for (int i = 0; i < len; i++)
            {
                for (int j = 0; j < block[i].Count; j++)
                {
                    Console.Write(block[i][j]+" ");
                }
            }
            Console.WriteLine();
        }
    }

    class Client
    {
        public static void Main(string[] args)
        {
            // 5、分块查找
            int[] elements = { 24, 21, 6, 11, 8, 22, 32, 31, 54, 72, 61, 78, 88, 83 };
            int[] index = { 24, 54, 78, 88 };
            BlockSearch bs = new BlockSearch(elements, index);
            bs.Insert(35);
            bs.Delete(61);
            bs.Print();
            int block;
            int i = bs.Search(78, out block);
            if (i == -1)
            {
                Console.WriteLine("Not Found");
                return;
            }
            Console.WriteLine("该元素位于第{0}块第{1}个位置", block + 1, i + 1);
        }
    }
}

// 输出结果：
// 24 21 6 11 8 22 32 31 54 35 72 78 88 83 
// 该元素位于第3块第2个位置

从代码中可以看出，分块查找的时间复杂度介于顺序查找和二分查找之间，还可以动态地插入和删除元素。由于分块查找中块内查找必须采用顺序查找，因此分块时每一块不能太大，不然影响块内查找的效率。但如果每一个块太小，建立一个有序的索引表比较耗时，这样分块查找就没有意义了，还不如先排好序直接进行二分查找。即使有动态地插入和删除元素的需求，块数过多也会降低索引查找的效率。

因此，要在块数和块内元素数量之间找到一个平衡。在上述分块查找的代码中，索引查找的ASL为log2(b+1)取上整，块内查找的ASL为(s+1)/2。当两者之和最小时，可以求得块数b和块内元素个数s的关系式，从而找到b和s之间的平衡。在实际开发中，分块思想很重要。比如，把服务器请求日志按年月日分块，从而可以快速查找到某一天的服务器请求日志。

散列查找

谈到散列查找，我们首先想到散列表，又称哈希表。在常用数据结构与算法之数组中，我们讲到哈希表是一个直接根据关键字访问元素的数据结构。通过哈希函数将查找表中的关键字映射成该关键字对应的地址，记为Hash(key)=Addr，这个地址可以数组下标、索引、内存地址等。理想情况下，散列查找的时间复杂度为O(1)，与表中元素个数无关。但如果出现哈希冲突，查找的时间复杂度就会增大。因此，我们应尽量较少哈希冲突的发生。

哈希冲突是指哈希函数将多个不同的关键字映射到同一地址，这样就无法直接准确的查找到关键字对应的元素。我们把发生冲突的多个不同的关键字称为同义词。哈希冲突是不可避免的，只能减少。而减少哈希冲突的发生主要分两个方面：源头治理，即选取一个产生冲突几率较小的哈希函数；对症下药，即选取一个好的冲突解决办法。常用的哈希函数构造法有：直接定址法，除留命数法，数字分析法和折叠法等。常用的冲突解决办法有：线性探测法和拉链法等。哈希表在实际开发中应用广泛，很多编程语言都内置了哈希表相关的数据结构。

树表查找

树表查找的本质是遍历整棵树的结点，然后将key与每个结点的关键字进行比较，相同就返回结点的位置，如果全部遍历完都没查找到，就表示查找失败。不同的树的查找时间复杂度不同，最简单的树表查找就是二叉查找树的查找。二叉查找树的中序序列就是一个有序序列，它的查找时间复杂度和二分查找相同都是O(logn)。但最坏情况下时间复杂度为O(n)，即二叉查找树退化成一棵单支树。

二分查找只适用于有序的顺序表，插入和删除元素的时间复杂度为O(n)。而二叉查找树一般采用链式存储，不要求查找表有序，插入和删除元素的时间复杂度为O(logn)。因此，如果有序表是静态查找表，则采用顺序存储并用二分查找来完成查找操作。如果有序表是动态查找表，则采用链式存储并用二叉查找树作为查找的逻辑结构。但是通过有序表构造的二叉查找树是一棵单支树，查找时间复杂度最坏为O(n)。因此我们引入了平衡二叉树AVL树来避免二叉查找树因树高增长过快而导致查找性能降低。

除了AVL树，与二叉查找树相关的还有红黑树和B/B+树，这三种二叉查找树查找、插入和删除元素的时间复杂度都是O(logn)。只是应用领域不同，红黑树主要应用于关联数组（key-value键值对）的实现。比如：C++中的map、multimap和multiset，JAVA中的TreeMap和TreeSet，.NET中的SortedDictionary和SortedSet。注意，红黑树实现的关键数组是有序的，而哈希表实现的关联数组是无序的。比如，.NET中的Dictionary是无序的，是用哈希表来实现的。B/B+树主要应用于数据库和文件系统，比如：MySQL和Oracle数据库，Windows、MAC和Linux的文件系统等。