自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

Java編程內(nèi)功-數(shù)據(jù)結(jié)構(gòu)與算法「平衡二叉樹(shù)」

作者：Java精髓
開(kāi)發(fā) 后端 算法
本篇繼續(xù)給大家介紹關(guān)于Java編程的相關(guān)知識(shí)，今天主要介紹數(shù)據(jù)結(jié)構(gòu)與算法之平衡二叉樹(shù)，希望對(duì)你有所幫助！

[[390860]]

二叉排序樹(shù)可能的問(wèn)題

給定一個(gè)數(shù)列{1,2,3,4,5,6}，要求創(chuàng)建一個(gè)二叉排序樹(shù)(BST)，分析問(wèn)題所在

問(wèn)題分析：

  1. 左子樹(shù)全部為空，從形式上看，更像一個(gè)單鏈表;
  2. 插入速度沒(méi)有影響;
  3. 查詢速度明顯降低(因?yàn)樾枰淮伪容^)，不能發(fā)揮BST的優(yōu)勢(shì)。因?yàn)槊看芜€要比較左子樹(shù)，其查詢速度，比單鏈表還慢。
  4. 解決方案-平衡二叉樹(shù)(ALV)

基本介紹

  1. 平衡二叉樹(shù)也叫平衡二叉搜索樹(shù)(Self-balancing binary search tree)，又稱為AVL樹(shù)，可以保證查詢效率較高。
  2. 具有以下特點(diǎn)：它是一顆空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一顆平衡二叉樹(shù)。平衡二叉樹(shù)的常用實(shí)現(xiàn)方法有 紅黑樹(shù)、AVL、替罪羊樹(shù)、Treap、伸展樹(shù)等;
  3. 舉例說(shuō)明，下圖前兩個(gè)都是平衡二叉樹(shù)，第一個(gè)左右子樹(shù)的高度差絕對(duì)值是1，第二個(gè)左右子樹(shù)高度差的絕對(duì)值是0，而第三個(gè)的左右子樹(shù)高度差的絕對(duì)值是2，這樣第三個(gè)就不是平衡二叉樹(shù);

平衡二叉樹(shù)之左旋轉(zhuǎn)

步驟：

  1. 創(chuàng)建一個(gè)新的節(jié)點(diǎn)newNode，值等于當(dāng)前根節(jié)點(diǎn)的值。
  2. 把新節(jié)點(diǎn)的左子樹(shù)設(shè)置成當(dāng)前節(jié)點(diǎn)的左子樹(shù)。
  3. 把新節(jié)點(diǎn)的右子樹(shù)設(shè)置成當(dāng)前節(jié)點(diǎn)的右子樹(shù)的左子樹(shù)。
  4. 把當(dāng)前節(jié)點(diǎn)的值換為當(dāng)前右子節(jié)點(diǎn)的值。
  5. 把當(dāng)前節(jié)點(diǎn)的右子樹(shù)設(shè)置成右子樹(shù)的右子樹(shù)。
  6. 把當(dāng)前節(jié)點(diǎn)的左子樹(shù)設(shè)置為新的節(jié)點(diǎn)。

平衡二叉樹(shù)之右旋轉(zhuǎn)

步驟：

  1. 創(chuàng)建一個(gè)新的節(jié)點(diǎn)，值等于當(dāng)前根的節(jié)點(diǎn)的值。
  2. 把新節(jié)點(diǎn)的右子樹(shù)設(shè)置成當(dāng)前節(jié)點(diǎn)的右子樹(shù)。
  3. 把新節(jié)點(diǎn)的左子樹(shù)設(shè)置成當(dāng)前節(jié)點(diǎn)的左子樹(shù)的右子樹(shù)。
  4. 把當(dāng)前節(jié)點(diǎn)的值換位左子節(jié)點(diǎn)的值。
  5. 把當(dāng)前節(jié)點(diǎn)的左子樹(shù)設(shè)置成左子樹(shù)的左子樹(shù)。
  6. 把當(dāng)前節(jié)點(diǎn)的右子樹(shù)設(shè)置為新的節(jié)點(diǎn)。

平衡二叉樹(shù)之雙旋轉(zhuǎn)

