學習地址：【數據結構與算法基礎-java版】? ? ? ? ? ? ? ? ??🚀數據結構--Java專欄🚀

• 筆記01【01-09】【概述、數組基本使用】【源碼、課件】
• 筆記02【10-18】【棧、隊列、單鏈表(增刪節點)、循環鏈表、雙向循環鏈表、遞歸(斐波那契、漢諾塔)】
• 筆記03【19-27】【（時間、空間復雜度）；八大排序（冒泡、快速、插入、希爾、選擇、歸并、基數、隊列基數）】
• 筆記04【28-33】【樹結構(二叉樹)概述、創建、遍歷、查找節點、刪除節點】
• 筆記05【34-39】【順序存儲二叉樹概述、二叉樹遍歷、堆排序、線索二叉樹實現及遍歷】
• 筆記06【40-48】【赫夫曼樹、概述、原理分析、代碼實現(數據壓縮、創建編碼表、解碼、壓縮文件、解壓文件)】
• 筆記07【49-54】【二叉排序樹（添加、查找、刪除節點）】
• 筆記08【55-57】【二叉平衡樹(AVL)-概述、單旋轉、雙旋轉】
• 筆記09【58-60】【計算機中數據的存儲原理、2-3樹的插入原理、B樹和B+樹】
• 筆記10【61-63】【哈希表概述、散列函數的設計、散列沖突解決方案】
• 筆記11【64-67】【圖結構概述、圖遍歷原理(BFS\DFS)、圖遍歷代碼實現】

目? ?錄

P55 4.28 平衡二叉樹概述

P56 4.29 構建平衡二叉樹之單旋轉

P57 4.30 構建平衡二叉樹之雙旋轉

代碼匯總

1、Node.java

2、BinarySortTree.java

3、TestBinarySortTree.java

---

P55 4.28 平衡二叉樹概述

AVL樹（平衡二叉樹）：左子樹和右子樹的高度差的絕對值不超過1。（包括子樹！左子樹和右子樹，也是平衡二叉樹！）【查找效率比較高！】

【1、2、3、4、5、6、7、8】二叉排序樹-->查找不方便！

P56 4.29 構建平衡二叉樹之單旋轉

將 二叉排序樹 轉換為 平衡樹，保證查找效率！

每加入一個節點，就要檢查一次。-->是否進行旋轉！

P57 4.30 構建平衡二叉樹之雙旋轉

代碼匯總

1、Node.java

