美文网首页
二叉排序树

二叉排序树

作者: huyongming | 来源:发表于2020-09-10 16:34 被阅读0次

1、二叉排序树定义

二叉排序树也叫二叉搜索树、二叉查找树。二叉排序树树是一颗它的左子树上的节点都小于根节点,右子树上的节点都大于根节点的二叉树,且其左右子树也是二叉排序树。

实例


二叉树实例

2、二叉排序树的创建

当要向二叉排序树中插入元素的时候,从根节点开始查找,先将根节点作为当前节点,如果要插入的值比当前节点的值小,则判断当前节点的左孩子是不是空,如果是空则将要插入的值作为当前节点的左孩子,不是空则将当前节点的左孩子作为当前节点继续查找;当要插入的值比当前节点的值大时,判断当前节点的右孩子是不是空,如果是空则将要插入的值作为当前节点的右孩子,不是空则把当前节点的右孩子作为当前节点继续查找
节点定义

public static class Node {
    public int value;
    public Node left;
    public Node right;
}

递归实现

private static Node create(Node root, int value) {
    if (root == null) {
        Node node = new Node();
        node.value = value;
        return node;
    }
    if (value < root.value) {
        root.left = create(root.left, value);
    } else if (value > root.value) {
        root.right = create(root.right, value);
    }
    return root;
}

非递归实现

private static Node create2(Node root, int value) {
    Node node = new Node();
    node.value = value;

    if (root == null) {
        return node;
    }

    Node temp = root;
    while (true) {
        if (value < temp.value) {
            if (temp.left == null) {
                temp.left = node;
                return root;
            } else {
                temp = temp.left;
            }
        } else if (value > temp.value) {
            if (temp.right == null) {
                temp.right = node;
                return root;
            } else {
                temp = temp.right;
            }
        } else {
            return root;
        }
    }
}

3、二叉排序树的遍历

使用中序遍历,遍历出来的结构刚好是一个升序排列的数列
递归写法

private static void traverseMide(StringBuilder builder, Node root) {
    if (root == null) {
        return;
    }
    traverseMide(builder, root.left);//遍历左孩子
    builder.append(root.value + ",");//打印更节点
    traverseMide(builder, root.right);//遍历有孩子
}

非递归写法

 private static void traverseMide2(StringBuilder builder, Node root) {
        Stack<Node> stack = new Stack<>();//缓存要回溯的节点
        Node temp = root;
        while (temp != null || !stack.isEmpty()) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
            if (!stack.isEmpty()) {
                temp = stack.pop();
                builder.append(temp.value + ",");//打印节点
                if (temp.right != null) {
                    temp = temp.right;
                } else {
                    temp = null;
                }
            }
        }
    }

4、二叉排序树的搜索

搜索二叉排序树的时候,从根节点开始搜索,将根节点作为当前节点,如果当前节点的值和搜索的值相等,则搜索结束,返回成功;如果当前节点的值小于搜索值,则判断当前节点的左孩子是不是空,如果是空,则搜索的值不在树中,搜索结束返回失败,如果不为空,则将当前节点的左孩子作为当前节点,继续搜索;如果当前节点的值大于搜索值,则判断当前节点的右子树是不是空,如果是空,则搜索的值不在树中,搜索结束,返回失败,如果不为空,则将当前节点的右孩子作为当前节点,继续搜索。

private static boolean search(Node root, int value) {
    if (root == null) {
        return false;
    }
    if (root.value == value) {
        return true;
    } else if (value < root.value) {
        return search(root.left, value);
    } else {
        return search(root.right, value);
    }
}

5、二叉树的删除

二叉排序树的删除分为如下三种基本的情况

  1. 要删除的节点就是叶子节点
  2. 要删除的节点只有一个孩子
  3. 要删除的节点有两个孩子

5.1 要删除的节点就是叶子节点

直接删除节点即可


删除节点3000
节点删除之后

5.2 要删除的节点只有一个孩子

将要删除的节点的孩子节点替换当前节点即可


删除节点2500
节点删除之后

5.3 要删除的节点有两个孩子

