侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

二叉排序(查找)树的定义及实现

kaixindeken
2021-04-22 / 0 评论 / 0 点赞 / 76 阅读 / 3,395 字

为什么要引入二叉排序树

数组、链表、散列表等,数组查找性能高,但是插入、删除性能差,链表插入、删除性能高,但查找性能差,在不考虑散列冲突的话,散列表的插入、删除、查找性能都很高,但是前提是没有散列冲突,此外,散列表存储的数据是无序的,散列表的扩容非常麻烦,涉及到散列冲突时,性能不稳定,另外,散列表用起来爽,构造起来可不简单,要考虑散列函数的设计、哈希冲突的解决、扩容缩容等一系列问题,有没有一种插入、删除、查找性能都不错,构建起来也不是很复杂,性能还很稳定的数据结构呢?这就是我们今天要介绍的数据结构 —— 二叉排序树。

什么是二叉排序树

二叉排序树是一种特殊的二叉树,我们重点关注「排序」二字,二叉排序树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值,所以这么看来,二叉排序树是天然有序的,如果按照昨天讲的中序遍历,得到将是一个从小到大的有序数据集。但是构造二叉排序树的目的,并不是为了排序,而是为了提高查找、插入和删除的速度。不管怎么说,在一个有序数据集上查找数据肯定比无序数据集要快,同时二叉排序树这种非线性结构,也非常有利于插入和删除的实现。

注:二叉排序树也叫做二叉查找树,二叉搜索树,你如果看到类似概念,它们是一个意思。

下面我们就来看看如何实现二叉排序树的插入、查找和删除以及它们对应的时间复杂度。

二叉排序树的插入

首先我们先定义好基本的类结构,还是通过二叉链表来存储二叉排序树,对应的节点类如下:

void insert(int data) {
        if (!this->tree){
            this->tree = new Node(data);
            return;
        }
        Node* p = this->tree;
        while (p) {
            if (data < p->data){
                if (!p->left) {
                    p->left = new Node(data);
                    return;
                }
                p = p->left;
            } else if (data > p->data){
                if (!p->right){
                    p->right = new Node(data);
                    return;
                }
                p = p->right;
            }
        }
}

如果是空树,则将其作为根节点,否则判断插入节点数据与当前节点数据的大小,如果小于当前节点,则递归遍历左子树,找到对应的位置插入,如果大于当前节点,则递归遍历右子树找到对应的位置插入。

我们可以写一段简单的测试代码测试节点插入:

BinarySortedTree tree = BinarySortedTree();
tree.insert(3);
tree.insert(2);
tree.insert(5);
tree.insert(1);
tree.insert(4);
midOrderTraverse(tree.getTree());

这里我们使用了中序遍历方法 midOrderTraverse,对应的输出结果如下:

截屏20210422 上午11.16.56.png

二叉排序树的查找

二叉排序树的删除比较复杂,我们先来看查找实现,查找实现非常简单,和插入类似,依次递归比较就好了,直到直到对应节点,或者返回空,表示没有找到:

Node* find(int data){
        Node* p = this->tree;
        while (p) {
            if (data < p->data){
                p = p->left;
            } else if (data > p->data){
                p = p->right;
            } else {
                return p;
            }
        }
        return nullptr;
}

还是借助前面的测试代码,我们可以通过

std::cout<< tree.find(3) << std::endl;

打印找到节点的对象信息。

二叉排序树的删除

二叉排序树的删除相对而言要复杂一些,需要分三种情况来处理:

  • 第一种情况是,如果要删除的节点没有子节点,我们只需要直接将父节点中,指向要删除节点的指针置为 null。比如图中的删除节点 55。
  • 第二种情况是,如果要删除的节点只有一个子节点(只有左子节点或者右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。
  • 第三种情况是,如果要删除的节点有两个子节点,这就比较复杂了。我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除掉这个最小节点,因为最小节点肯定没有左子节点(如果有左子结点,那就不是最小节点了),所以,我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。(同理,也可以通过待删除节点的左子树中的最大节点思路来实现)

1.jpeg

下面我们给出删除逻辑实现代码:

void del(int data){
        if (!this->tree){
            this->tree = new Node(data);
            return;
        }
        Node* p = this->tree;
        Node* pp = nullptr;
        while (p && p->data != data){
            pp = p;
            if (data < p->data){
                p = p->left;
            } else if (data > p->data){
                p = p->right;
            }
        }
        if (p == nullptr){
            return;
        }
        if (p->left && p->right){
            Node* minP = p->right;
            Node* minPP = p;
            while(minP->left){
                minPP = minP;
                minP = minP->left;
            }
            p->data = minP->data;
            p = minP;
            pp = minPP;
        }
        Node* child = nullptr;
        if (p->left){
            child = p->left;
        } else if (p->right){
            child = p->right;
        }

        if (!pp){
            this->tree = child;
        } else if (pp->left == p){
            pp->left = child;
        } else {
            pp->right = child;
        }
}

二叉排序树的时间复杂度

不论是插入、删除、还是查找,二叉排序树的时间复杂度都等于二叉树的高度,最好的情况当然是满二叉树或完全二叉树,此时根据完全二叉树的特性,时间复杂度是 O(logn),性能相当好,最差的情况是二叉排序树退化为线性表(斜树),此时的时间复杂度是 O(n),所以二叉排序树的形状也很重要,不同的形状会影响最终的操作性能。

0

评论区