搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 炼数笔记 > 玩转数据结构5之二分搜索树(学习笔记)

玩转数据结构5之二分搜索树(学习笔记)

炼数笔记 2020-07-01

上文深入研究了链表及其具有的一种固有属性--递归,并递归实现了链表元素的删除操作。本节课学习另外一种高效的数据结构--树。

1. 二分搜索树

树是一种天然的组织结构,在实际生活中非常常见,比如:

  • 文件夹的存储结构
  • 公司的人员组织架构

很多数据使用树结构存储以后,出奇的高效。树结构主要包括以下几种:

  • 二分搜索树
  • 平衡二叉树
  • 红黑树
  • 线段树等等
  
    
    
  
// 二叉树的节点class Node{ E e; Node left; Node right;}

二叉树具有很强的辨识性,特点明显:

  • 有且只有一个根节点
  • 每个节点最多有两个孩子
  • 每个节点最多有一个父亲
玩转数据结构5之二分搜索树(学习笔记) 另外,同链表一样,二叉树具有天然的递归属性:
  • 每个节点的左子树也是二叉树
  • 每个节点的右子树也是二叉树 玩转数据结构5之二分搜索树(学习笔记)

需要注意的是,二叉树不一定是满的玩转数据结构5之二分搜索树(学习笔记)二分搜索树是二叉树的一种,在二分搜索树中:

  • 每个节点的值大于其左子树的所有节点值
  • 每个节点的值小于其右子树的所有节点值
  • 每个子树也是一个二分搜索树

玩转数据结构5之二分搜索树(学习笔记)注意,二分搜索树存储的元素必须具有可比较性。基于这些内容,我们可以给出二分搜索树的一个基本结构:

  
    
    
  
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 boolean isEmpty() { return size == 0; } public int getSize() { return size; }}

注意,泛型声明时必须具有可比较性。

2. 增加、查找和遍历

2.1 添加元素

向二分搜索树中添加元素,需要保持二分搜索树的顺序性,可以采用递归写法和非递归写法。递归写法相对较简单,只要处理好边界点和添加逻辑即可:

  • 当根节点为空时,直接创建新节点,添加到根节点中

  • 当添加元素大于根结点元素时,向以根结点的右子树为根节点的二分搜索树中添加

  • 当添加元素小于根节点元素时,向以根结点的左子树为根节点的二分搜索树中添加

// 公有方法添加元素public void addElement(E e) { // 调用私有添加方法向根结点所在树添加元素 root = addElement(root, e);}// 私有方法,向以node结点为根的二分搜索树中添加元素private Node addElement(Node node,E e) { if(node==null) { node = new Node(e); size++; return node; } if(e.compareTo(node.e)<0) { // 递归实现,添加元素小于node,向node的左子树中添加元素 node.left = addElement(node.left,e); } if(e.compareTo(node.e)>0) { // 递归实现,添加元素大于node,向node的右子树中添加元素 node.right = addElement(node.right,e); } return node;}

添加元素的非递归写法,与之前链表的写法相似,从实用性角度来看,非递归写法并不常用,这里不做研究。

2.2 查找元素

二分搜索树中不存在索引的概念,因此查找操作是指查询二分搜索树中是否包含某个元素。递归实现起来,也是非常简单的:

  • 如果节点元素等于要查找的元素,则直接返回true

  • 如果节点元素为空,返回false

  • 如果节点元素大于要查找的元素,到节点的左子树中继续查找

  • 如果节点元素小于要查找的元素,到节点的右子树中继续查找

// 查看二分搜索树中是否包含元素epublic boolean contains(E e){ // 调用私有方法 return contains(root,e);}
// 查看以node为根的二分搜索树中是否包含元素eprivate boolean contains(Node node,E e) { if(node==null) { return false; } if(e.equals(node.e)) return true; if(e.compareTo(node.e)<0) { return contains(node.left,e); } else return contains(node.right,e);}
2.3 深度优先遍历

在二分搜索树中,一个非常重要的操作就是遍历。遍历就是把所有节点都访问一遍。在二分搜索树中,有三种遍历方法,以访问根结点是在访问左子树和右子树的之前、之后和之间来进行划分:

  • 前序遍历:根节点在访问节点的左子树和右子树之前访问:

function traverse(node): if(node==null) return;
访问该节点 traverse(node.left) traverse(node.right)

