AVL tree java
AVL tree is also known as a self-balancing binary tree which is used for balancing and calculating the difference between respective heights of left and right subtrees whose result can’t come out as more than one in the entire balanced tree. Binary Search tree operation allows the insertion, deletion, search, max, and min operation which is necessary as part of the AVL tree as well. All these operations are considered costly affairs due to which if the difference between the heights of all BST is maintained then the cost and time complexity associated with it can be maintained.
Start Your Free Software Development Course
Web development, programming languages, Software testing & others
Syntax:
There is not as such proper syntax but while implementing it in Java AVL tree is considered as a data structure where the syntax is represented as follows:
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; }
Explanation:
In the syntax flow here Class Node_demo contains key, height, and structure which describes the key-value pair where the elements will get stored. Followed by AVL_Tree demo_1 node containing root node and its associated elements with value pairs having a height to be maintained everywhere with values as null.
How does the AVL tree work in java?
- There exists proper flow where AVL tree works in Java and is invented by GM Adelson in 1962.
- AVL tree is defined as a height-balanced binary search tree in which each node is associated with a balance factor that gets calculated by subtracting the height of its right-subtree from that of its left-subtree.
- Tree is called balanced if the balance factor lies between -1 to 1 otherwise the tree will need to be balanced from top to bottom.
- As the balance tree controls the height of the binary search tree then the height comes out to be O(h) whereas there is a provision where it is needed to extend the binary search tree once it gets skewed than in that case it comes out to be (n-1) for its manipulation.
- Once the skewed tree gets limited then in that case it imposes an upper bound on all operations which come out as O (log n) where n is the number of nodes.
- There are ways also to rotate the AVL tree and it happens only in one condition where if the balance factor lies between -1, 1, or 0.
- There are four types of Rotations which are as follows:
- LL Rotations: Node gets inserted if it lies in the left subtree of the tree with node D.
- RR Rotations: Node gets inserted if it lies in the right subtree of the tree with node D.
- LR Rotations: Node gets inserted if it gets inserted in the right subtree of a left subtree with node D.
- RL Rotations: Node gets inserted if it gets inserted in the left subtree of a right subtree with node D.
Where D stands for that node whose height and balance factor lies other than -1, 1, and 0 due to which all these Rotations are required to make them properly in format.
There are many operations that exist and for it, there must have proper rotations with proper analysis for manipulation.
Example: This example demonstrates the AVL tree where the insertion, left and right insertion with a preorder, postorder, and levelorder representation as shown in the output below.
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); } }
Output:
Explanation: This program performs the insertion of elements in the AVL tree post which there is some order in a way where some checks like whether the list taken is empty or not and then if the AVL tree has rotations to be performed in a pre-order, post-order, or level order format. All elements given automatically takes input and arrange them in proper order.
Conclusion
AVL tree in Java is used as a proper data structure which is liked by many developers as it gives an edge in terms of operations and helps in saving and consuming time-complexity created by a big set of codes. AVL tree has the capability to handle major operations like insertion, deletion, rotation, and removal from the entire subtrees if heights are maintained properly.
The above is the detailed content of AVL tree java. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics











Java 8 introduces the Stream API, providing a powerful and expressive way to process data collections. However, a common question when using Stream is: How to break or return from a forEach operation? Traditional loops allow for early interruption or return, but Stream's forEach method does not directly support this method. This article will explain the reasons and explore alternative methods for implementing premature termination in Stream processing systems. Further reading: Java Stream API improvements Understand Stream forEach The forEach method is a terminal operation that performs one operation on each element in the Stream. Its design intention is

PHP is a scripting language widely used on the server side, especially suitable for web development. 1.PHP can embed HTML, process HTTP requests and responses, and supports a variety of databases. 2.PHP is used to generate dynamic web content, process form data, access databases, etc., with strong community support and open source resources. 3. PHP is an interpreted language, and the execution process includes lexical analysis, grammatical analysis, compilation and execution. 4.PHP can be combined with MySQL for advanced applications such as user registration systems. 5. When debugging PHP, you can use functions such as error_reporting() and var_dump(). 6. Optimize PHP code to use caching mechanisms, optimize database queries and use built-in functions. 7

PHP and Python each have their own advantages, and the choice should be based on project requirements. 1.PHP is suitable for web development, with simple syntax and high execution efficiency. 2. Python is suitable for data science and machine learning, with concise syntax and rich libraries.

PHP is suitable for web development, especially in rapid development and processing dynamic content, but is not good at data science and enterprise-level applications. Compared with Python, PHP has more advantages in web development, but is not as good as Python in the field of data science; compared with Java, PHP performs worse in enterprise-level applications, but is more flexible in web development; compared with JavaScript, PHP is more concise in back-end development, but is not as good as JavaScript in front-end development.

PHP and Python each have their own advantages and are suitable for different scenarios. 1.PHP is suitable for web development and provides built-in web servers and rich function libraries. 2. Python is suitable for data science and machine learning, with concise syntax and a powerful standard library. When choosing, it should be decided based on project requirements.

PHPhassignificantlyimpactedwebdevelopmentandextendsbeyondit.1)ItpowersmajorplatformslikeWordPressandexcelsindatabaseinteractions.2)PHP'sadaptabilityallowsittoscaleforlargeapplicationsusingframeworkslikeLaravel.3)Beyondweb,PHPisusedincommand-linescrip

The reasons why PHP is the preferred technology stack for many websites include its ease of use, strong community support, and widespread use. 1) Easy to learn and use, suitable for beginners. 2) Have a huge developer community and rich resources. 3) Widely used in WordPress, Drupal and other platforms. 4) Integrate tightly with web servers to simplify development deployment.

PHP is suitable for web development and content management systems, and Python is suitable for data science, machine learning and automation scripts. 1.PHP performs well in building fast and scalable websites and applications and is commonly used in CMS such as WordPress. 2. Python has performed outstandingly in the fields of data science and machine learning, with rich libraries such as NumPy and TensorFlow.
