數據結構與算法——平衡二叉樹(AVL樹)

天然呆dull 2021-09-18 15:49:30 阅读数:437

算法 平衡 二叉 avl

二叉排序樹存在的問題

一個數列 {1,2,3,4,5,6},創建一顆二叉排序樹(BST)

創建完成的樹如上圖所示,那麼它存在的問題有以下幾點:

  1. 左子樹全部為空,從形式上看,更像一個單鏈錶

  2. 插入速度沒有影響

  3. 但查詢速度明顯降低

    因為需要依次比較,不能利用二叉排序樹的折半優勢。而且每次都還要比較左子樹,可能比單鏈錶查詢速度還慢。

那麼解决這個劣勢的方案就是:平衡二叉樹(AVL)

基本介紹

平衡二叉樹也叫 平衡二叉搜索樹(Self-balancing binary search tree),又被稱為 AVL 樹,可以保證 查詢效率較高。它是解决 二叉排序 可能出現的查詢問題。

它的特點:是一顆空樹或它的 左右兩個子樹的高度差的絕對值不超過 1,並且左右兩個子樹都是一棵平衡二叉樹

平衡二叉樹的常用實現方法有:

  • 紅黑樹
  • AVL(算法)
  • 替罪羊樹
  • Treap
  • 伸展樹

想了解更多的可以去看 平衡樹——維基百科

如下所述,哪些是平衡二叉樹?

  1. 是平衡二叉樹:

    • 左子樹高度為 2
    • 右子樹高度為 1

    他們差值為 1

  2. 也是平衡二叉樹

  3. 不是平衡二叉樹

    1. 左子樹高度為 3
    2. 右子樹高度為 1

    他們差值為 2,所以不是

單旋轉(左旋轉)

一個數列 4,3,6,5,7,8 ,創建出它對應的平衡二叉樹。

思路分析:下圖紅線部分是調整流程。

按照規則調整完成之後,形成了下面這樣一棵樹

完整流程如下圖所示:

如上圖,插入 8 時,發現左右子樹高度相差大於 1,則進行左旋轉

  1. 創建一個新的節點 newNode,值等於當前 根節點 的值(上圖根節點為 4)

  2. 把新節點的 左子樹 設置為當前節點(根節點)的 左子樹

    newNode.left = this.left
    
  3. 把新節點的 右子樹 設置為當前節點(根節點)的 右子樹 的 左子樹

    newNode.right = this.right.left
    
  4. 當前節點(根節點) 的值換為 右子節點 的值

    this.value = this.right.value
    
  5. 當前節點(根節點) 的右子樹設置為 右子樹的右子樹(按上圖的話就是 7)

    this.right = this.right.right
    
  6. 當前節點(根節點) 的左子樹設置為新節點newNode

    this.left = this.newNode
    

:左圖是調整前,右圖是調整後。注意調整前的 6 那個節點,調整之後,沒有節點指向他了。也就是說,遍曆的時候它是不可達的。那麼將會自動的被垃圾回收掉。

樹高度計算

前面說過,平衡二叉樹是為了解决二叉排序樹中可能出現的查找效率問題,那麼基本上的代碼都可以在之前的二叉排序樹上進行優化。那麼下面只給出與當前主題相關的代碼,最後放出一份完整的代碼。

樹的高度計算,我們需要得到 3 個高度:

  1. 這顆樹的整體高度
  2. 左子樹的高度
  3. 右子樹的高度