package demo12;public class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}/*** 返回當前節點的高度* * @return*/public int height() {return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;}/*** 獲取左子樹的高度* * @return*/public int leftHeight() {if (left == null) {return 0;}return left.height();}/*** 獲取右子樹的高度* * @return*/public int rightHeight() {if (right == null) {return 0;}return right.height();}/*** 向子樹中添加節點* * @param node*/public void add(Node node) {if (node == null) {return;}// 判斷傳入的節點的值比當前子樹的根節點的值大還是小// 添加的節點比當前節點的值更小if (node.value < this.value) {// 如果左節點為空if (this.left == null) {this.left = node;// 如果不為空} else {this.left.add(node);}} else {if (this.right == null) {this.right = node;} else {this.right.add(node);}}// 查詢是否平衡// 進行右旋轉if (leftHeight() - rightHeight() >= 2) {// 雙旋轉if (left != null && left.leftHeight() < left.rightHeight()) {// 先左旋轉left.leftRotate();// 再右旋轉rightRotate();// 單旋轉} else {rightRotate();}}// 左旋轉if (leftHeight() - rightHeight() <= -2) {// 雙旋轉if (right != null && right.rightHeight() < right.leftHeight()) {right.rightRotate();leftRotate();// 單旋轉} else {leftRotate();}}}/*** 左旋轉*/private void leftRotate() {Node newLeft = new Node(value);newLeft.left = left;newLeft.right = right.left;value = right.value;right = right.right;left = newLeft;}/*** 右旋轉*/private void rightRotate() {// 創建一個新的節點，值等于當前節點的值Node newRight = new Node(value);// 把新節點的右子樹設置了當前節點的右子樹newRight.right = right;// 把新節點的左子樹設置為當前節點的左子樹的右子樹newRight.left = left.right;// 把當前節點的值換為左子節點的值value = left.value;// 把當前節點的左子樹設置了左子樹的左子樹left = left.left;// 把當前節點的右子樹設置為新節點right = newRight;}/*** 中序遍歷* * @param node*/public void midShow(Node node) {if (node == null) {return;}midShow(node.left);System.out.println(node.value);midShow(node.right);}/*** 查找節點* * @param value2*/public Node search(int value) {if (this.value == value) {return this;} else if (value < this.value) {if (left == null) {return null;}return left.search(value);} else {if (right == null) {return null;}return right.search(value);}}/*** 搜索父節點* * @param value* @return*/public Node searchParent(int value) {if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {if (this.value > value && this.left != null) {return this.left.searchParent(value);} else if (this.value < value && this.right != null) {return this.right.searchParent(value);}return null;}} }

2、BinarySortTree.java

package demo12;public class BinarySortTree {Node root;/*** 向二叉排序樹中添加節點* * @param node*/public void add(Node node) {// 如果是一顆空樹if (root == null) {root = node;} else {root.add(node);}}/*** 中序遍歷二叉排序樹，從小到大的順序*/public void midShow() {if (root != null) {root.midShow(root);}}/*** 節點的查找* * @param value* @return*/public Node search(int value) {if (root == null) {return null;} else {return root.search(value);}}/*** 刪除節點* * @param value*/public void delete(int value) {if (root == null) {return;} else {// 找到這個節點Node target = search(value);// 如果沒有這個節點if (target == null) {return;}// 找到他的父節點Node parent = searchParent(value);// 要刪除的節點是葉子節點if (target.left == null && target.right == null) {// 要刪除的節點是父節點的左子節點if (parent.left.value == value) {parent.left = null;// 要刪除的節點是父節點的右子節點} else {parent.right = null;}// 要刪除的節點有兩個子節點的情況} else if (target.left != null && target.right != null) {// 刪除右子樹中值最小的節點，取獲取到該節點的值int min = deleteMin(target.right);// 替換目標節點中的值target.value = min;// 要刪除的節點有一個左子節點或右子節點} else {// 有左子節點if (target.left != null) {// 要刪除的節點是父節點的左子節點if (parent.left.value == value) {parent.left = target.left;// 要刪除的節點是父節點的右子節點} else {parent.right = target.left;}// 有右子節點} else {// 要刪除的節點是父節點的左子節點if (parent.left.value == value) {parent.left = target.right;// 要刪除的節點是父節點的右子節點} else {parent.right = target.right;}}}}}/*** 刪除一顆樹中最小的節點* * @param right* @return*/private int deleteMin(Node node) {Node target = node;// 遞歸向左找while (target.left != null) {target = target.left;}// 刪除最小的這個節點delete(target.value);return target.value;}/*** 搜索父節點* * @param value* @return*/public Node searchParent(int value) {if (root == null) {return null;} else {return root.searchParent(value);}} }

3、TestBinarySortTree.java

package demo12;public class TestBinarySortTree {public static void main(String[] args) { // int[] arr = new int[] {8,9,6,7,5,4};int[] arr = new int[] { 8, 9, 5, 4, 6, 7 };// 創建一顆二叉排序樹BinarySortTree bst = new BinarySortTree();// 循環添加for (int i : arr) {bst.add(new Node(i));}// 查看高度System.out.println(bst.root.height());System.out.println(bst.root.value);}}

🚀🚀🚀🚀🚀🚀

總結

以上是生活随笔為你收集整理的数据结构Java08【二叉平衡树(AVL)-概述、单旋转、双旋转】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。