数据结构与算法分析：（十五）二叉查找树

一时失言乱红尘 2023-07-26 05:29 8阅读 0赞

上一篇我们学了树、二叉树以及二叉树的遍历。请戳：[数据结构与算法分析：（十四） 二叉树][Link 1]

二叉树的种类各种各样，这一篇我们主要来讲二叉查找树。二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。

## 一、二叉查找树（Binary Search Tree） ##

二叉树的一个重要应用是它们在查找中的使用，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。这里提一个小问题：我们之前讲过散列表，如下链接，散列表的操作比二叉查找树更高效，时间复杂度都是O(1)。**既然散列表这么高效，那散列表是否完全可以替代二叉查找树？**

[数据结构与算法分析：（十一）散列表（上）][Link 2]  
[数据结构与算法分析：（十二）散列表（下）][Link 3]

答案是否定的，存在即合理。接下来我们来看下二叉查找树的一些性质。

二叉查找树要求，假设树中每个节点存储一项数据，对于树中的每个节点 X，它的左子树中所有项的值小于X中的项，而它的右子树中所有项的值大于X中的项。注意，这意味着该树所有的元素可以用某种一致的方式排序。下面我画个图你就知道了。

![在这里插入图片描述][20200415213348389.png]

左边的树是二叉查找树，但右边的则不是。右边的树在其项是6的节点（该节点正好是根节点）的左子树中，有一个节点的项是7。这下明白了吧！前面我们说二叉查找树支持快速查找、插入、删除操作，接下来我们来看下它们是如何操作的。

**1、二叉查找树的查找操作**

首先，我们看如何在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

![在这里插入图片描述][20200415220207613.png]

下面用代码实现一遍，结合上面的图更加容易理解了。

public class BinarySearchTree { 
    
        private Node tree;
    
        public Node find(int data) { 
            Node p = tree;
            while (p != null) { 
                if (data < p.data) p = p.left;
                else if (data > p.data) p = p.right;
                else return p;
            }
            return null;
        }
    
        public static class Node { 
            private int data;
            private Node left;
            private Node right;
    
            public Node(int data) { 
                this.data = data;
            }
        }
    
    }

**2、二叉查找树的插入操作**

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

![在这里插入图片描述][2020041522070639.png]

代码如下：

public void inset(int data) { 
        if (tree == null) { 
            tree = new Node(data);
            return;
        }
    
        Node p = tree;
        while (p != null) { 
            if (data < p.data) { 
                if (p.left == null) { 
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            } else {  // data > p.data
                if (p.right == null) { 
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            }
        }
    }

**3、二叉查找树的删除操作**

前面的查找、插入都比肩简单易懂，删除操作就有点复杂了。针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。

第一种情况：如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。

第二种情况：如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。

第三种情况：如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。

![在这里插入图片描述][20200415223748386.png]

代码如下：

public void delete(int data) { 
        Node p = tree; // p指向要删除的节点，初始化指向根节点
        Node pp = null; // pp记录的是p的父节点
        while (p != null && pp.data != data) { 
            pp = p;
            if (data < p.data) p = p.left;
            else p = p.right;
        }
        if (p == null) return; // 没有找到
    
        // 要删除的节点有两个子节点
        if (p.left != null && p.right != null) {  // 查找右子树中最小节点
            Node minP = p.right;
            Node minPP = p; // minPP表示minP的父节点
            while (minP.left != null) { 
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data; // 将minP的数据替换到p中
            p = minP; // 下面就变成了删除minP了
            pp = minPP;
        }
    
        // 删除节点是叶子节点或者仅有一个子节点
        Node child; // p的子节点
        if (p.left != null) child = p.left;
        else if (p.right != null) child = p.right;
        else child = null;
    
        if (pp == null) tree = child; // 删除的是根节点
        else if (pp.left == p) pp.left = child;
        else pp.right = child;
    }

## 二、二叉查找树的时间复杂度分析 ##

二叉树的形态各式各样，有的直接退化成了一条链表，所以查找的时间复杂度是 O(n)。

退化成链表是最糟的情况，我们现在来分析一个最理想的情况，二叉查找树是一棵完全二叉树（或满二叉树）。这个时候，插入、删除、查找的时间复杂度是多少呢？

从前面讲的来看，，不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。既然这样，现在问题就转变成另外一个了，也就是，如何求一棵包含 n 个节点的完全二叉树的高度？

树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示。完全二叉树的图上一篇也画过，不难想象，包含 n 个节点的完全二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点，依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2^(K-1)。

不过，对于完全二叉树来说，最后一层的节点个数有点儿不遵守上面的规律了。它包含的节点个数在 1 个到 2^(L-1) 个之间（我们假设最大层数是 L）。如果我们把每一层的节点个数加起来就是总的节点个数 n。也就是说，如果节点的个数是 n，那么 n 满足这样一个关系：

> n >= 1+2+4+8+…+2^(L-2)+1  
> n <= 1+2+4+8+…+2^ (L-2)+2 ^(L-1)

借助等比数列的求和公式，我们可以计算出，L 的范围是\[ log ⁡ 2 ( n + 1 ) \\log\_2(n+1) log2(n\+1) ,  log ⁡ 2 n \\log\_2n log2n\+1\]。完全二叉树的层数小于等于 log ⁡ 2 n \\log\_2n log2n\+1，也就是说，完全二叉树的高度小于等于  log ⁡ 2 b \\log\_2b log2b。

显然，极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求。我们需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树，这就是我们下一节课要详细讲的，一种特殊的二叉查找树，`平衡二叉查找树`。平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。

[Link 1]: https://blog.csdn.net/riemann_/article/details/105496071
[Link 2]: https://blog.csdn.net/riemann_/article/details/105181212
[Link 3]: https://blog.csdn.net/riemann_/article/details/105301851
[20200415213348389.png]: /images/20230528/35ebb98a91924701b9338d4e7e42fdbb.png
[20200415220207613.png]: /images/20230528/b248c19fc753434aa2007797a836b4e8.png
[2020041522070639.png]: /images/20230528/241b785905c449ba99eb7659fb51b608.png
[20200415223748386.png]: /images/20230528/a5b264c1d5ad43518703fa23b2f71894.png