AVL樹java-java教程-PHP中文網

AVL樹也稱為自平衡二元樹，用於平衡計算左右子樹各自的高度差，其結果在整個平衡樹中不能多於一個。二元搜尋樹操作允許插入、刪除、搜尋、最大和最小操作，這也是 AVL 樹的一部分所必需的。所有這些操作都被認為是成本高昂的事務，因此，如果保持所有 BST 高度之間的差異，則可以保持與其相關的成本和時間複雜度。

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

文法：

沒有這樣正確的語法，但在 Java AVL 樹中實現它時，它被視為一種資料結構，其語法表示如下：

Class Node_demo
{
int key, height_0;
Node left, right;
Node_demo (int d_1)
{
key = d_1;
height_0 = 1;
}
}
class AVLTree_demo1 {
Node root_0;
int height_0(Node N_1) {
if (N_1== null)
return 0;
return N_1.height;
}

登入後複製

說明：

在此處的語法流程中，Node_demo 類別包含鍵、高度和結構，它們描述了儲存元素的鍵值對。接下來是包含根節點及其關聯元素的 AVL_Tree demo_1 節點，其具有值對的值對，其高度在任何地方都需要維護，值為空。

AVL樹在java中是如何運作的？

AVL樹在Java中工作有適當的流程，它是由GM Adelson於1962年發明的。
AVL樹被定義為高度平衡的二元搜尋樹，其中每個節點都與一個平衡因子相關聯，該平衡因子透過從其左子樹的高度中減去其右子樹的高度來計算。
如果平衡因子介於 -1 到 1 之間，則樹稱為平衡樹，否則樹需要從上到下保持平衡。
由於平衡樹控制二元搜尋樹的高度，因此高度為 O(h)，而有一項規定，一旦二元搜尋樹傾斜，就需要擴展二元搜尋樹。其操縱結果為 (n-1)。
一旦傾斜樹受到限制，那麼在這種情況下，它會對所有操作施加上限，其結果為 O (log n)，其中 n 是節點數。
還有一些方法可以旋轉 AVL 樹，並且僅在平衡因子介於 -1、1 或 0 之間的一種情況下才會發生。
旋轉有四種類型，如下：
LL 旋轉：如果節點位於節點 D 的樹的左子樹中，則插入該節點。
RR 旋轉：如果節點位於節點 D 的樹的右子樹中，則插入該節點。
LR 旋轉：如果節點插入到具有節點 D 的左子樹的右子樹中，則節點將被插入。
RL 旋轉：如果將節點插入到具有節點 D 的右子樹的左子樹中，則節點將被插入。

其中 D 代表高度和平衡因子不為 -1、1 和 0 的節點，因此所有這些旋轉都需要使它們的格式正確。

存在許多操作，為此，必須有適當的旋轉和適當的操作分析。

範例：此範例示範了 AVL 樹，其中插入、左插入和右插入具有前序、後序和層級順序表示，如下面的輸出所示。

import java. util.LinkedList;
import java.util.Queue;
class Node_8 {
int data_0, height_1;
Node_8 left_nd_0;
Node_8 right_nd_0;
Node_8(int d_2) {
data_0 = d_2;
height_1 = 1;
}
}
public class AVLTree_Demo
{
Node_8 root_0;
int height_1(Node_8 N) {
if (N == null)
return 0;
return N.height_1;
}
int max_2(int a_0,  int b_0) {
return (a_0 > b_0) ? a_0 : b_0;
}
Node_8 rightRotation_mode(Node_8 oldRoot_0) {
Node_8 newRoot_0 = oldRoot_0.left_nd_0;
Node_8 temp_0 = newRoot_0.right_nd_0;
newRoot_0.right_nd_0 = oldRoot_0;
oldRoot_0.left_nd_0 = temp_0;
newRoot_0.height_1 = max_2(height_1(newRoot_0.left_nd_0), height_1(newRoot_0.right_nd_0)) + 1;
oldRoot_0.height_1 = max_2(height_1(oldRoot_0.left_nd_0), height_1(oldRoot_0.right_nd_0)) + 1;
return newRoot_0;
}
Node_8 leftRotation_mode(Node_8 oldRoot_0) {
Node_8 newRoot_0 = oldRoot_0.right_nd_0;
Node_8 temp_0 = newRoot_0.left_nd_0;
newRoot_0.left_nd_0 = oldRoot_0;
oldRoot_0.right_nd_0 = temp_0;
newRoot_0.height_1 = max_2(height_1(newRoot_0.left_nd_0), height_1(newRoot_0.right_nd_0)) + 1;
oldRoot_0.height_1=max_2(height_1(oldRoot_0.left_nd_0), height_1(oldRoot_0.right_nd_0)) + 1;
return newRoot_0;
}
int balFactor_c(Node_8 root_0) {
if(root_0 == null)
return 0;
return height_1(root_0.left_nd_0) - height_1(root_0.right_nd_0);
}
Node_8 insert(Node_8 root_0, int data_0) {
if(root_0 == null)
return new Node_8(data_0);
else if(data_0 < root_0.data_0)
root_0.left_nd_0 = insert(root_0.left_nd_0, data_0);
else if(data_0 > root_0.data_0)
root_0.right_nd_0 = insert(root_0.right_nd_0, data_0);
else
return root_0;
root_0.height_1= max_2(height_1(root_0.left_nd_0), height_1(root_0.right_nd_0)) + 1;
int bal = balFactor_c(root_0);
if(bal > 1 && data_0 < root_0.left_nd_0.data_0)
return rightRotation_mode(root_0);
if(bal < -1 && data_0 > root_0.right_nd_0.data_0)
return leftRotation_mode(root_0);
if(bal > 1 && data_0 > root_0.left_nd_0.data_0) {
root_0.left_nd_0 = leftRotation_mode(root_0.left_nd_0);
return rightRotation_mode(root_0);
}
if(bal < -1 && data_0 < root_0.right_nd_0.data_0) {
root_0.right_nd_0 = rightRotation_mode(root_0.right_nd_0);
return leftRotation_mode(root_0);
}
return root_0;
}
void preOrder_traversal(Node_8 node) {
if (node != null) {
System.out.print(node.data_0 + " ");
preOrder_traversal(node.left_nd_0);
preOrder_traversal(node.right_nd_0);
}
}
void levelOrder_traversal(Node_8 root) {
Queue<Node_8> q_1 = new LinkedList<Node_8>();
q_1.add(root);
while(!q_1.isEmpty()) {
Node_8 current = q_1.peek();
System.out.print(current.data_0 + " ");
if(current.left_nd_0 != null)
q_1.add(current.left_nd_0);
if(current.right_nd_0 != null)
q_1.add(current.right_nd_0);
q_1.poll();
}
}
public static void main (String args[]) {
AVLTree_Demo tree = new AVLTree_Demo ();
tree. root_0 = tree.insert(tree.root_0, 15);
tree.root_0 = tree.insert(tree.root_0, 20);
tree.root_0 = tree.insert(tree.root_0, 19);
tree.root_0 = tree.insert(tree.root_0, 40);
tree.root_0 = tree.insert(tree.root_0, 50);
tree.root_0 = tree.insert(tree.root_0, 25);
System.out.println("order_of_Preorder_traversal_representation : ");
tree.preOrder_traversal(tree.root_0);
System.out.println();
System.out.println("Levelorder_of_traversal_representation : ");
tree.levelOrder_traversal(tree.root_0);
}
}

登入後複製

輸出：

AVL樹java