专栏首页我是攻城师什么是二叉搜索树

什么是二叉搜索树

二叉搜索树是一种综合效率比较好的一种数据结构,搜索、插入、删除的复杂度等于树高, 平均空间复杂度为O(n),时间复杂度为O(log n),最坏时间复杂度为O(n),(当插入的数列有序,导致二叉树退化为线性表),故一些其他的树,在二叉搜索树基础上进行改良的平衡树,如AVL树、红黑树等,可以使得树的高度总是得到平衡,从而使得最坏的情况下,时间复杂度也能达到O(log n)。

在没有二叉搜索树这种结构出现的时候,我们如果想对一个有序的序列,进行快速的检索,使用数组是可以做到的,但数组的弊端在于,如果我想向这个序列里面插入或者删除一个新的元素,使用数组就可能捉襟见肘了,而链表则对插入,删除非常友好,但检索性能比较低,故才出现了二叉搜索树这种结够,使得查询和更新能够达到不错的一个O(log n)性能权衡。

二叉搜索树的特点

(1)每个节点包含一个key,也称data的数据域

(2)左子树不为空的情况下,左子树的每个节点值都小于根节点的值,即:L < P

(3)右子树不为空的情况下,右子树的每个节点值都大于根节点的值,即:P < R

(4)节点的值不允许出现重复

(5)任意节点的左,右子树,均符合上面的规则

二叉搜索树的插入

二叉搜索树的插入与二叉树的搜索非常类似,当一个新的值要插入的时候,首先与根节点进行比较,如果大于根节点则进入右子树进行递归找位置,如果小于根节点则进入左子树进行递归找位置,按照二叉树的性质,新插入的节点最终会落在某在一个位置上,注意如果该值已经存在那么则不做任何处理,因为二叉树不允许重复的值插入。 下图在插入节点7之后的变化:

二叉搜索树的搜索

二叉搜索树的搜索与插入流程类型,都是从root节点开始,然后锁定要查询节点所在的子树,如果大于根节点则在右边搜索,否则则在左边,然后递归遍历,直到找到结果,如果没有找到,则返回false即可。

二叉搜索树的删除

删除相对于插入和搜索要复杂一点,删除一个节点要考虑如下几种情况:

(1)删除的节点不存在

(2)删除的节点是叶子节点

(3)删除的节点有一个孩子节点

(4)删除的节点包含两个孩子节点

第一种情况,不做处理,第二种和第三种情况,其实与链表处理的策略是一样的,如果是叶子节点直接将其赋值成null即可,如果包含一个孩子节点,则直接取孩子节点覆盖要删除的节点即可,如下:

第四种情况,如果该节点有两个孩子节点,这种情况就复杂了点,因为直接删除该节点会导致树结构遭到破坏,所以不能直接删除,要先找到该节点在左子树里面的最大节点或者右子树里面的最小节点,然后将最大节点的值替换到要删除的节点,之后在左子树里面再删除该节点的值即可,这样就完成了拥有两个节点删除的情况,如下图示:

下面我们看下代码实现:

首先定义一个二叉树结构:

public class BST< T extends Comparable<T>> {
    public Node<T> root;
       static class Node<T>{        public T data;        public Node<T> left;        public Node<T> right;
        public Node(T data, Node<T> left, Node<T> right) {            this.data = data;            this.left = left;            this.right = right;        }
       @Override       public String toString() {           return "Node{" +                   "data=" + data +                   '}';       }   }


    }