在某些情況下，單旋轉(zhuǎn)不能完成完成平衡二叉樹(shù)的轉(zhuǎn)換，需要進(jìn)行兩次旋轉(zhuǎn)。

  1. 如果它的右子樹(shù)的左子樹(shù)的高度大于它的右子樹(shù)的右子樹(shù)的高度，需要先對(duì)右子樹(shù)進(jìn)行右旋轉(zhuǎn)，再對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)。
  2. 如果它的左子樹(shù)的右子樹(shù)高度大于它的左子樹(shù)的左子樹(shù)高度，
  3. 需要對(duì)左子樹(shù)先進(jìn)行左旋轉(zhuǎn),再對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)。

代碼案例

  1. package com.xie.avl; 
  2.  
  3. public class AVLTreeDemo { 
  4.     public static void main(String[] args) { 
  5.         int[] arr = {4, 3, 6, 5, 7, 8}; 
  6.         AVLTree avlTree = new AVLTree(); 
  7.         for (int i = 0; i < arr.length; i++) { 
  8.             avlTree.add(new Node(arr[i])); 
  9.         } 
  10.         System.out.println("中序遍歷"); 
  11.         avlTree.infixOrder(); 
  12.         System.out.println("在沒(méi)有平衡處理前~~"); 
  13.         System.out.println("樹(shù)的高度=" + avlTree.getRoot().height()); 
  14.         System.out.println("樹(shù)的左子樹(shù)的高度=" + avlTree.getRoot().leftHeight()); 
  15.         System.out.println("樹(shù)的右子樹(shù)的高度=" + avlTree.getRoot().rightHeight()); 
  16.     } 
  17. } 
  18.  
  19. class AVLTree { 
  20.     private Node root; 
  21.  
  22.     public Node getRoot() { 
  23.         return root; 
  24.     } 
  25.  
  26.     public void setRoot(Node root) { 
  27.         this.root = root; 
  28.     } 
  29.  
  30.     //查找要?jiǎng)h除的節(jié)點(diǎn)的父節(jié)點(diǎn) 
  31.     public Node searchParent(Node node) { 
  32.         if (root != null) { 
  33.             return root.searchParent(node); 
  34.         } else { 
  35.             return null; 
  36.         } 
  37.     } 
  38.  
  39.     //查找要?jiǎng)h除的節(jié)點(diǎn) 
  40.     public Node search(int value) { 
  41.         if (root == null) { 
  42.             return null; 
  43.         } else { 
  44.             return root.search(value); 
  45.         } 
  46.     } 
  47.  
  48.     /** 
  49.      * 找到以node 根的二叉排序樹(shù)的最小值，并刪除以node 為根節(jié)點(diǎn)的二叉排序樹(shù)的最小節(jié)點(diǎn) 
  50.      * 
  51.      * @param node 傳入節(jié)點(diǎn)（當(dāng)做二叉排序樹(shù)的根節(jié)點(diǎn)) 
  52.      * @return 返回以node為根節(jié)點(diǎn)的二叉排序樹(shù)的最小節(jié)點(diǎn)值 
  53.      */ 
  54.     public int delRightTreeMin(Node node) { 
  55.         Node target = node; 
  56.         //循環(huán)查找左節(jié)點(diǎn) 
  57.         while (target.left != null) { 
  58.             target = target.left; 
  59.         } 
  60.         //刪除最小節(jié)點(diǎn) 
  61.         delNode(target.value); 
  62.         return target.value; 
  63.     } 
  64.  
  65.     /** 
  66.      * 找到以node 根的二叉排序樹(shù)的最大值，并刪除以node 為根節(jié)點(diǎn)的二叉排序樹(shù)的最大節(jié)點(diǎn) 
  67.      * 
  68.      * @param node 傳入節(jié)點(diǎn)（當(dāng)做二叉排序樹(shù)的根節(jié)點(diǎn)) 
  69.      * @return 返回以node為根節(jié)點(diǎn)的二叉排序樹(shù)的最大節(jié)點(diǎn)值 
  70.      */ 
  71.     public int delLeftTreeMax(Node node) { 
  72.         Node target = node; 
  73.         while (target.right != null) { 
  74.             target = target.right; 
  75.         } 
  76.  
  77.         //刪除最大節(jié)點(diǎn) 
  78.         delNode(target.value); 
  79.         return target.value; 
  80.     } 
  81.  
  82.     //刪除節(jié)點(diǎn) 
  83.     public void delNode(int value) { 
  84.         if (root == null) { 
  85.             return; 
  86.         } else { 
  87.             Node targetNode = search(value); 
  88.             if (targetNode == null) { 
  89.                 return; 
  90.             } 
  91.             if (targetNode == root) { 
  92.                 root = null; 
  93.                 return; 
  94.             } 
  95.             Node parentNode = searchParent(targetNode); 
  96.  
  97.             if (targetNode.left == null && targetNode.right == null) { 
  98.                 //如果要?jiǎng)h除的節(jié)點(diǎn)是葉子節(jié)點(diǎn) 
  99.                 if (parentNode.left != null && parentNode.left.value == targetNode.value) { 
  100.                     parentNode.left = null; 
  101.                 } 
  102.                 if (parentNode.right != null && parentNode.right.value == targetNode.value) { 
  103.                     parentNode.right = null; 
  104.                 } 
  105.             } else if (targetNode.left != null && targetNode.right != null) { 
  106.                 //如果要?jiǎng)h除的節(jié)點(diǎn)是有兩個(gè)子樹(shù)的節(jié)點(diǎn) 
  107.                 int minValue = delRightTreeMin(targetNode.right); 
  108.                 targetNode.value = minValue; 
  109.                 //上下代碼刪除效果一樣 
  110.                 //int maxValue = delLeftTreeMax(targetNode.left); 
  111.                 //targetNode.value = maxValue; 
  112.             } else { 
  113.                 //要?jiǎng)h除的節(jié)點(diǎn)是只有左子節(jié)點(diǎn) 
  114.                 if (targetNode.left != null) { 
  115.                     if (parentNode != null) { 
  116.                         if (parentNode.left == targetNode) { 
  117.                             parentNode.left = targetNode.left; 
  118.                         } else { 
  119.                             parentNode.right = targetNode.left; 
  120.                         } 
  121.                     } else { 
  122.                         //如果父節(jié)點(diǎn)是空，讓root換位 
  123.                         root = targetNode.left; 
  124.                     } 
  125.                 } else {//要?jiǎng)h除的節(jié)點(diǎn)是只有右子節(jié)點(diǎn) 
  126.                     if (parentNode != null) { 
  127.                         if (parentNode.left == targetNode) { 
  128.                             parentNode.left = targetNode.right; 
  129.                         } else { 
  130.                             parentNode.right = targetNode.right; 
  131.                         } 
  132.                     } else { 
  133.                         //如果父節(jié)點(diǎn)是空，讓root換位 
  134.                         root = targetNode.right; 
  135.                     } 
  136.  
  137.                 } 
  138.             } 
  139.         } 
  140.     } 
  141.  
  142.     //添加節(jié)點(diǎn) 
  143.     public void add(Node node) { 
  144.         if (root == null) { 
  145.             root = node; 
  146.         } else { 
  147.             root.add(node); 
  148.         } 
  149.     } 
  150.  
  151.     //中序遍歷 
  152.     public void infixOrder() { 
  153.         if (root != null) { 
  154.             root.infixOrder(); 
  155.         } else { 
  156.             System.out.println("二叉排序?yàn)榭?，不能遍歷"); 
  157.         } 
  158.     } 
  159. } 
  160.  
  161. class Node { 
  162.     int value; 
  163.     Node left; 
  164.     Node right; 
  165.  
  166.     public Node(int value) { 
  167.         this.value = value; 
  168.     } 
  169.  
  170.     /** 
  171.      * 返回左子樹(shù)的高度 
  172.      * 
  173.      * @return 
  174.      */ 
  175.     public int leftHeight() { 
  176.         if (left == null) { 
  177.             return 0; 
  178.         } 
  179.         return left.height(); 
  180.     } 
  181.  
  182.     /** 
  183.      * 返回右子樹(shù)的高度 
  184.      * 
  185.      * @return 
  186.      */ 
  187.     public int rightHeight() { 
  188.         if (this.right == null) { 
  189.             return 0; 
  190.         } 
  191.         return right.height(); 
  192.     } 
  193.  
  194.     /** 
  195.      * 返回以該節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)的高度 
  196.      * 
  197.      * @return 
  198.      */ 
  199.     public int height() { 
  200.         return Math.max(this.left == null ? 0 : this.left.height(), this.right == null ? 0 : this.right.height()) + 1; 
  201.     } 
  202.  
  203.     /** 
  204.      * 左旋轉(zhuǎn) 
  205.      */ 
  206.     public void leftRotate() { 
  207.         //創(chuàng)建新的節(jié)點(diǎn)，以當(dāng)前根節(jié)點(diǎn)的值 
  208.         Node newNode = new Node(value); 
  209.         //把新的節(jié)點(diǎn)的左子樹(shù)設(shè)置為當(dāng)前節(jié)點(diǎn)的左子樹(shù) 
  210.         newNode.left = left; 
  211.         //把新的右子樹(shù)設(shè)置為當(dāng)前節(jié)點(diǎn)的右子樹(shù)的左子樹(shù) 
  212.         newNode.right = right.left; 
  213.         //把當(dāng)前節(jié)點(diǎn)的值替換成右子節(jié)點(diǎn)的值 
  214.         value = right.value; 
  215.         //把當(dāng)前節(jié)點(diǎn)的右子樹(shù)設(shè)置成當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)的右子樹(shù) 
  216.         right = right.right; 
  217.         //把當(dāng)前的節(jié)點(diǎn)的左子節(jié)點(diǎn)(左子樹(shù)),設(shè)置成新的節(jié)點(diǎn) 
  218.         left = newNode; 
  219.     } 
  220.  
  221.     /** 
  222.      * 右旋轉(zhuǎn) 
  223.      */ 
  224.     public void rightRotate() { 
  225.         //創(chuàng)建新的節(jié)點(diǎn)，以當(dāng)前根節(jié)點(diǎn)的值 
  226.         Node newNode = new Node(value); 
  227.         //把新的節(jié)點(diǎn)的右子樹(shù)設(shè)置成當(dāng)前節(jié)點(diǎn)的右子樹(shù) 
  228.         newNode.right = right; 
  229.         //把新的節(jié)點(diǎn)的左子樹(shù)設(shè)置為當(dāng)前節(jié)點(diǎn)左子樹(shù)的右子樹(shù) 
  230.         newNode.left = left.right; 
  231.         //把當(dāng)前節(jié)點(diǎn)的值換為左子節(jié)點(diǎn)的值 
  232.         value = left.value; 
  233.         //把當(dāng)前節(jié)點(diǎn)左子樹(shù)設(shè)置成左子樹(shù)的左子樹(shù) 
  234.         left = left.left; 
  235.         //把當(dāng)前節(jié)點(diǎn)的右子樹(shù)設(shè)置新節(jié)點(diǎn) 
  236.         right = newNode; 
  237.     } 
  238.  
  239.     /** 
  240.      * 查找要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn) 
  241.      * 
  242.      * @param node 要?jiǎng)h除的節(jié)點(diǎn) 
  243.      * @return 要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn) 
  244.      */ 
  245.     public Node searchParent(Node node) { 
  246.         //如果當(dāng)前節(jié)點(diǎn)就是要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)就返回 
  247.         if ((this.left != null && this.left.value == node.value) || 
  248.                 (this.right != null && this.right.value == node.value)) { 
  249.             return this; 
  250.         } else { 
  251.             if (this.left != null && node.value < this.value) { 
  252.                 //如果查找的節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值，向左子樹(shù)遞歸查找 
  253.                 return this.left.searchParent(node); 
  254.             } else if (this.right != null && value >= this.value) { 
  255.                 //如果查找的節(jié)點(diǎn)的值小于當(dāng)前節(jié)點(diǎn)的值，向左子樹(shù)遞歸查找 
  256.                 return this.right.searchParent(node); 
  257.             } else { 
  258.                 return null; 
  259.             } 
  260.         } 
  261.     } 
  262.  
  263.     /** 
  264.      * 查找要?jiǎng)h除的節(jié)點(diǎn) 
  265.      * 
  266.      * @param value 要?jiǎng)h除的節(jié)點(diǎn)的值 
  267.      * @return 刪除的節(jié)點(diǎn) 
  268.      */ 
  269.     public Node search(int value) { 
  270.         if (value == this.value) { 
  271.             return this; 
  272.         } else if (value < this.value) { 
  273.             if (this.left != null) { 
  274.                 return this.left.search(value); 
  275.             } else { 
  276.                 return null; 
  277.             } 
  278.         } else { 
  279.             if (this.right != null) { 
  280.                 return this.right.search(value); 
  281.             } else { 
  282.                 return null; 
  283.             } 
  284.         } 
  285.     } 
  286.  
  287.     //遞歸的形式添加節(jié)點(diǎn)，滿足二叉排序樹(shù)的要求 
  288.     public void add(Node node) { 
  289.         if (node == null) { 
  290.             return; 
  291.         } 
  292.         if (node.value < this.value) { 
  293.             if (this.left == null) { 
  294.                 this.left = node; 
  295.             } else { 
  296.                 //遞歸向左子樹(shù)添加 
  297.                 this.left.add(node); 
  298.             } 
  299.         } else { 
  300.             if (this.right == null) { 
  301.                 this.right = node; 
  302.             } else { 
  303.                 //遞歸向右子節(jié)點(diǎn)添加 
  304.                 this.right.add(node); 
  305.             } 
  306.         } 
  307.  
  308.         //當(dāng)添加完一個(gè)節(jié)點(diǎn)后，如果（右子樹(shù)高度-左子樹(shù)高度）> 1 ，進(jìn)行左旋轉(zhuǎn) 
  309.         if (rightHeight() - leftHeight() > 1) { 
  310.             //如果它的右子樹(shù)的左子樹(shù)的高度大于它的右子樹(shù)的右子樹(shù)的高度，需要先對(duì)右子樹(shù)進(jìn)行右旋轉(zhuǎn)，再對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn) 
  311.             if(right != null && right.leftHeight()>right.rightHeight()){ 
  312.                 right.rightRotate(); 
  313.                 leftRotate(); 
  314.             }else{ 
  315.                 //直接進(jìn)行左旋轉(zhuǎn)即可 
  316.                 leftRotate(); 
  317.             } 
  318.             return; 
  319.         } 
  320.  
  321.         //當(dāng)添加完一個(gè)節(jié)點(diǎn)后，如果（左子樹(shù)高度-右子樹(shù)高度）> 1 ，進(jìn)行右旋轉(zhuǎn) 
  322.         if (leftHeight() - rightHeight() > 1) { 
  323.             //如果它的左子樹(shù)的右子樹(shù)高度大于它的左子樹(shù)的左子樹(shù)高度，需要對(duì)左子樹(shù)先進(jìn)行左旋轉(zhuǎn),再對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn) 
  324.             if(left != null && left.rightHeight() > left.leftHeight()){ 
  325.                 left.leftRotate(); 
  326.                 rightRotate(); 
  327.             }else{ 
  328.                 //直接進(jìn)行右旋轉(zhuǎn)即可 
  329.                 rightRotate(); 
  330.             } 
  331.  
  332.         } 
  333.     } 
  334.  
  335.     //中序遍歷 
  336.     public void infixOrder() { 
  337.         if (this.left != null) { 
  338.             this.left.infixOrder(); 
  339.         } 
  340.         System.out.println(this); 
  341.         if (this.right != null) { 
  342.             this.right.infixOrder(); 
  343.         } 
  344.     } 
  345.  
  346.     @Override 
  347.     public String toString() { 
  348.         return "Node{" + 
  349.                 "value=" + value + 
  350.                 '}'; 
  351.     } 
  352. } 

 【編輯推薦】

 

