二分搜索树

二叉查找树(英语:Binary Search Tree),也称为二分搜索树二叉搜索树有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree)也可以简写为 BST,是指一棵空树或者具有下列性质的二叉树

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(logN)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合,映射等

基本结构

先搭一个基本的架子出来,后面再来慢慢的完善功能

public class BST<E extends Comparable<E>>{
//TreeNode
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),只要抓住了它的性质就很好写,画个图描述下这个过程

mark

① 首先和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);
}

// 向以node为根的二分搜索树中插入元素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 //e.compareTo(node.e) > 0
add(node.right, e);
}

这个递归???咋感觉比循环还繁琐🙄

确实,上面这个递归的终止条件太繁琐了,compareTo一共比较了4次,有很多重复代码,所以我们还得改改😋

我们让这个add函数有返回值,返回插入后的根节点,这样我们的函数 add(Node node,E e) 定义就变成了 插入元素e到 以 node 为根节点的BST中,并且返回根节点 ,清楚了递归函数的定义,我们再来写方法就会容易很多

public void add(E e){
root=add(root,e);
}

//插入元素`e`到 以 `node` 为根节点的BST中,并且返回根节点
private Node add(Node node, E e){
if (node == null) {
size++;
return new Node(e);
}
if(e.compareTo(node.e) < 0){
//插入左子树中,并返回根节点,然后接在node.left
node.left=add(node.left, e);
}else if (e.compareTo(node.e) > 0) { //注意不要写else,前面没有对相等的元素做判断
//插入右子树中,并返回根节点,然后接在node.right
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;
}
}

注意这里并不是经典的前序遍历方式,是按照 “模板” 来的,首先我们考虑栈里面存的是什么,这里的栈里面存的实际上是 左子树的左边 的集合,这里我不知道咋描述,画个图吧

mark

图中绿色部分就是我所说的左子树的左边的集合,整个栈的入栈顺序就是从左往右,从上到下,依次的将这些“左边” 入栈,并且在没有左子树,也就是遍历到叶子节点的时候开始出栈,然后切换成当前出栈的节点的右子树,将右子树的左子树的左边重复前面的过程继续入栈出栈,我们要考虑的就是在什么时候访问节点!

细心的同学肯定已经发现了,其实这里进栈顺序和出栈顺序,分别对应的就是这颗树前序遍历和中序遍历!!!所以我们就只需要在进栈和出栈的时候,进行访问节点的操作,就可以完成前序和后序遍历

中序遍历

递归写法

//中序遍历,递归
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();//查看栈顶元素
//如果右子树为空或者右节点已经访问过,则当前节点出栈,并记录lastNode
if (cur.right==null || lastNode==cur.right) {
System.out.print(cur.e+" ");
stack.pop();
lastNode=cur;
//为了下一次能直接查看栈顶元素
//cur的使命其实已经结束了,cur和它的孩子都已经访问了,下一次直接从栈顶取,不然就死循环了
cur=null;
}else{
cur=cur.right;
}
}
}

mark

其实不管是什么遍历,对于这个模板来说,栈的轨迹都是一样的,只不过访问节点的时机有所不同,蓝色线条代表审查的顺序,红色辅助的代表出栈部分,右边对应的就是遍历过程中栈的变化,和对应结果的变化,对照这个图再分析下就很清楚了。

如果觉得实在是不好理解也可以换用下面的方式

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) { //root.e > e,求小于e的值,一定在左边
return floor(root.left,e);
}
//tmep>0 e>root.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) { //root.e<e,求的是最后大于root.e的元素,一定在右边
return ceiling(root.right,e);
}
//tmep<0 e<root.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的时机

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) { //e<root.e
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);
}
//删除node为头节点的树中的最小值,并返回头节点
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);
}

//删除以node为首的BST中,值为e的节点并且返回根节点
private Node delete(Node node,E e){
if (node==null) {
return null;
}
if (e.compareTo(node.e)>0) { //e>root.e
node.right=delete(node.right,e);
}else if (e.compareTo(node.e)<0) {
node.left=delete(node.left,e);
}else{ //e==root.e
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;
}

这里文字的描述比较无力,画个图就清晰明白了,核心的思想就是利用右子树中的最小值填补待删除节点

mark

当然这里其实也是有坑的,主要就是连最后两句

//删除对应的右子树的最小值,然后连接起来
node.right=deleteMin(delNode.right);
node.left=delNode.left;

这里的两句话是不能交换的,如果我们交换了两句话的位置,那么我们下一步删除最小值就会出现问题,我们希望的是删除右子树中最小的node节点,结果你先把待删除节点的left接到了node的左边,这样的话node就不再是delNode.right中的最小值,最后结果可能就会成这个样子,成了一个闭环!!!

mark

所以最后的结果肯定是不对的,其实这一点书上并没有提到,我也是在做这道题删除节点 的时候写反了,才发现这个问题,感兴趣可以去试试

其实这样的删除时一种很随机的做法,虽然能正确的删除元素,但是并没有考虑树的对称性,关于树的对称性,我们后面再来研究

代码地址

BST.java

BSTTest.java

BSTWithCount.java