AVL Tree

Abstract

---

Transclude of avl_tree.pngg

• Also known as Self-Balancing Binary Search Tree (平衡二叉搜索树)
• A Binary Tree (二叉树) that is empty OR with nodes that are all Height-Balanced
• An optimised Binary Search Tree (二叉搜索树)

Efficient Operations

The self-balancing property guarantees that theHeight of an AVL tree with $n$ nodes is always around $O(logn)$. This means operations like searching, insertion, and deletion take a maximum of $O(logn)$ time, making them very efficient.

Leetcode Problems

---

Properties

• 110. Balanced Binary Tree
• 108. Convert Sorted Array to Binary Search Tree