devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】用Java实现二叉搜索树（二分搜索树）_java 二叉搜索树

作者：小蓝xlanll | 2024-05-03 06:52:02

赞

踩

java 二叉搜索树

1. 概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树
  • 一般来说二叉搜索树不存在重复的元素（JDK中的二叉搜索树也不存在重复的元素）

2. 具体实现

2.1 MyBST类

  1. public class MyBST {
  2.     private TreeNode root;
  3.     private int size;
  4.     static class TreeNode {
  5.         int val;
  6.         TreeNode left;//左孩子的引用
  7.         TreeNode right;//右孩子的引用
  8.         public TreeNode(int val) {
  9.             this.val = val;
  10.         }
  11.     }
  12.  
  13.  
  14. }

2.2 插入

（1）如果树为空树，即根 == null，直接插入

（2）如果树不是空树，按照查找逻辑确定插入位置，插入新结点（val < root.val,在root的左子树中插入；val > root.val,在root的右子树中插入）（默认不存在重复的元素）

  1.     public void add(int val){
  2.         root = add(root,val);
  3.     }
  4.  
  5. //    插入一个新的值val，
  6.     private TreeNode add(TreeNode root, int val) {
  7.         if (root == null){
  8.             TreeNode node = new TreeNode(val);
  9.             size++;
  10.             return node;
  11.         } else if (val < root.val) {
  12.             root.left =  add(root.left,val);
  13.             return root;
  14.         }
  15.         root.right = add(root.right,val);
  16.         return root;
  17.     }

2.3 查找树的最大值

树为空，返回null

树的最大值在数的最右边

  1.     //    找最大,树的最右节点
  2.     public int Max(){
  3.         if (root == null){
  4.             throw new NoSuchElementException("bst is empty! Do no has max node");
  5.         }
  6.         TreeNode node = findMax(root);
  7.         return node.val;
  8.     }
  9.     private TreeNode findMax(TreeNode root){
  10.         if(root.right == null){
  11.             return root;
  12.         }
  13.         return findMax(root.right);
  14.     }

2.4 查找树的最小值

树为空，返回null

树的最小值在数的最左边

  1.     //    找最小，树的最左节点
  2.     public int Min(){
  3.         if (root == null){
  4.             throw new NoSuchElementException("bst is empty! Do no has max node");
  5.         }
  6.         TreeNode node = findMin(root);
  7.         return node.val;
  8.     }
  9.     private TreeNode findMin(TreeNode root){
  10.         if(root.left == null){
  11.             return root;
  12.         }
  13.         return findMin(root.left);
  14.     }

2.5 查找任意值

树为空，返回false

val == root.val 找到了，返回true；

val < root.val,在root的左子树找；

val > root.val,在root的右子树找

  1.     //    查找任意值
  2.     public boolean contains(int val){
  3.         return contains(root,val);
  4.     }
  5.  
  6.     private boolean contains(TreeNode root, int val) {
  7.         if(root == null){
  8.             return false;
  9.         }
  10.         if(root.val == val){
  11.             return true;
  12.         } else if (root.val > val) {
  13.             return contains(root.left,val);
  14.         }
  15.         return contains(root.right,val);
  16.     }

2.6 删除最大值

找到树的最大值，返回它的左子树节点

  1. //    删除最大值
  2.     public int removeMax(){
  3.         TreeNode node = findMax(root);
  4.         root = removeMax(root);
  5.         return node.val;
  6.     }
  7.  
  8.     private TreeNode removeMax(TreeNode root) {
  9.         if(root.right == null) {
  10.             TreeNode left = root.left;
  11.             root = root.left = null;
  12.             size--;
  13.             return left;
  14.         }
  15.         root.right = removeMax(root.right);
  16.         return root;
  17.     }

2.7 删除最小值

找到树的最小值，返回它的右子树节点

  1. //    删除最小值
  2.     public int removeMin(){
  3.         TreeNode node = findMin(root);
  4.         root = removeMin(root);
  5.         return node.val;
  6.     }
  7.  
  8.     private TreeNode removeMin(TreeNode root) {
  9.         if(root.left == null){
  10.             TreeNode right = root.right;
  11.             root.right = root = null;
  12.             size--;
  13.             return right;
  14.         }
  15.         root.left = removeMin(root.left);
  16.         return root;
  17.     }

2.8 删除任意值