前序遍历是最自然,也是最常用的一种遍历方式:

// 前序遍历二分搜索树public void preOrder() { preOrder(root);}
// 前序遍历以node为根的二分搜索树private void preOrder(Node node) { if(node==null) { return; } System.out.println(node.e); preOrder(node.left); preOrder(node.right);}
  • 中序遍历:根节点在访问节点的左子树和右子树之间进行访问:

function traverse(node): if(node==null) return;
traverse(node.left) 访问该节点 traverse(node.right)

结合二分搜索树的结构特性,可以发现,中序遍历可以将树中的元素从小到大排列一遍,因此二分搜索树也是一种有序的数据结构。

// 中序遍历public void inOrder() { inOrder(root);}
private void inOrder(Node node) { if(node==null) { return; } inOrder(node.left); System.out.println(node.e); inOrder(node.right);}
  • 后序遍历:根节点在访问节点的左子树和右子树之后进行访问

function traverse(node): if(node==null) return;
traverse(node.left) traverse(node.right) 访问该节点

代码实现:

// 后序遍历public void postOrder() { postOrder(root);}private void postOrder(Node node) { if(node==null) { return; } postOrder(node.left); postOrder(node.right); System.out.println(node.e);}

接下来,借助之前介绍的关于栈的知识,研究二分搜索树前序遍历的非递归实现。前序遍历的过程,可以用一个压栈和弹栈的流程表示出来:

  • 对已在栈内的根结点,访问到该节点时,将该节点弹栈,然后立刻将其右节点和左节点依次压入栈内

  • 当某个子树为空时,不进行压栈操作

  • 当栈内元素为空时,遍历结束

// 前序遍历,非递归写法public void preOderNR() { if(root==null) { return; } Stack<Node> stack = new Stack(); stack.push(root); while(!stack.isEmpty()) { Node node = stack.pop(); System.out.println(node.e); if(node.right!=null) { stack.push(node.right);  } if(node.left!=null) { stack.push(node.left);  } }}
2.4 层序遍历

前面介绍的几种遍历方法均属于深度优先遍历,本节介绍一种层序遍历方法,即逐层访问树的元素,这种遍历方式也叫做广度优先遍历。这里借助队列先进先出的结构特性来实现二分搜索树的层序遍历。

  • 每次访问到一个节点时(出队),将该节点的左孩子和右孩子依次入队

  • 当某个孩子为空时,不进行入队操作

  • 当队列内元素为空时,遍历结束

// 层序遍历,广度优先遍历public void levelOrder() { if(root==null) { return; } Queue<Node> queue = new LinkedList<>(); // 根节点入队 queue.add(root);  // 队列不为空时 while(!queue.isEmpty()) { // 队首元素出队,记为cur节点 Node cur = queue.remove();  System.out.println(cur.e); // cur节点的左孩子不为空时,入队 if(cur.left!=null) { queue.add(cur.left); } // cur节点的右孩子不为空时,入队 if(cur.right!=null) { queue.add(cur.right); } }}

树的层序优先遍历通常能够更快地找到问题的解,常用于在路径规划中寻找最短路径。

3. 二分搜索树删除节点

3.1 删除最大值和最小值

本节讨论如何从二分搜索树中删除元素,先从最简单的情况开始:删除二分搜索树的最大值和最小值。基于二分搜索树的结构特性,最大值位于二分搜索树的最右边,最小值位于二分搜索树的最左边。因此,删除最大值和最小值可以很容易使用递归方法来实现:

  • 删除最小值

// 删除二分搜索树中的最小值,返回删除后的根结点public Node removeMin(){ // 如果根节点为空,抛异常(可选操作) if(root==null) { throw new IllegalArgumentException("Remove failed. The tree is empty."); } // 删除根节点所在树的最小值,并返回删除后的根结点 root = removeMin(root); return root;}
// 从以node为根的二分搜索树中删除最小值,返回删除后的根结点private Node removeMin(Node node) { // 如果节点左孩子为空,说明该节点即为最小值,直接删除 if(node.left==null) { node = node.right; size--; } // 如果节点左孩子不为空,递归从以左孩子为根结点的二分搜索树中删除最小值,并返回删除后的根节点 else { node.left = removeMin(node.left); } return node;}
  • 删除最大值(与删除最小值类似)

