AVL Tree
An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees for any node cannot be more than one.
The difference between the heights of the left subtree and the right subtree for any node is known as the balance factor of the node.
Rotating the subtrees in an AVL Tree:
An AVL tree may rotate in one of the following four ways to keep itself balanced:
Left Rotation:
When a node is added into the right subtree of the right subtree, if the tree gets out of balance, we do a single left rotation.
Right Rotation:
If a node is added to the left subtree of the left subtree, the AVL tree may get out of balance, we do a single right rotation.
Left-Right Rotation:
A left-right rotation is a combination in which first left rotation takes place after that right rotation executes.
Right-Left Rotation:
A right-left rotation is a combination in which first right rotation takes place after that left rotation executes.
Operations in an AVL Tree:
Trees Notes for GATE Exam [2024]Tree Traversal Techniques:
Trees are foundational structures in computer science, serving as the backbone for numerous algorithms and data representations. GATE aspirants should be well versed in tree structures to prepare for the GATE Exam in 2024. This article aims to provide a concise yet comprehensive overview of trees, exploring key concepts crucial for a comprehensive understanding of the topic. To help candidates understand tree-based problem-solving scenarios, these notes provide invaluable insights and knowledge essential to success in GATE.
Table of Content
- Introduction to Tree
- Basic Terminologies In Tree Data Structure
- Types of Tree data structures
- Binary Tree
- Ternary Tree
- N-ary Tree or Generic Tree
- Binary Search Tree
- AVL Tree
- Previously Asked GATE Questions on Trees