（1）找到需要删除的节点
（2）需要删除的节点的左子树为空，返回右子树（可能也为空）；需要删除的节点的右子树为空，返回左子树；需要删除的节点的左右子树都不为空：需要使用替换法进行删除，即在它的右子树中找最小值，用它的值填补到被删除节点中，再来处理该结点的删除问题（或者在左子树中找最大值）
需要删除的节点的右子树中的最小值：需要删除的节点的左子树的每一个值都比它小 
  1. //    删除任意值  Hibbard Deletion 1962
  2.     public void removeValue(int val){
  3.         remove(root,val);
  4.     }
  5.  
  6.     private TreeNode remove(TreeNode root, int val) {
  7.         if(root == null){
  8.             return null;
  9.         } else if (val < root.val) {
  10.             root.left = remove(root.left,val);
  11.             return root;
  12.         }else if (val > root.val){
  13.             root.right = remove(root.right,val);
  14.             return root;
  15.         }else {
  16.             if(root.left == null){
  17.                 TreeNode right = root.right;
  18.                 root.right = root = null;
  19.                 size--;
  20.                 return right;
  21.             }else if (root.right == null){
  22.                 TreeNode left = root.left;
  23.                 root.left = root = null;
  24.                 size--;
  25.                 return left;
  26.             }
  27.             TreeNode suor = findMin(root.right);
  28. //            移除右子树的最小值时维护了size属性~
  29. //            一定要先删除再连左子树
  30.             suor.right = removeMin(root.right);
  31.             suor.left = root.left;
  32.             root.left = root.right = root = null;
  33.             return suor;
  34.         }
  35.     }

2.9 普通中序打印输出

  1.     public void print(){
  2.         print(root);
  3.     }
  4.     private void print(TreeNode root) {
  5.         if (root == null){
  6.             return;
  7.         }
  8.         print(root.left);
  9.         System.out.print(root.val + " ");
  10.         print(root.right);
  11.     }

2.10 美观的中序打印输出

  1.     //    toString打印
  2.     @Override
  3.     public String toString() {
  4.         StringBuilder sb = new StringBuilder();
  5.         generateBSTString(root,0,sb);
  6.         return sb.toString();
  7.     }
  8.  
  9.     private void generateBSTString(TreeNode root, int depth, StringBuilder sb) {
  10.         if(root == null){
  11.             sb.append(generateDepthString(depth) + "null\n");
  12.             return;
  13.         }
  14.         sb.append(generateDepthString(depth) + root.val + "\n");
  15.         generateBSTString(root.left,depth + 1,sb);
  16.         generateBSTString(root.right,depth + 1,sb);
  17.     }
  18.  
  19. //    打印--
  20. //    层数越深，--越多
  21.     private String generateDepthString(int depth) {
  22.         StringBuilder res = new StringBuilder();
  23.         for (int i=0; i<depth; i++){
  24.             res.append("--");
  25.         }
  26.         return res.toString();
  27.     }