public class AvlTreeTest {
/**
* 樹高度測試
*/
@Test
public void heightTest() {
AvlTree tree = new AvlTree();
int[] arr = {4, 3, 6, 5, 7, 8};
for (int i = 0; i < arr.length; i++) {
tree.add(new Node(arr[i]));
}
tree.infixOrder();
System.out.println("樹高度:" + tree.root.height()); // 4
System.out.println("左樹高度:" + tree.root.leftHeight()); // 1
System.out.println("右樹高度:" + tree.root.rightHeight()); // 3
}
}
/**
* 排序二叉樹
*/
class AvlTree {
Node root;
public Node getRoot() {
return root;
}
}
/**
* 節點
*/
class Node {
/**
* 以當前節點為基礎:計算出它包含它子樹的所有高度
*
* @return
*/
public int height() {
/*
這裏使用了遞歸:返回了左右子樹中,最高的那一個數值。
遞歸原理:第一個開始統計的時候,一定是一個葉子節點
根據這個邏輯:葉子節點的 Math.max(0,0) = 0 看下面代碼
因為當前節點算一層,所以 + 1;
返回到上一層的時候,至少是這樣:Math.max(1,0) = 1
然後把自己本身的層 +1。 以此類推,返回到根節點的時候,就拿到了從包含根節點的樹的高度
所以這個 +1 是精髓所在
*/
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();
}
}

測試輸出

3
4
5
6
7
8
樹高度:4
左樹高度:1
右樹高度:3

旋轉

說下旋轉的時機:也就是什麼時機采取做旋轉的操作?

當然是:當 右子樹高度 - 左子樹高度 > 1 時,才執行左旋轉。

這裏就得到一些信息:

  1. 每次添加完一個節點後,就需要檢查樹的高度

  2. 滿足 右子樹高度 - 左子樹高度 > 1,那麼一定滿足下面的條件:

    ①左子樹高度為 1

    ②右子樹高度為 3

    也就是符合這張圖

也正是有如上的信息邏輯,在實現旋轉的時候,只要按照思路分析寫就可以了,不需要進行邊界判定了。

class Node {
/**
* 添加節點:按照排序二叉樹的要求添加
*
* @param node
*/
public void add(Node node) {
if (node == null) {
return;
}
// 如果添加的值小於當前節點,則往左走
if (node.value < value) {
// 左節點為空,則直接掛在上面
if (left == null) {
left = node;
} else {
// 否則繼續往下查找
left.add(node);
}
} else {
// 往右走
if (right == null) {
right = node;
} else {
right.add(node);
}
}
// 旋轉的時候有以下規則
// 每添加一個節點之後:檢查樹的高度是否平衡
// 如果右子樹高度 - 左子樹高度 > 1,則左旋轉
// 也就是說:每次旋轉的層只涉及到 4 層(對照筆記上的圖示理解)
if (rightHeight() - leftHeight() > 1) {
leftRotate();
}
}
/**
* 以當前節點為根節點,進行左旋轉
*/
public void leftRotate() {
// 1. 創建一個新的節點 newNode,值等於當前 根節點 的值
Node newNode = new Node(value);
// 2. 把 新節點的 左子樹 設置為當前節點的左子樹
newNode.left = left;
// 3. 把 新節點的 右子樹 設置為當前節點的 右子樹的左子樹
newNode.right = right.left;
// 4. 把 當前節點的值,替換為 右子樹 節點的子
value = right.value;
// 5. 把 當前節點 的 右節點 設置為 右子樹的右子樹
right = right.right;
// 6. 把 當前節點 的 左節點 設置為 新節點
left = newNode;
}
}

測試

 /**
* 左旋轉測試
*/
@Test
public void leftRotatedTest() {
AvlTree tree = new AvlTree();
int[] arr = {4, 3, 6, 5, 7, 8};
for (int i = 0; i < arr.length; i++) {
tree.add(new Node(arr[i]));
}
tree.infixOrder();
System.out.println("樹高度:" + tree.root.height()); // 3
System.out.println("左樹高度:" + tree.root.leftHeight()); // 2
System.out.println("右樹高度:" + tree.root.rightHeight()); // 2
}

測試輸出

3
4
5
6
7
8
樹高度:3
左樹高度:2
右樹高度:2

看完代碼之後,它的旋轉其實就是,將 root 節點,往下沉到了,root.right 節點下面。

看著上圖,是否有想過,貌似根本就可以不用前面講解的 6 個步驟來旋轉:

  1. 不用創建新節點
  2. 直接將 node 節點下沉
  3. 更改 node 的 right 節點為 right.left
  4. 更改 right.left = node

