二叉搜索树

1820

二叉树的存储

二叉树的存储结构有两种，分别为顺序存储和链式存储。

二叉树的顺序存储结构

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。

普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其”拼凑”成完全二叉树即可。

image.png

完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。

image.png
其实二叉树并不适合用数组存储，因为并不是每个二叉树都是完全二叉树，普通二叉树使用顺序表存储或多或多会存在空间浪费的现象。

在 n 个动态的整数中搜索某个整数？（查看其是否存在）
假设使用动态数组存放元素，从第 0 个位置开始遍历搜索，平均时间复杂度：O(n)

image.png
如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度：O(logn)
；但是添加、删除的平均时间复杂度是 O(n)

image.png

针对这个需求，有没有更好的方案？
使用二叉搜索树，添加、删除、搜索的最坏时间复杂度均可优化至：O(logn)

二叉树的链式存储结构

既然顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域。表示方式如图

image.png

二叉搜索树

二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST。又被称为：二叉查找树、二叉排序树。
其特性为：
  1）任意一个节点的值都大于其左子树所有节点的值；
  2）任意一个节点的值都小于其右子树所有节点的值；
  3）它的左右子树也是一棵二叉搜索树。

示例：
image.png

二叉搜索树可以大大提高搜索数据的效率。
观察二叉搜索树结构可知，查询每个节点需要的比较次数为节点深度加一。如深度为 0，节点值为 “8” 的根节点，只需要一次比较即可；深度为 1，节点值为 “3” 的节点，只需要两次比较。即二叉树节点个数确定的情况下，整颗树的高度越低，节点的查询复杂度越低。

注意：二叉搜索树存储的元素必须具备可比较性

1）比如 int、double 等；
2）如果是自定义类型，需要指定比较方式；
3）不允许为 null。

我们定义可以定义如下节点类：

/**
 * 节点类
 * @param <E> 泛型
 */
private static class Node<E> {
    E element; //节点数据
    Node<E> left; //左节点
    Node<E> right; //右节点
    Node<E> parent; //父节点 - 额外增加

    public Node(E element, Node<E> parent) {
        this.element = element;
        this.parent = parent;
    }
}
复制代码

接口设计：

// 元素的数量
public int size() {}

// 是否为空
public boolean isEmpty() {}

// 添加元素
public void add(E element) {}

// 删除元素
public void remove(E element) {}

// 是否包含某元素
public boolean contains(E element) {}
复制代码

接下来针对上面的接口一一实现

添加元素

添加元素（节点）的步骤：
1、找到父节点 parent；
2、创建新节点 node；
3、parent.left = node（比找到的 parent 的值小） 或者 parent.right = node（比找到的 parent 的值大）。

// 添加元素
public void add(E element) {
    elementNotNullCheck(element);

    // 添加根节点
    if (root == null) {
        root = new Node<>(element, null);
        size++;
        return;
    }

    // 添加的不是第一个节点
    // 1.找到父节点
    Node<E> parent = root;
    Node<E> node = root;
    int cmp = 0;
    while (node != null) {
        // 保存父节点，如果此时不保存的话，在 while 循环发现 node == null 的时候，跳出循环
        parent = node;

        cmp = compare(element, node.element);
        if (cmp > 0) {
            node = node.right;
        } else if (cmp < 0) {
            node = node.left;
        } else { // 相等
            return;
        }
    }

    // 2.看看插入到父节点的哪个位置
    Node<E> newNode = new Node<>(element, parent);
    if (cmp > 0) {
        parent.right = newNode;
    } else {
        parent.left = newNode;
    }
    size++;
}


上面调用的 compare 先实现为节点的值类型为 Integer（即可以直接进行减法比较值大小）如下：
/**
 * 节点值比较
 * @param e1
 * @param e2
 * @return 返回值等于0，代表e1 == e2；返回值大于0，代表e1 > e2；返回值小于0，代表e1 < e2；
 */
private int compare(Integer e1, Integer e2) {
    return e1 - e2;
}
复制代码

当然针对引用数据类型，需要实现 Comparable 接口，使其具有可比较性，
如 Person 类：

/**
 * 自定义 Person 类，实现 Comparable
 */
public class Person implements Comparable{
    private String name;
    private int age;
    private int height;

    public Person(String name, int age, int height) {
        this.name = name;
        this.age = age;
        this.height = height;
    }

    @Override
    /**
     * 比较规则为年龄大小
     */
    public int compareTo(Object o) {
        Person p = (Person)o;
        return age - p.age;
    }
}
复制代码

另外可以设计接口，让调用方传入比较器，这时，如果外界传入了比较器，则使用传入的比较器，否则使用默认的比较器（Person 类重写的 compareTo 方法）。

所以 BinarySearchTree 新增构造器和成员变量：