在要删除的节点的右子树中找一个最小的值来替换掉要删除的节点,同时将这个最小的节点删除掉(也可以从左子树中找一个最大的节点)
具体情况

  1. 右子树没有孩子


    删除节点2000,右子树没有孩子,右子树直接替代节点2000
    节点2000被替代之后
  1. 右子树只有右孩子


    删除节点2000,右孩子只有右节点,右孩子直接替代节点2000
    节点2000被替代之后
  2. 右子树有左孩子


    删减节点2000,右子树有左孩子,从右子树中找到最左的节点替换节点2000
    节点2000被替代之后

算法实现:

  1. 先找出右子树中的值最小的节点;
  2. 用最小节点的值替代掉要删除的节点的地址;
  3. 然后子从右子树中删除这个最小节点
    删除的源码
private static Node delete(Node root, int value) {
    if (root == null) {
        return null;
    }
    if (value < root.value) {
        root.left = delete(root.left, value);
    } else if (value > root.value) {
        root.right = delete(root.right, value);
    } else {
        if (root.left == null && root.right == null) {//叶子节点
            root = null;
        } else if (root.left == null || root.right == null) {//一个节点
            if (root.left == null) {
                root = root.right;
            } else if (root.right == null) {
                root = root.left;
            }
        } else {//有两个节点:
            //找到右边最小的节点,替换要删除的节点,然后删除最小的节点
                Node temp = root.right;
                while (temp.left != null) {
                    temp = temp.left;
                }
                root.value = temp.value;
                root.right = delete(root.right, temp.value);
        }
    }
    return root;
}

6、时间复杂度

二叉排序树的查找时间与二叉树的高度有关,高度越高需要的查找时间就越多。
二叉排序树的高度有两种极端的情况,一种是完全二叉树,一种是每层只有一个节点的情况,变成了一个链表。


完全二叉树
链表

当是完全二叉树的时候:这种情况下的时间复杂为O(log2N)
当每一层只有一个节点时,也就是链表的时候:这种情况下的时间复杂度为O(n)
所以二叉排序树的搜索时间复杂度在:O(log2N)O(n)之间。它的插入,删除复杂度也在O(log2N)O(n)之间

相关文章

  • 详解Java二叉排序树

    姓名: 李小娜 [嵌牛导读] :这篇文章主要介绍了Java二叉排序树,包括二叉排序树的定义、二叉排序树的性质、二叉...

  • Java数据结构:二叉排序树(BST)

    一、基本介绍 二叉排序树 BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一...

  • 2018-06-19/20 机试准备09

    数据结构 四、二叉排序树 对二叉排序树进行中序遍历 结果必然是一个递增序列 所以通过建立二叉排序树可以对无序序列进...

  • 二叉搜索树(BST)

    构造一棵二叉排序树的目的,其实并不是为了排序,而是为了提高查找的效率。 那么什么是二叉排序树呢?二叉排序树具有以下...

  • Binary Search Tree

    如果二叉排序树是平衡的,则n个节点的二叉排序树的高度为 ,其查找效率为 ,近似于折半查找。如果二叉排序树完全不平衡...

  • 红黑树

    二叉排序树 非空二叉排序树具有如下特点: 二叉排序树中,如果其根结点有左子树,那么左子树上所有结点的值都小于根结点...

  • 数据结构之二叉排序树

    二叉排序数 1.二叉排序树介绍 二叉排序树:BST: (Binary Sort(Search) Tree), 对于...

  • 数据结构学习第四弹 二叉排序树

    二叉排序树又称为二叉搜索树或二叉查找树,这是一种插入、删除和检索记录效率都很高的树结构 二叉排序树概念 二叉排序树...

  • 数据结构与算法——基础篇(五)

    二叉排序树——BST——Binary Sort(Search) Tree 二叉排序树的出现是为了解决数组的查询快,...

  • 看图说话之平衡二叉排序树

    本文在看图说话之二叉排序树的基础上介绍了平衡二叉排序树,结构性较好的二叉排序树其插入和删除操作的时间复杂度接近Lo...

网友评论

      本文标题:二叉排序树

      本文链接:https://www.haomeiwen.com/subject/fzypektx.html