3. 整体代码

  1. import java.util.NoSuchElementException;
  2.  
  3. /**
  4.  * 二分搜索树,一般不存相同值的元素
  5.  */
  6.  
  7.  
  8. public class MyBST {
  9.     private TreeNode root;
  10.     private int size;
  11.     static class TreeNode {
  12.         int val;
  13.         TreeNode left;//左孩子的引用
  14.         TreeNode right;//右孩子的引用
  15.  
  16.         public TreeNode(int val) {
  17.             this.val = val;
  18.         }
  19.     }
  20.     
  21.     public void add(int val){
  22.         root = add(root,val);
  23.     }
  24.  
  25. //    插入一个新的值val，
  26.     private TreeNode add(TreeNode root, int val) {
  27.         if (root == null){
  28.             TreeNode node = new TreeNode(val);
  29.             size++;
  30.             return node;
  31.         } else if (val < root.val) {
  32.             root.left =  add(root.left,val);
  33.             return root;
  34.         }
  35.         root.right = add(root.right,val);
  36.         return root;
  37.     }
  38.  
  39. //    找最大,树的最右节点
  40.     public int Max(){
  41.         if (root == null){
  42.             throw new NoSuchElementException("bst is empty! Do no has max node");
  43.         }
  44.         TreeNode node = findMax(root);
  45.         return node.val;
  46.     }
  47.     private TreeNode findMax(TreeNode root){
  48.         if(root.right == null){
  49.             return root;
  50.         }
  51.         return findMax(root.right);
  52.     }
  53.  
  54. //    删除最大值
  55.     public int removeMax(){
  56.         TreeNode node = findMax(root);
  57.         root = removeMax(root);
  58.         return node.val;
  59.     }
  60.  
  61.     private TreeNode removeMax(TreeNode root) {
  62.         if(root.right == null) {
  63.             TreeNode left = root.left;
  64.             root = root.left = null;
  65.             size--;
  66.             return left;
  67.         }
  68.         root.right = removeMax(root.right);
  69.         return root;
  70.     }
  71.  
  72.  
  73.     //    找最小，树的最左节点
  74.     public int Min(){
  75.         if (root == null){
  76.             throw new NoSuchElementException("bst is empty! Do no has max node");
  77.         }
  78.         TreeNode node = findMin(root);
  79.         return node.val;
  80.     }
  81.     private TreeNode findMin(TreeNode root){
  82.         if(root.left == null){
  83.             return root;
  84.         }
  85.         return findMin(root.left);
  86.     }
  87.  
  88. //    删除最小值
  89.     public int removeMin(){
  90.         TreeNode node = findMin(root);
  91.         root = removeMin(root);
  92.         return node.val;
  93.     }
  94.  
  95.     private TreeNode removeMin(TreeNode root) {
  96.         if(root.left == null){
  97.             TreeNode right = root.right;
  98.             root.right = root = null;
  99.             size--;
  100.             return right;
  101.         }
  102.         root.left = removeMin(root.left);
  103.         return root;
  104.     }
  105.  
  106.  
  107.     //    查找任意值
  108.     public boolean contains(int val){
  109.         return contains(root,val);
  110.     }
  111.  
  112.     private boolean contains(TreeNode root, int val) {
  113.         if(root == null){
  114.             return false;
  115.         }
  116.         if(root.val == val){
  117.             return true;
  118.         } else if (root.val > val) {
  119.             return contains(root.left,val);
  120.         }
  121.         return contains(root.right,val);
  122.     }
  123.  
  124. //    删除任意值  Hibbard Deletion 1962
  125.     public void removeValue(int val){
  126.         remove(root,val);
  127.     }
  128.  
  129.     private TreeNode remove(TreeNode root, int val) {
  130.         if(root == null){
  131.             return null;
  132.         } else if (val < root.val) {
  133.             root.left = remove(root.left,val);
  134.             return root;
  135.         }else if (val > root.val){
  136.             root.right = remove(root.right,val);
  137.             return root;
  138.         }else {
  139.             if(root.left == null){
  140.                 TreeNode right = root.right;
  141.                 root.right = root = null;
  142.                 size--;
  143.                 return right;
  144.             }else if (root.right == null){
  145.                 TreeNode left = root.left;
  146.                 root.left = root = null;
  147.                 size--;
  148.                 return left;
  149.             }
  150.             TreeNode suor = findMin(root.right);
  151. //            移除右子树的最小值时维护了size属性~
  152.             suor.right = removeMin(root.right);
  153.             suor.left = root.left;
  154.             root.left = root.right = root = null;
  155.             return suor;
  156.         }
  157.     }
  158.  
  159.  
  160.     //    普通打印
  161.     public void print(){
  162.         print(root);
  163.     }
  164.     private void print(TreeNode root) {
  165.         if (root == null){
  166.             return;
  167.         }
  168.         print(root.left);
  169.         System.out.print(root.val + " ");
  170.         print(root.right);
  171.     }
  172.  
  173. //    toString打印
  174.     @Override
  175.     public String toString() {
  176.         StringBuilder sb = new StringBuilder();
  177.         generateBSTString(root,0,sb);
  178.         return sb.toString();
  179.     }
  180.  
  181.     private void generateBSTString(TreeNode root, int depth, StringBuilder sb) {
  182.         if(root == null){
  183.             sb.append(generateDepthString(depth) + "null\n");
  184.             return;
  185.         }
  186.         sb.append(generateDepthString(depth) + root.val + "\n");
  187.         generateBSTString(root.left,depth + 1,sb);
  188.         generateBSTString(root.right,depth + 1,sb);
  189.  
  190.  
  191.     }
  192.  
  193.     private String generateDepthString(int depth) {
  194.         StringBuilder res = new StringBuilder();
  195.         for (int i=0; i<depth; i++){
  196.             res.append("--");
  197.         }
  198.         return res.toString();
  199.     }
  200. }

4. 性能分析

4.1 理论分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则 二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2⁡N
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N2
问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，都可以是二叉搜索树的性能最佳？

答：TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set ；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证。关于红黑树的内容后序再进行讲解，现在只简单使用一些。

4.2 代码实测