其實就已經完成了旋轉。但是你仔細想一想,旋轉邏輯是寫在 node 裏面的, avgTree 中的引用如何改變?除非把旋轉邏輯移動到 avgTree 中去,就可以省略掉新建節點的步驟來完成。

右旋轉

弄懂了左旋轉,對於右旋轉其實就很好理解了:

  • 左旋轉:右 - 左 > 1,把右邊的往左邊旋轉一層
  • 右旋轉:左 - 右 > 1,把左邊的往右邊旋轉一層

他們其實是反著來的,那麼右旋轉的思路如下:

  1. 創建一個新的節點 newNode,值等於當前 根節點 的值(以 4 創建)

  2. 把新節點的 右子樹 設置為當前節點(根節點)的 右子樹

    newNode.right = right
    
  3. 把新節點的 左子樹 設置為當前節點(根節點)的 左子樹的右子樹

    newNode.left = left.right
    
  4. 當前節點(根節點) 的值換為 左子節點 的值

    value = left.value
    
  5. 當前節點 (根節點)的左子樹設置為 左子樹的左子樹

    left = left.left
    
  6. 當前節點 的右子樹設置為新節點

    right = newNode
    

上述步驟就是對下圖的描述:查看圖示更清楚

class Node {
/**
* 添加節點:按照排序二叉樹的要求添加
*
* @param node
*/
public void add(Node node) {
if (node == null) {
return;
}
// 如果添加的值小於當前節點,則往左走
if (node.value < value) {
// 左節點為空,則直接掛在上面
if (left == null) {
left = node;
} else {
// 否則繼續往下查找
left.add(node);
}
} else {
// 往右走
if (right == null) {
right = node;
} else {
right.add(node);
}
}
// 旋轉的時候有以下規則
// 每添加一個節點之後:檢查樹的高度是否平衡
// 如果右子樹高度 - 左子樹高度 > 1,則左旋轉
// 也就是說:每次旋轉的層只涉及到 4 層(對照筆記上的圖示理解)
if (rightHeight() - leftHeight() > 1) {
leftRotate();
return;
}
if (leftHeight() - rightHeight() > 1) {
rightRotate();
}
}
/**
* 以當前節點為根節點,進行右旋轉
*/
public void rightRotate() {
// 1. 創建一個新的節點 newNode,值等於當前 根節點 的值
Node newNode = new Node(value);
// 2. 把 新節點的 右子樹 設置為當前節點的右子樹
newNode.right = right;
// 3. 把 新節點的 左子樹 設置為當前節點的 左子樹的右子樹
newNode.left = left.right;
// 4. 把 當前節點的值,替換為 左子樹 節點的子
value = left.value;
// 5. 把 當前節點 的 左節點 設置為 左子樹的左子樹
left = left.left;
// 6. 把 當前節點 的 右節點 設置為 新節點
right = newNode;
}
}

測試

 /**
* 右旋轉測試
*/
@Test
public void rightRotatedTest() {
AvlTree tree = new AvlTree();
int[] arr = {10, 12, 8, 9, 7, 6};
for (int i = 0; i < arr.length; i++) {
tree.add(new Node(arr[i]));
}
tree.infixOrder();
System.out.println("樹高度:" + tree.root.height()); // 3
System.out.println("左樹高度:" + tree.root.leftHeight()); // 2
System.out.println("右樹高度:" + tree.root.rightHeight()); // 2
System.out.println("當前根節點:" + tree.root); // 8
}

測試輸出

6
7
8
9
10
12
樹高度:3
左樹高度:2
右樹高度:2
當前根節點:Node{value=8}

雙旋轉

在前面的例子中,使用單旋轉(即一次旋轉)就可以將非平衡二叉樹轉換為平衡二叉樹。

但是在某些情况下,就無法做到。比如下面這兩組數列

int[] arr ={10,11,7,6,8,9}
int[] arr ={2,1,6,5,7,3}