責(zé)任編輯：姜華 來(lái)源： 今日頭條
Java編程數(shù)據(jù)結(jié)構(gòu)算法
相關(guān)推薦

2021-03-19 10:25:12

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-22 09:00:22

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-29 10:13:47

Java編程數(shù)據(jù)結(jié)構(gòu)算法

2020-11-02 09:15:47

算法與數(shù)據(jù)結(jié)構(gòu)

2021-09-29 10:19:00

算法平衡二叉樹(shù)

2021-03-18 08:44:20

Java數(shù)據(jù)結(jié)構(gòu)算法

2020-09-23 18:25:40

算法二叉樹(shù)多叉樹(shù)

2021-04-19 07:47:42

數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)Tree

2021-04-20 08:37:14

數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)樹(shù)

2021-04-07 09:26:37

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-28 20:12:27

數(shù)據(jù)結(jié)構(gòu)創(chuàng)建

2013-01-30 10:34:02

數(shù)據(jù)結(jié)構(gòu)

2021-05-12 09:07:09

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-24 10:41:04

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-04-23 09:12:09

Java數(shù)據(jù)結(jié)構(gòu)算法

2023-04-06 07:39:48

2021-04-13 09:37:41

Java數(shù)據(jù)結(jié)構(gòu)算法

2021-03-09 06:30:32

JAVA數(shù)據(jù)結(jié)構(gòu)算法

2021-01-07 08:12:47

數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)樹(shù)

2021-03-26 08:40:28

Java數(shù)據(jù)結(jié)構(gòu)算法
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)