4.2.1 生成随机数组与近似有序的数组

  1. import java.util.Arrays;
  2. import java.util.concurrent.ThreadLocalRandom;
  3.  
  4. public class ArrayUtil {
  5.     private static ThreadLocalRandom random = ThreadLocalRandom.current();
  6.  
  7.     // 生成一个大小为n的近乎有序的数组
  8.     // 数组的有序与否取决于元素的交互次数
  9.     public static int[] generateSortedArray(int n,int swapTimes){
  10.         int[] arr = new int[n];
  11.         for (int i = 0; i < n; i++) {
  12.             arr[i] = i + 1;
  13.         }
  14.         for (int i = 0; i < swapTimes; i++) {
  15.             int x = random.nextInt(0,n);
  16.             int y = random.nextInt(0,n);
  17.             swap(arr,x,y);
  18.         }
  19.         return arr;
  20.     }
  21.     
  22.     private static void swap(int[] arr,int x, int y) {
  23.         int temp = arr[x];
  24.         arr[x] = arr[y];
  25.         arr[y] = temp;
  26.     }
  27.  
  28.     // 生成一个大小为n的随机数数组
  29.     // 随机数的取值范围为[l..r)
  30.     public static int[] generateRandomArray(int n,int l,int r){
  31.         int[] arr = new int[n];
  32.         for (int i = 0; i < n; i++) {
  33.             arr[i] = random.nextInt(l,r);
  34.         }
  35.         return arr;
  36.     }
  37.  
  38.     // 深拷贝数组
  39.     public static int[] arrCopy(int[] arr) {
  40.         return Arrays.copyOf(arr,arr.length);
  41.     }
  42.  
  43. }

4.2.2 测试代码

测试红黑树只需要将二分搜索树的代码注释掉，换成红黑树的就好（代码中我已经给了哪些是二分搜索树的代码，哪些是红黑树的代码）

  1. import MyBST;
  2.  
  3. import java.util.LinkedList;
  4. import java.util.TreeMap;
  5.  
  6. import static util.ArrayUtil.generateRandomArray;
  7. import static util.ArrayUtil.generateSortedArray;
  8.  
  9. public class BSTPerformanceTest {
  10.     public static void main(String[] args) {
  11.         LinkedList<Integer> list = new LinkedList<>();
  12.  
  13. //        红黑树又称红-黑二叉树，红黑树是一颗自平衡的排序二叉树。
  14. //        TreeMap<Integer,Integer> bst = new TreeMap<>();
  15.         渐进有序的数组
  16. //        int n = 10_0000;
  17. //        int[] arr = generateSortedArray(n,50);
  18.  
  19. //        二分搜索树
  20.         MyBST bst = new MyBST();
  21. //        乱序的数组
  22.         int n = 100_0000;
  23.         int[] arr = generateRandomArray(n,0,Integer.MAX_VALUE);
  24.  
  25.  
  26.         System.out.println("-----------------------插入-----------------------------");
  27.         Long start = System.nanoTime();
  28.         for (int i:arr
  29.              ) {
  30.             list.add(i);
  31.         }
  32.         Long end = System.nanoTime();
  33.         System.out.println("链表插入" + (end - start)/1000000.0 + " ms");
  34.         start = System.nanoTime();
  35.         for (int i:arr
  36.         ) {
  37. //            二叉树搜索树
  38.             bst.add(i);
  39. //            红黑树
  40. //            bst.put(i,i);
  41.         }
  42.  
  43.         end = System.nanoTime();
  44.         System.out.println("BST插入" + (end - start)/1000000.0 + " ms");
  45. //        System.out.println("红黑树插入" + (end - start)/1000000.0 + " ms");
  46.  
  47.  
  48.         System.out.println("-----------------------查询-----------------------------");
  49.         start = System.nanoTime();
  50.         list.contains(999);
  51.         end = System.nanoTime();
  52.         System.out.println("链表查询" + (end - start)/1000000.0 + "  ");
  53.         start = System.nanoTime();
  54. //        二叉树搜索树
  55.         bst.contains(999);
  56. //        红黑树
  57. //        System.out.println(bst.containsKey(999));
  58.  
  59.         end = System.nanoTime();
  60.         System.out.println("BST查询" + (end - start)/1000000.0 + "  ");
  61. //        System.out.println("红黑树查询" + (end - start)/1000000.0 + "  ");
  62.  
  63.  
  64.     }
  65. }

4.2.3 测试结果

二分搜索树与链表性能测试

红黑树与链表性能测试

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/528332
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号