運行上面的代碼測試可以發現並未生效

 /**
* 不能通過單旋轉解决的場景
*/
@Test
public void notLeftOrRightRotatedTest() {
AvlTree tree = new AvlTree();
int[] arr = {10, 11, 7, 6, 8, 9};
for (int i = 0; i < arr.length; i++) {
tree.add(new Node(arr[i]));
}
tree.infixOrder();
System.out.println("樹高度:" + tree.root.height()); // 4
System.out.println("左樹高度:" + tree.root.leftHeight()); // 1
System.out.println("右樹高度:" + tree.root.rightHeight()); // 3
System.out.println("當前根節點:" + tree.root); // 7
}

測試輸出

6
7
8
9
10
11
樹高度:4
左樹高度:1
右樹高度:3
當前根節點:Node{value=7}

為什麼會出現這種情况呢?看下圖

左側這個樹滿足 leftHeight - rightHeight > 1 ,也就是滿足右旋轉,旋轉之後,樹結構變化了。但是還是一個非平衡二叉樹。

它的主要原因是:root 左子樹的 左子樹高度 小於 右子樹的高度。即:節點 7 的左子樹高度小於右子樹的高度。

解决辦法:

  1. 先將 7 這個節點作為 root 節點,進行左旋轉
  2. 再將原始的 root 節點進行右旋轉

過程示意圖如下:

其實可以參考下前面兩個單旋轉的圖例,它有這樣一個特點:

  1. 右旋轉:
    • root 的 left 左子樹高度 大於 右子樹高度
    • 右旋轉的時候,會將 left.right 旋轉到 right.left 節點上
  2. 左旋轉:
    • root 的 right 右子樹高度 大於 左子樹高度
    • 左旋轉的時候,會將 right.left 旋轉到 left.right 上。

如果不滿足這個要求,在第二個操作的時候,就會導致 2 層的高度被旋轉到 1 層的節點下面,導致不平衡了。

那麼解决代碼如下:

在 Node 類的 add 方法中進行雙節點邏輯的執行。

 /**
* 添加節點:按照排序二叉樹的要求添加
*
* @param node
*/
public void add(Node node) {
if (node == null) {
return;
}
// 如果添加的值小於當前節點,則往左走
if (node.value < value) {
// 左節點為空,則直接掛在上面
if (left == null) {
left = node;
} else {
// 否則繼續往下查找
left.add(node);
}
} else {
// 往右走
if (right == null) {
right = node;
} else {
right.add(node);
}
}
// 旋轉的時候有以下規則
// 每添加一個節點之後:檢查樹的高度是否平衡
// 如果右子樹高度 - 左子樹高度 > 1,則左旋轉
// 也就是說:每次旋轉的層只涉及到 4 層(對照筆記上的圖示理解)
// 小旋轉的時候:只涉及到 3 層,旋轉的時候,最多操作了當前節點和左右節點,所以不會導致 NPE 問題,這一點一定要明白
if (rightHeight() - leftHeight() > 1) {
// 當 右節點的:左子樹高度 大於 右子樹的高度時,將 right 節點進行 右旋轉
if (right != null && right.leftHeight() > right.rightHeight()) {
right.rightRotate();
}
leftRotate();
return;
}
if (leftHeight() - rightHeight() > 1) {
// 當 左節點的:右子樹高度 大於 左子樹的高度時,將 left 節點進行左旋轉
if (left != null && left.rightHeight() > left.leftHeight()) {
left.leftRotate();
}
rightRotate();
}
}

測試代碼

 /**
* 添加雙旋轉之後,之前測試不能旋轉的數列進行測試
*/
@Test
public void doubleRotatedTest() {
AvlTree tree = new AvlTree();
int[] arr = {10, 11, 7, 6, 8, 9};
// int[] arr ={2,1,6,5,7,3}
for (int i = 0; i < arr.length; i++) {
tree.add(new Node(arr[i]));
}
tree.infixOrder();
System.out.println("樹高度:" + tree.root.height());
System.out.println("左樹高度:" + tree.root.leftHeight());
System.out.println("右樹高度:" + tree.root.rightHeight());
System.out.println("當前根節點:" + tree.root);
}