// 删除二分搜索树中的最大值,返回删除后的根结点public Node removeMax(){ if(root==null) throw new IllegalArgumentException("Remove failed. The tree is empty."); else { root = removeMax(root); return root; }}
// 从以node为根的二分搜索树中删除最大值,返回删除后的根结点private Node removeMax(Node node) { if(node.right==null) { node = node.left; size--; } else { node.right =removeMax(node.right); } return node;}
3.2 删除最大值和最小值的第二种方法

上述删除操作,没能返回删除的元素值,不实用。这里介绍第二种删除方法,即先找到二分搜索树中的最大值和最小值所在节点,然后删除该节点。

  • 查找最小值

// 找到二分搜索树中的最小值public E minimum(){ if(size==0) throw new IllegalArgumentException("The tree is empty."); else { // 调用私有最小值函数 // 找到以root为根节点的二分搜索树中的最小值所在节点 Node minNode = minimum(root); return minNode.e;  }}
// 找到以node为结点的二分搜索树的最小值所在结点private Node minimum(Node node) { // 如果node节点的左孩子为空,表明node即为最小值所在节点 if(node.left==null) { return node; } else // node节点的左孩子不为空,则递归查找node节点左子树中的最小值所在节点 return minimum(node.left);}
  • 移除最小值的第二种方法(实际上不能称之为第二种方法,只加入了查找最小值操作)

// 移除最小值所在节点,返回移除的元素public E removeMin2(){ if(size==0) { throw new IllegalArgumentException("The tree is empty."); } // 找到以root为根节点的二分搜索树的最小值所在节点 Node res = minimum(root); // 调用私有移除方法 // 移除以root结点为根的二分搜索树的最小值所在节点,返回移除后的根结点 root = removeMin2(root); return res.e;} // 移除以node结点为根的二分搜索树的最小值,返回移除后的根结点public Node removeMin2(Node node) { if(node.left==null) { node = node.right; size--; } else node.left = removeMin2(node.left); return node;}
  • 查找最大值

// 找到二分搜索树中的最大值public E maxmum(){ if(size==0) throw new IllegalArgumentException("The tree is empty."); else { // 调用私有最大值函数 // 找到以root为根节点的二分搜索树中的最大值所在节点 Node maxNode = maxmum(root); return maxNode.e;  }} // 找到以node 为结点的二分搜索树的最大值所在结点private Node maxmum(Node node) { // 如果node节点的右孩子为空,表明node即为最大值所在节点 if(node.right==null) { return node; } else // node节点的右孩子不为空,则递归查找node节点右子树中的最大值所在节点 return maxmum(node.right);}
  • 删除最大值的“第二种方法”

// 移除最大值的第二种实现,返回移除的元素public E removeMax2() { if(size==0) throw new IllegalArgumentException("The tree is empty."); Node delNode = maxmum(root); root = removeMax2(root); return delNode.e;} // 移除以node为根的二分搜索树的最大值,返回移除后的根结点private Node removeMax2(Node node) { if(node.right==null) { node = node.left; size--; } else { node.right = removeMax2(node.right); } return node;}
3.3 移除二分搜索树中的任意元素

前面介绍的移除最大值和最小值都比较简单,困难的是移除二分搜索树中的任意元素。实际上,可以分为三种情况来处理:

  • 删除只有左孩子的节点

对只有左孩子的节点,直接返回该节点的左子树即可玩转数据结构5之二分搜索树(学习笔记)

  • 删除只有右孩子的节点

对只有右孩子的节点,直接返回该节点的右子树即可玩转数据结构5之二分搜索树(学习笔记)

  • 删除左右都有孩子的节点

对左右都有孩子的节点,最主要的问题是,删除该节点后,使用哪一个节点来替代该节点的位置,且能保证二分搜索树的结构不变。目前,广泛采用的是Hibbard在1962年提出的Hibbard删除法:

1)首先从待删除节点delNode的右子树中,找到最小值所在节点sNode ( sNode = minimum(delNode.right) );玩转数据结构5之二分搜索树(学习笔记)

2)将sNode的左子树赋值为delNode的左子树 ( sNode.left = delNode.left );玩转数据结构5之二分搜索树(学习笔记)3)将sNode的右子树赋值为delNode右子树中删除sNode以后的二分搜索树( sNode.right = delMin(delNode.right) );

4) 删除delNode节点 ( delNode.left = delNode.right = null; delNode = sNode )