然后分别定义插入方法:

  public void insert(T data){        root=insert(root, data); //递归插入    }
    public Node<T> insert(Node<T> p, T data){
        if(p==null){            return new Node<>(data,null,null);        }
        if(compare(p.data,data)==0){            return p;        }
        if(compare(data,p.data)<0){            p.left=insert(p.left,data);        }else {            p.right=insert(p.right,data);        }        return p;    }

搜索方法:

     public boolean search(T data){      return   search(root,data);    }
    public boolean search(Node<T> node,T data){        if(node==null){            return false;        }        if(compare(node.data,data)==0){            return true;        }else if(compare(data,node.data)<0) {            return search(node.left,data);        }else{            return search(node.right,data);        }
    }

最后是删除的方法:

   public void delete(T data){        root=delete(root,data);    }
    public Node<T> delete(Node<T> node,T data){
        if(node==null){            throw new RuntimeException("删除的节点不存在");        }else if(compare(data,node.data)<0){            node.left=delete(node.left,data);        }else if(compare(data,node.data)>0){            node.right=delete(node.right,data);        }else{//叶子节点,或者只拥有一个孩子节点的处理逻辑是一样的            if(node.left==null){                return node.right;            }else if(node.right==null){                return node.left;            }else{                //到这一步说明删除的节点拥有2个孩子节点                //找到剩下左子树里面最大的节点,或者找到右子树里面最小的节点,这里使用的是前者                //使用最大值覆盖当前要被删除的节点的值                node.data=retrieveData(node.left);                //最后删除,在剩下左子树里面刚才被替换到最大值的节点                node.left=delete(node.left,node.data);            }
        }
    return node;    }

    private T retrieveData(Node<T> p)    {        while (p.right != null) p = p.right;
        return p.data;    }

二叉搜索树的中序遍历,即可得到一个有序的数列,我们看下中序遍历的递归实现:

   private void inOrder(Node<T> node){        if(node==null) return;        inOrder(node.left);        System.out.println(node);        inOrder(node.right);    }

代码比较简单,然后我们再看下不用递归,使用迭代方式的中序遍历方式:

    public void inOrderiterator(Node<Integer> root){
        Stack<Node<Integer>> stack=new Stack<>();        List<Integer> list=new ArrayList<>();        while (root!=null||!stack.isEmpty()){            if(root!=null) {                stack.push(root);                root = root.left;            }else{                root=stack.pop();                list.add(root.data);                root=root.right;            }        }
        System.out.println(list);
    }

这里借助了栈这个数据结构,非常简单的就实现了迭代版本的中序遍历,关于前序和后序版本这里就不再给出例子了,感兴趣的朋友可以自己研究下。

二叉搜索树是一个非常高效的数据结构,其综合效率约为O(logn),但插入数列为有序数列时,插入性能会退化为O(n),这是二叉搜索树的一个弊端,在改良后加入了具有平衡的功能时候,可以使得树的高度保持均衡,就演变成了AVL或者红黑树,这个时候即使是有序数列,插入性能也可保持在O(logn),这也是为什么红黑树高效的原因,因为其在插入时候能够自我调整树的高度,不会在极端情况下发生退化倾斜向一边的场景。

本文分享自微信公众号 - 我是攻城师(woshigcs),作者:攻城师在路上

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 理解Java里面并发工具框架AbstractQueuedSynchronizer的底层实现

    前面的文章我们讨论了Java并发工具框架基类AbstractQueuedSynchronizer的核心功能和设计思想,本篇在结合源码来分析下相关的内容

    我是攻城师
  • 什么是2-3树

    前面的文章我们已经学习了二叉搜索树和平衡二叉搜索树AVL树,今天我们再来了解一种新的平衡树2–3树,2–3树由约翰·霍普克洛夫特于1970年发明,在计算机科学中...

    我是攻城师
  • 数据结构之(树)

    在计算机科学中,树(英语:tree)是一种非线性的抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0...

    我是攻城师
  • 数据结构与算法-二叉树(二)

    二叉查找树是一种特殊的二叉树,它支持动态的数据集合的快速插入、删除和查找操作。二叉查找树的一般结构如下图所示:

    用户3470542
  • Java并发之AQS源码分析(一)

    AQS 全称是 AbstractQueuedSynchronizer,顾名思义,是一个用来构建锁和同步器的框架,它底层用了 CAS 技术来保证操作的原子性,同时...

    JAVA葵花宝典
  • Java并发之AQS源码分析(一)

    AQS 全称是 AbstractQueuedSynchronizer,顾名思义,是一个用来构建锁和同步器的框架,它底层用了 CAS 技术来保证操作的原子性,同时...

    张乘辉
  • TreeView中节点勾选设置

    本文转载:http://www.cnblogs.com/luxiaoxun/p/3288003.html

    跟着阿笨一起玩NET
  • 平衡二叉树(AVL树)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    于小勇
  • 图神经网络(GNN)结构化数据分析

    【导读】Graph Neural Network(GNN)由于具有分析图结构数据的能力而受到了广泛的关注。本文对Graph Neural Network进行了简...

    代码医生工作室
  • 算法篇:链表之删除链表中重复节点

    核心点在于如何找到重复节点,有序链表的话,只要下一个节点与当前节点数值一样就是重复节点,直接将当前节点指向下一个节点的下一个节点即可。

    灰子学技术

扫码关注云+社区

领取腾讯云代金券