輸出信息

6
7
8
9
10
11
樹高度:3
左樹高度:2
右樹高度:2
當前根節點:Node{value=8}
1
2
3
5
6
7
樹高度:3
左樹高度:2
右樹高度:2
當前根節點:Node{value=5}

完整代碼

public class AVLTreeDemo {
public static void main(String[] args) {
//int[] arr = {4,3,6,5,7,8};
//int[] arr = { 10, 12, 8, 9, 7, 6 };
int[] arr = {10, 11, 7, 6, 8, 9};
//創建一個 AVLTree對象
AVLTree avlTree = new AVLTree();
//添加結點
for (int i = 0; i < arr.length; i++) {
avlTree.add(new Node(arr[i]));
}
//遍曆
System.out.println("中序遍曆");
avlTree.infixOrder();
System.out.println("在平衡處理~~");
System.out.println("樹的高度=" + avlTree.getRoot().height()); //3
System.out.println("樹的左子樹高度=" + avlTree.getRoot().leftHeight()); // 2
System.out.println("樹的右子樹高度=" + avlTree.getRoot().rightHeight()); // 2
System.out.println("當前的根結點=" + avlTree.getRoot());//8
}
}
// 創建AVLTree
class AVLTree {
private Node root;
public Node getRoot() {
return root;
}
// 查找要删除的結點
public Node search(int value) {
if (root == null) {
return null;
} else {
return root.search(value);
}
}
// 查找父結點
public Node searchParent(int value) {
if (root == null) {
return null;
} else {
return root.searchParent(value);
}
}
// 編寫方法:
// 1. 返回的 以node 為根結點的二叉排序樹的最小結點的值
// 2. 删除node 為根結點的二叉排序樹的最小結點
/**
* @param node 傳入的結點(當做二叉排序樹的根結點)
* @return 返回的 以node 為根結點的二叉排序樹的最小結點的值
*/
public int delRightTreeMin(Node node) {
Node target = node;
// 循環的查找左子節點,就會找到最小值
while (target.left != null) {
target = target.left;
}
// 這時 target就指向了最小結點
// 删除最小結點
delNode(target.value);
return target.value;
}
// 删除結點
public void delNode(int value) {
if (root == null) {
return;
} else {
// 1.需求先去找到要删除的結點 targetNode
Node targetNode = search(value);
// 如果沒有找到要删除的結點
if (targetNode == null) {
return;
}
// 如果我們發現當前這顆二叉排序樹只有一個結點
if (root.left == null && root.right == null) {
root = null;
return;
}
// 去找到targetNode的父結點
Node parent = searchParent(value);
// 如果要删除的結點是葉子結點
if (targetNode.left == null && targetNode.right == null) {
// 判斷targetNode 是父結點的左子結點,還是右子結點
if (parent.left != null && parent.left.value == value) { // 是左子結點
parent.left = null;
} else if (parent.right != null && parent.right.value == value) {// 是由子結點
parent.right = null;
}
} else if (targetNode.left != null && targetNode.right != null) { // 删除有兩顆子樹的節點
int minVal = delRightTreeMin(targetNode.right);
targetNode.value = minVal;
} else { // 删除只有一顆子樹的結點
// 如果要删除的結點有左子結點
if (targetNode.left != null) {
if (parent != null) {
// 如果 targetNode 是 parent 的左子結點
if (parent.left.value == value) {
parent.left = targetNode.left;
} else { // targetNode 是 parent 的右子結點
parent.right = targetNode.left;
}
} else {
root = targetNode.left;
}
} else { // 如果要删除的結點有右子結點
if (parent != null) {
// 如果 targetNode 是 parent 的左子結點
if (parent.left.value == value) {
parent.left = targetNode.right;
} else { // 如果 targetNode 是 parent 的右子結點
parent.right = targetNode.right;
}
} else {
root = targetNode.right;
}
}
}
}
}
// 添加結點的方法
public void add(Node node) {
if (root == null) {
root = node;// 如果root為空則直接讓root指向node
} else {
root.add(node);
}
}
// 中序遍曆
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序樹為空,不能遍曆");
}
}
}
// 創建Node結點
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
/**
* 以當前節點為基礎:計算出它包含它子樹的所有高度
*
* @return
*/
public int height() {
/*
這裏使用了遞歸:返回了左右子樹中,最高的那一個數值。
遞歸原理:第一個開始統計的時候,一定是一個葉子節點
根據這個邏輯:葉子節點的 Math.max(0,0) = 0 看下面代碼
因為當前節點算一層,所以 + 1;
返回到上一層的時候,至少是這樣:Math.max(1,0) = 1
然後把自己本身的層 +1。 以此類推,返回到根節點的時候,就拿到了從包含根節點的樹的高度
所以這個 +1 是精髓所在
*/
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();
}
//左旋轉方法
private void leftRotate() {
//創建新的結點,以當前根結點的值
Node newNode = new Node(value);
//把新的結點的左子樹設置成當前結點的左子樹
newNode.left = left;
//把新的結點的右子樹設置成帶你過去結點的右子樹的左子樹
newNode.right = right.left;
//把當前結點的值替換成右子結點的值
value = right.value;
//把當前結點的右子樹設置成當前結點右子樹的右子樹
right = right.right;
//把當前結點的左子樹(左子結點)設置成新的結點
left = newNode;
}
//右旋轉
private void rightRotate() {
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
// 查找要删除的結點
/**
* @param value 希望删除的結點的值
* @return 如果找到返回該結點,否則返回null
*/
public Node search(int value) {
if (value == this.value) { // 找到就是該結點
return this;
} else if (value < this.value) {// 如果查找的值小於當前結點,向左子樹遞歸查找
// 如果左子結點為空
if (this.left == null) {
return null;
}
return this.left.search(value);
} else { // 如果查找的值不小於當前結點,向右子樹遞歸查找
if (this.right == null) {
return null;
}
return this.right.search(value);
}
}
// 查找要删除結點的父結點
/**
* @param value 要找到的結點的值
* @return 返回的是要删除的結點的父結點,如果沒有就返回null
*/
public Node searchParent(int value) {
// 如果當前結點就是要删除的結點的父結點,就返回
if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
return this;
} else {
// 如果查找的值小於當前結點的值, 並且當前結點的左子結點不為空
if (value < this.value && this.left != null) {
return this.left.searchParent(value); // 向左子樹遞歸查找
} else if (value >= this.value && this.right != null) {
return this.right.searchParent(value); // 向右子樹遞歸查找
} else {
return null; // 沒有找到父結點
}
}
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
// 添加結點的方法
// 遞歸的形式添加結點,注意需要滿足二叉排序樹的要求
public void add(Node node) {
if (node == null) {
return;
}
// 判斷傳入的結點的值,和當前子樹的根結點的值關系
if (node.value < this.value) {
// 如果當前結點左子結點為null
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);
}
}
// 旋轉的時候有以下規則
// 每添加一個節點之後:檢查樹的高度是否平衡
// 如果右子樹高度 - 左子樹高度 > 1,則左旋轉
// 也就是說:每次旋轉的層只涉及到 4 層(對照筆記上的圖示理解)
// 小旋轉的時候:只涉及到 3 層,旋轉的時候,最多操作了當前節點和左右節點,所以不會導致 NPE 問題,這一點一定要明白
if (rightHeight() - leftHeight() > 1) {
// 當 右節點的:左子樹高度 大於 右子樹的高度時,將 right 節點進行 右旋轉
if (right != null && right.leftHeight() > right.rightHeight()) {
right.rightRotate();
}
leftRotate();
return;
}
if (leftHeight() - rightHeight() > 1) {
// 當 左節點的:右子樹高度 大於 左子樹的高度時,將 left 節點進行左旋轉
if (left != null && left.rightHeight() > left.leftHeight()) {
left.leftRotate();
}
rightRotate();
}
}
// 中序遍曆
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.infixOrder();
}
}
}
版权声明:本文为[天然呆dull]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210918154929497w.html