Java代码实现:

  
    
    
  
// 移除二分搜索树中的任意元素epublic void removeElement(E e) { // 如果树为空,则抛异常(可选择操作) if(size==0) throw new IllegalArgumentException("The tree is empty."); // 调用私有方法,从以root为根的二分搜索树中删除元素e root = removeElement(root,e);}// 从以node为根结点的二分搜索树种删除元素e,返回删除后的根结点private Node removeElement(Node node,E e) { // 如果node为空,表明没有找到该元素 if(node==null) { return null; } // 如果node节点就是要删除的元素 // 分三种情况分别处理 if(e.equals(node.e)) {  // 待删除结点左子树为空的情况 if(node.left==null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } // 待删除结点右子树为空的情况 if(node.right==null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } // 待删除结点左右子树均不为空的情况 // 找到待删除节点右子树中的最小值作为新的节点 Node minNode = minimum(node.right); // 新节点的右子树为待删除节点右子树中删掉最小值的树 minNode.right = removeMin2(node.right); // 新节点的左子树为待删除节点的左子树 minNode.left = node.left; // 待删除节点的左右子树清空 node.left = node.right = null; // 返回新节点作为根节点 return minNode;  } // 如果要删除的元素小于node节点的元素,向node的左子树递归 else if(e.compareTo(node.e)<0) { node.left = removeElement(node.left,e); return node; } else { // e.compareTo(node.e)>0 node.right = removeElement(node.right,e); return node; }}

4. 功能测试

public static void main(String[] args) { BST<Integer> bst = new BST<>(); int[] nums = {5,3,6,8,4,2}; for(int num:nums) { bst.addElement(num); } ///////////////// // 5 // // / \ // // 3 6 // // / \ \ // // 2 4 8 // ///////////////// bst.preOrder(); // 5, 3, 2, 4, 6, 8 System.out.println(); 
// System.out.println(bst); // System.out.println(); bst.inOrder(); // 2,3,4,5,6,8 System.out.println(); bst.postOrder(); // 2, 4, 3, 8, 6, 5 System.out.println(); bst.preOderNR(); // 5, 3, 2, 4, 6, 8 System.out.println(); bst.levelOrder(); // 5, 3, 6, 2, 4, 8 System.out.println(bst.getSize()); // 6 System.out.println(); //bst.removeMin(); bst.removeMin2(); bst.levelOrder(); // 5, 3, 6, 4, 8 System.out.println(); bst.removeMax2(); bst.levelOrder(); // 5, 3, 6, 4 System.out.println(); System.out.println("size:"+bst.getSize()); // size: 4 System.out.println("Max:"+bst.maxmum()); // Max: 6 System.out.println("Min:"+bst.minimum()); // Min: 3 ///////////////// // 5 // // / \ // // 3 6 // // | // // 4 // ///////////////// System.out.println(); bst.removeElement(5); ///////////////// // 6 // // / // // 3 // // | // // 4 // ///////////////// bst.levelOrder(); // 6, 3, 4 System.out.println("size:"+bst.getSize());// size: 3}

5. 总结

本节主要学习了二分搜索树这样一种高效的数据结构。从二分搜索树的基本结构出发,介绍了如何使用递归法向二分搜索树中添加元素、查找元素以及二分搜索树的前序、中序和后序遍历的递归实现。借助栈的相关知识,实现了二分搜索树前序遍历的非递归实现;借助队列的相关知识又实现了二分搜索树的层序遍历。最后,介绍了如何从二分搜索树中删除元素,包括最小值、最大值以及任意指定的元素。主要难点在于如何删除任意元素,这里又细分了三种情况进行处理:待删除节点只有右孩子、只有左孩子以及左右都有孩子的情况。对于左右都有孩子的情况,采用Hibbard删除法,从右孩子中找到最小值节点作为新的根节点。下节学习集合与映射这两种数据结构,并深入分析二分搜索树的时间复杂度。

GitHub地址:https://github.com/xkzhai2019/dataStructure

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《玩转数据结构5之二分搜索树(学习笔记)》的版权归原作者「炼数笔记」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注炼数笔记微信公众号

炼数笔记微信公众号:gh_6c71dccb1bd1

炼数笔记

手机扫描上方二维码即可关注炼数笔记微信公众号

炼数笔记最新文章

精品公众号随机推荐