public class BinarySearchTree<E> {
    private int size; // 树元素大小
    private Node<E> root; // 根节点

    private Comparator<E> comparator; // 比较器，可由外部控制比较器规则

    // 外部不传入比较器规则，则使用默认的存入节点的对象实现的比较规则
    public BinarySearchTree() {
        this(null);
    }

    // 外部传入比较器规则，则使用传入的比较规则
    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }


    // 元素的数量
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 添加元素
    public void add(E element) {
        elementNotNullCheck(element);

        // 添加根节点
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }

        // 添加的不是第一个节点
        // 1.找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null) {
            // 保存父节点，如果此时不保存的话，在 while 循环发现 node == null 的时候，跳出循环
            parent = node;

            cmp = compare(element, node.element);
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else { // 相等
                return;
            }
        }

        // 2.看看插入到父节点的哪个位置
        Node<E> newNode = new Node<>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
    }

    /**
     * 节点值比较
     * @param e1
     * @param e2
     * @return 返回值等于0，代表e1 == e2；返回值大于0，代表e1 > e2；返回值小于0，代表e1 < e2；
     */
    private int compare(E e1, E e2) {
        // 外部传入了可比较器则使用传入的可比较器
        if (this.comparator != null) {
            return comparator.compare(e1, e2);
        }

        // 外部未可比较器则使用e1对应类实现的Comparable的比较器，因为二叉搜索树的节点必须存放可比较的对象元素
        return ((Comparable<E>)e1).compareTo(e2);
    }
}
复制代码

这样外部调用可穿比较器也可不传（不传则使用自定义类实现的比较方法的比较规则）：

// 使用默认比较器进行（即使用Person类实现的compare规则）
BinarySearchTree<Person> personBst1 = new BinarySearchTree<>();
personBst1.add(new Person("zhangsan", 18, 55));
personBst1.add(new Person("lisi", 19, 60));
personBst1.add(new Person("wangwu", 20, 65));

// 使用自定义比较器进行
BinarySearchTree<Person> personBst2 = new BinarySearchTree<>(new Comparator<Person>() {
    @Override
    public int compare(Person o1, Person o2) {
        return o1.getHeight() - o2.getHeight();
    }
});
personBst2.add(new Person("zhangsan", 18, 55));
personBst2.add(new Person("lisi", 19, 60));
personBst2.add(new Person("wangwu", 20, 65));
复制代码

查询元素节点

二叉搜索树根据元素查找节点。

查询思路：遍历二叉树，在遍历过程中比较查找元素和当前节点元素值的大小，再分别查找对应的子树
具体实现如下：

/**
 * 通过值找到节点
 */
private Node<E> node(E element) {
    Node<E> node = root;
    while (node != null) {
        int cmp = compare(element, node.element);

        // 相等（即找到）直接返回
        if (cmp == 0) return node;

        // 查询元素比节点值大，则继续查找节点的右子树
        if (cmp > 0) {
            node = node.right;
        } else {
            node = node.left;
        }
    }

    // while 循环结束，未查到对应节点
    return null;
}
复制代码

是否包含某元素

是否包含某元素，只需要直接调用上面 查询元素节点，判断返回值是否为 null 即可：

/**
 * 是否包含某元素
 */
public boolean contains(E element) {
    return node(element) != null;
}
复制代码

删除元素

二叉搜索树在删除元素的时候，需要根据元素节点的不同情况区别处理：
1、删除节点的度为 0，即 叶子节点：

 直接删除该节点：该节点父节点对应左（右节点）置为 null。

   1.1当该节点为左节点时：node.parent.left = null

   1.2当该节点为左节点时：node.parent.right = null

   1.3当该节点为根节点时：root = null

image.png

2、删除节点的度为 1 时：

 用子节点代替源节点的位置。子节点 child 是 节点 node 的左（或右）子节点

   2.1当该节点为左子节点时：child.parent = node.parent && node.parent.left = child

   2.2当该节点为右子节点时：child.parent = node.parent && node.parent.right = child

   2.3当该节点为根节点时：root = child && child.parent = null

image.png

3、删除节点的度为 2 时：

 先用后继节点的值覆盖原节点的值；然后删除相应的后继节点。

如果一个节点的度为 2，那么 它的前驱、后继节点的度只可能是 1 和 0 。这样在删除相应的后继节点时，即转为上面 删除节点的度为 0 或 1的情况。

image.png

具体代码：

获取节点的后继节点

/**
 * 获取一个节点的后继结点
 */
