二分搜索树 二叉查找树 (英语:Binary Search Tree),也称为二分搜索树 ,二叉搜索树 、有序二叉树 (ordered binary tree)或排序二叉树 (sorted binary tree)也可以简写为 BST
,是指一棵空树或者具有下列性质的二叉树 :
若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
任意节点的左、右子树也分别为二叉查找树;
没有键值相等的节点。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度 较低。为O(logN)
。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合,映射等
基本结构 先搭一个基本的架子出来,后面再来慢慢的完善功能
public class BST <E extends Comparable <E >> { private class Node { public E e; public Node left; public Node right; public Node (E e) { this .e=e; left=null ; right=null ; } } private Node root; private int size; public BST () { root=null ; size=0 ; } public int size () { return size; } public boolean isEmpty () { return size==0 ; } public void add (E e) { } public boolean contains (E e) { } }
添加 添加函数,时间复杂度O(logN)
,只要抓住了它的性质就很好写,画个图描述下这个过程
① 首先和root节点8比较,比8小,所以肯定再8的左子树中
② 再和root的左子树根节点5比较,比5大,所以最后肯定插入5的右子树中
③ 再和5节点的右子树根节点6比较,比6大,所以最后插入6的右子树中
④ 右子树为空,直接插入到6的右边
根据上面的流程我们很容易写出代码
public void addLoop (E e) { if (root==null ) { size++; root=new Node(e); return ; } Node temp=root; while (temp!=null ){ if (e.compareTo(temp.e)>0 ) { if (temp.right==null ) { temp.right=new Node(e); size++; return ; } temp=temp.right; }else if (e.compareTo(temp.e)<0 ) { if (temp.left==null ) { temp.left=new Node(e); size++; return ; } temp=temp.left; }else return ; } }
这里既然是树结构,用循环似乎有的显得不够优雅😂
所以我们尝试把这个改成递归
public void add2 (E e) { if (root == null ){ root = new Node(e); size ++; }else add(root, e); } private void add2 (Node node, E e) { if (e.equals(node.e)) return ; if (e.compareTo(node.e) < 0 && node.left == null ){ node.left = new Node(e); size ++; return ; } if (e.compareTo(node.e) > 0 && node.right == null ){ node.right = new Node(e); size ++; return ; } if (e.compareTo(node.e) < 0 ) add(node.left, e); else add(node.right, e); }
这个递归???咋感觉比循环还繁琐🙄
确实,上面这个递归的终止条件太繁琐了,compareTo
一共比较了4次,有很多重复代码,所以我们还得改改😋
我们让这个add
函数有返回值,返回插入后的根节点,这样我们的函数 add(Node node,E e)
定义就变成了 插入元素e
到 以 node
为根节点的BST中,并且返回根节点 ,清楚了递归函数的定义,我们再来写方法就会容易很多
public void add (E e) { root=add(root,e); } private Node add (Node node, E e) { if (node == null ) { size++; return new Node(e); } if (e.compareTo(node.e) < 0 ){ node.left=add(node.left, e); }else if (e.compareTo(node.e) > 0 ) { node.right=add(node.right, e); } return node; }
还是那句话,写递归函数,不要纠结于函数的每一步是如何去进行,如何去得到结果的,从全局出发,只要搞清楚递归函数的定义,按照函数的定义来写代码,最后思考一下边界,最后的代码就一定是正确的!
这个边界的思考,其实也很简单,就比如上面的这个结束条件,我们不用去考虑一步步直到递归终结时是什么情况,我们思考一下极端的边界情况(其实这就是终结的情况),root为null,还没有初始化,BST还是空的,这个时候add元素,其实想都不用想,肯定是直接把这个 e作为根节点返回就ok了,所以很自然的就写出了终止条件
查找 查找相比于上面的添加,会简单很多,可以很容易的写出代码
public boolean contains (E e) { if (e==null ) { return false ; } return contains(e,root); } private boolean contains (E e,Node root) { if (root==null ) { return false ; } if (e.compareTo(root.e)==0 ) { return true ; } return e.compareTo(root.e)<0 ?contains(e,root.left):contains(e,root.right); }
这里我为了简洁写了三目,不熟悉的可以改成if,整体时间复杂度依然是O(logN)
,比线性表的查找会快很多!
遍历 老生常谈的话题,这个在我之前的 LeetCode-二叉树 里面也做过了,这里再翻出来看看,其实重点是想把后序遍历给搞清楚了,之前一直挺迷糊的
前序遍历 递归写法 public void preorderTravelRecur () { preorderTravel(root); } private void preorderTravel (Node root) { if (root==null ) { return ; } System.out.print(root.e+" " ); preorderTravel(root.left); preorderTravel(root.right); }
非递归写法 public void preorderTravelNoRecur () { Stack<Node> stack=new Stack<>(); Node cur=root; while ( cur!=null || !stack.isEmpty()){ while (cur!=null ){ System.out.print(cur.e+" " ); stack.push(cur); cur=cur.left; } cur=stack.pop(); cur=cur.right; } }
注意这里并不是经典的前序遍历方式,是按照 “模板” 来的,首先我们考虑栈里面存的是什么,这里的栈里面存的实际上是 左子树的左边
的集合,这里我不知道咋描述,画个图吧
图中绿色部分就是我所说的左子树的左边的集合 ,整个栈的入栈顺序就是从左往右,从上到下,依次的将这些“左边” 入栈,并且在没有左子树,也就是遍历到叶子节点的时候开始出栈,然后切换成当前出栈的节点
的右子树,将右子树的左子树的左边
重复前面的过程继续入栈出栈,我们要考虑的就是在什么时候访问节点!
细心的同学肯定已经发现了,其实这里进栈顺序和出栈顺序,分别对应的就是这颗树前序遍历和中序遍历!!!所以我们就只需要在进栈和出栈的时候,进行访问节点的操作,就可以完成前序和后序遍历
中序遍历 递归写法 public void inorderTravelRecur () { inorderTravel(root); } private void inorderTravel (Node root) { if (root==null ) { return ; } inorderTravel(root.left); System.out.print(root.e+" " ); inorderTravel(root.right); }
非递归写法 结合上面的分析,我们也可以很容易的得出非递归的中序遍历的写法
public void inorderTravelNoRecur () { Stack<Node> stack=new Stack<>(); Node cur=root; while ( cur!=null || !stack.isEmpty()){ while (cur!=null ){ stack.push(cur); cur=cur.left; } cur=stack.pop(); System.out.print(cur.e+" " ); cur=cur.right; } }
后序遍历 递归写法 public void postorderTravelRecur () { postorderTravel(root); } private void postorderTravel (Node root) { if (root==null ) { return ; } postorderTravel(root.left); postorderTravel(root.right); System.out.print(root.e+" " ); }
非递归写法 这里的非递归写法就不一样了,比前两种要复杂
public void postorderTravelNoRecur () { Stack<Node> stack=new Stack<>(); Node cur=root,lastNode=null ; while (cur!=null || !stack.isEmpty()){ while (cur!=null ){ stack.push(cur); cur=cur.left; } cur=stack.peek(); if (cur.right==null || lastNode==cur.right) { System.out.print(cur.e+" " ); stack.pop(); lastNode=cur; cur=null ; }else { cur=cur.right; } } }
其实不管是什么遍历,对于这个模板来说,栈的轨迹都是一样的 ,只不过访问节点的时机有所不同,蓝色线条代表审查的顺序,红色辅助的代表出栈部分,右边对应的就是遍历过程中栈的变化,和对应结果的变化,对照这个图再分析下就很清楚了。
如果觉得实在是不好理解也可以换用下面的方式
public void postorderTravelNoRecur2 () { Stack<Node> stack=new Stack<>(); stack.push(root); Node lastNode=null ; while (!stack.isEmpty()){ Node cur=stack.peek(); if ( (cur.left==null && cur.right ==null ) || (lastNode!=null &&(cur.left==lastNode || cur.right==lastNode))){ stack.pop(); System.out.print(cur.e+" " ); lastNode=cur; }else { if (cur.right!=null ) { stack.push(cur.right); } if (cur.left!=null ) { stack.push(cur.left); } } } }
这种方式相比上面就好理解多了,左右子树都为空,或者上一个访问的节点是当前节点的子节点,就可以输出该节点了,注意添加的时候是逆序添加的,这样就可以保证先访问左节点,再访问右节点,最后访问根节点
层次遍历 递归写法 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); helper(res, root, 0 ); return res; } private void helper (List<List<Integer>> res, TreeNode root, int depth) { if (root == null ) return ; if (res.size() == depth) res.add(new LinkedList<>()); res.get(depth).add(root.val); helper(res, root.left, depth + 1 ); helper(res, root.right, depth + 1 ); }
非递归写法 经典的BFS
public void levelorderTravel () { Queue<Node> queue=new LinkedList<>(); queue.add(root); while (!queue.isEmpty()){ int count=queue.size(); while (count>0 ){ Node node=queue.poll(); System.out.print(node.e+" " ); if (node.left!=null ) { queue.add(node.left); } if (node.right!=null ) { queue.add(node.right); } count--; } } }
其实关于前中后序的遍历方式,还有很多,我这里主要记录的是模板
的思路,其实还有一种很🐂🍺的做法,模拟系统栈的方式,具体可以参考我之前的 LeetCode二叉树 这里就不多解释了
取整 向下取整(floor) public E floor (E e) { Node node=floor(root,e); return node!=null ?node.e:null ; } public Node floor (Node root,E e) { if (root==null ) { return null ; } int temp=e.compareTo(root.e); if (temp==0 ) { return root; } if (temp<0 ) { return floor(root.left,e); } Node node=floor(root.right,e); return node!=null ?node:root; }
向上取整(ceiling) public E ceiling (E e) { Node node=ceiling(root,e); return node!=null ?node.e:null ; } public Node ceiling (Node root,E e) { if (root==null ) { return null ; } int temp=e.compareTo(root.e); if (temp==0 ) { return root; } if (temp>0 ) { return ceiling(root.right,e); } Node node=ceiling(root.left,e); return node!=null ?node:root; }
这两个函数还是挺有用的,比如这个题 220-存在重复元素-III 通过率只有25%的mid题。。。。
获取第K大 获取第k大(从0开始)的元素,如果左子树节点数小于k
,则第k大的元素肯定在右子树,同时我们可以直接排除size(left)+1
个元素(加上根节点) 。
然后直接在 右子树中继续搜索 getKth(root.right,k-size(left)-1)
,只有当左子树刚好k个元素的时候,根节点就是我们要找的Kth
public E getKth (int k) { if (k>=size || k<0 ) { return null ; } return getKth(root,k).e; } public Node getKth (Node root,int k) { if (root==null ) { return root; } int temp = childSize(root.left); if (temp>k) { return getKth(root.left,k); } if (temp<k) { return getKth(root.right,k-temp-1 ); } return root; }
这里其实我的实现是有问题的,我的时间复杂度是O(NlogN)
!!!!主要是childSize()
时间复杂度是O(N)不是O(1),在《算法4》中这个实现的时间复杂度就是O(1),书上在定义的Node的时候给Node加了一个count属性,用来记录每个节点的子节点数(包括自己),在每次add和delete的时候动态的维护这个count,这样最后求子节点数的操作时间复杂度就是O(1)的了,那个版本的我也实现了一下,但是我没有在这篇文章中这样写(主要是懒得改),而且这也不是重点,感兴趣可以去看看 BSTWithCount 主要就是要注意操作count的时机
这里既然没有count数组,那么其实就不应该这样求,应该直接中序遍历,求第K大,时间复杂度O(N)
Rank() 其实是上面的逆过程,如果根节点等于key,那么直接返回左子树的键总数;如果key小于根节点,就继续去左子树中递归找,如果大于根节点,返回size(left)+1
加上它在右子树中的rank()
public int getRank (E e) { return getRank(root,e); } public int getRank (Node root,E e) { if (e.compareTo(root.e)<0 ) { return getRank(root.left,e); } if (e.compareTo(root.e)>0 ) { return getRank(root.right,e)+childSize(root.left)+1 ; } return childSize(root.left); }
Max&Min 没啥好说的
public E getMax () { return getMax(root).e; } public Node getMax (Node root) { if (root.right==null ) { return root; } return getMax(root.right); } public E getMin () { return getMin(root).e; } public Node getMin (Node root) { if (root.left==null ) { return root; } return getMin(root.left); }
删除 删除应该来说是BST中里面比较复杂的一个操作了,我们先从简单的开始
删除最值 public void deleteMin () { root=deleteMin(root); } private Node deleteMin (Node node) { if (node.left==null ) { return node.right; } node.left=deleteMin(node.left); return node; } public void deleteMax () { root=deleteMax(root); } private Node deleteMax (Node node) { if (node.right==null ) { return node.left; } node.right=deleteMax(node.right); return node; }
递归函数定义为删除node为头节点的树中的最小值,并返回头节点 ,删除最小值实际上就是删除二叉树最左边的节点,所以我们递归的删除node.left就ok,当node.left为空的时候返回node.right,这样前面节点的left就接在了node.right上,就达到了删除的作用
删除任意值 public void delete (E e) { root=delete(root,e); } private Node delete (Node node,E e) { if (node==null ) { return null ; } if (e.compareTo(node.e)>0 ) { node.right=delete(node.right,e); }else if (e.compareTo(node.e)<0 ) { node.left=delete(node.left,e); }else { if (node.left==null ) { return node.right; } if (node.right==null ) { return node.left; } Node delNode=node; node=getMin(node.right); node.right=deleteMin(delNode.right); node.left=delNode.left; } return node; }
这里文字的描述比较无力,画个图就清晰明白了,核心的思想就是利用右子树中的最小值填补待删除节点
当然这里其实也是有坑的,主要就是连最后两句
node.right=deleteMin(delNode.right); node.left=delNode.left;
这里的两句话是不能交换的,如果我们交换了两句话的位置,那么我们下一步删除最小值就会出现问题,我们希望的是删除右子树中最小的node节点,结果你先把待删除节点的left接到了node的左边,这样的话node就不再是delNode.right中的最小值,最后结果可能就会成这个样子,成了一个闭环!!!
所以最后的结果肯定是不对的,其实这一点书上并没有提到,我也是在做这道题删除节点 的时候写反了,才发现这个问题,感兴趣可以去试试
其实这样的删除时一种很随机的做法,虽然能正确的删除元素,但是并没有考虑树的对称性,关于树的对称性,我们后面再来研究
代码地址 BST.java
BSTTest.java
BSTWithCount.java