private Node<E> successor(Node<E> node) {
    if (node == null) return null;

    // 右子树不为空，前驱结点在右子树中（right.left.left...）
    if (node.right != null) {
        Node<E> p = node.right;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    // 右子树为空，从父节点、祖父节点..中寻找前驱结点
    while (node.parent != null && node == node.parent.right) {
        node = node.parent;
    }
    return node.parent;
}
复制代码

删除元素：

/**
 * 删除元素
 * @param element 删除的元素
 *
 *  删除节点度为 0：直接将节点的 parent 置为 null（注意只有根节点的处理）
 *  删除节点度为 1：用子节点替换其位置（注意根节点的处理）
 *  删除节点度为 2：用后继结点的值替换其值，然后删除后继结点（一个节点的度为2，则其后继节点的度要么为0要么为1，转化为上面两种情况的删除）
 */
public void remove(E element) {
    // 通过元素值查找节点
    Node<E> node = node(element);
    if (node == null) return;
    size--;
    if (node.hasTwoChildren()) { // 度为2的节点
        // 找到后继结点
        Node<E> s = successor(node);
        // 用后继结点的值覆盖读为2的节点的值
        node.element = s.element;
        // 删除后继结点，这里只需要将node指向s，后面代码统一删除 node 即可
        node = s;
    }

    // 删除 node 节点（此时 node 节点的度必然是 0 或者 1，因为node的度未2的情况，上面已经特殊处理了）
    Node<E> replaceNode = node.left != null ? node.left : node.right;
    if (replaceNode != null) { // node 是度为1的节点，使用子节点替代replaceNode替换node的位置
        // 更改 parent
        replaceNode.parent = node.parent;

        if (node.parent == null) { // 删除的是根节点
            root = replaceNode;
        }

        // 更改parent的left、right指向
        if (node == node.parent.left) {
            node.parent.left = replaceNode;

        } else if (node == node.parent.right) {
            node.parent.right = replaceNode;
        }
    } else if(node.parent == null) { // node是叶子节点且根节点
        root = null;
    } else { // node 是叶子节点但不是根节点
        if (node == node.parent.right) {
            node.parent.right = null;
        } else {
            node.parent.left = null;
        }
    }
}
复制代码

至此常见二叉搜索树的相关方法均已实现。

© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
代码人生
喜欢就支持一下吧
点赞0 分享
AI-robot的头像-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
14年前 2.6W+
机器学习之随机森林回归篇（RandomForestRegressor）-一一网
机器学习之随机森林回归篇（RandomForestRegressor）
机器学习之随机森林回归篇（RandomForestRegressor）
4年前 4235
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS-一一网
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
4年前 3920
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞-一一网
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
19年前 3843
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3411
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3162
相关推荐
开源浪潮下程序员的职业规划和成长-一一网
开源浪潮下程序员的职业规划和成长
开源浪潮下程序员的职业规划和成长
4年前 1487
技术实践丨如何解决异步接口请求快慢不均导致的数据错误问题？-一一网
技术实践丨如何解决异步接口请求快慢不均导致的数据错误问题？
技术实践丨如何解决异步接口请求快慢不均导致的数据错误问题？
4年前 1441
mac命令行设置代理，别挡着我起飞-一一网
mac命令行设置代理，别挡着我起飞
mac命令行设置代理，别挡着我起飞
4年前 1349
Linux纯命令行玩转谷歌浏览器：安装、更新、搜索、截图-一一网
Linux纯命令行玩转谷歌浏览器：安装、更新、搜索、截图
Linux纯命令行玩转谷歌浏览器：安装、更新、搜索、截图
4年前 983
WordPress教程 – WordPress新手指南（2021）-一一网
WordPress教程 – WordPress新手指南（2021）
WordPress教程 – WordPress新手指南（2021）
4年前 927
DBLP数据集处理-一一网
DBLP数据集处理
DBLP数据集处理
4年前 854
搜索
开启精彩搜索
世界，您好！-一一网
3.7W+人已阅读
世界，您好！
TOP1
番茄社区无限观看+付费视频破解教程-一一网
番茄社区无限观看+付费视频破解教程
5年前3.2W+人已阅读
TOP2
香蕉视频v3.8.3_VIP会员破解教程-一一网
香蕉视频v3.8.3_VIP会员破解教程
5年前3.1W+人已阅读
TOP3
[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网
密码保护：[桜井宁宁]COS和泉纱雾超可爱写真福利集
5年前2.8W+人已阅读
TOP4
[桜井宁宁] 爆乳奶牛少女cos写真-一一网
密码保护：[桜井宁宁] 爆乳奶牛少女cos写真
5年前2.8W+人已阅读
TOP5
快猫v1.1.7会员破解版_最新快猫vip破解教程大全-一一网
快猫v1.1.7会员破解版_最新快猫vip破解教程大全
5年前2.8W+人已阅读
TOP6
标签云
默认路由黑裙黑群晖麦克风车机鸿蒙系统鸿蒙系统鸿蒙OS鸿蒙驱动软件驱动题库音频剪辑音乐剪辑面板面具静态雷石集群随机阿里云