Live briefing
Everything about AVL tree
Self-balancing binary search tree
In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by not more than one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: AVL treeA 5-minute orientation
- Skim a recent paper: Analysis and visualization of proxy caching using LRU, AVL tree and BST with supervised machine learningInfluential work since 2022
- Pick up a classic book: Data structures and algorithm analysis in CThe most-reprinted book on the subject
- Read the landmark paper: Concurrent Search and Insertion in AVL TreesCited 59 times
- Go sideways: Weight-balanced treeA closely related topic
- Go sideways: Join-based tree algorithmsA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Concurrent Search and Insertion in AVL Trees
A generalization of AVL trees
Decision Tree Induction: An Approach for Data Classification Using AVL-Tree
An Amortized Analysis of Insertions into AVL-Trees
AVL-trees for localized search
On the correspondence between AVL trees and brother trees
A Verifiable Symmetric Searchable Encryption Scheme Based on the AVL Tree
High-Secured Image LSB Steganography Using AVL-Tree with Random RGB Channel Substitution
🆕 Influential since 2022
Analysis and visualization of proxy caching using LRU, AVL tree and BST with supervised machine learning
Comparative Performance of the AVL Tree and Three Variants of the Red‐Black Tree
COMPARATIVE EXPERIMENTAL ANALYSIS OF METHODS FOR IMPLEMENTING THE AVL TREE
Analysing Efficiency and Time Complexity of AVL Tree Re-balancing during Value Insertion
Empirical Performance Analysis of BST and AVL Tree on Modern Computing Architectures: A Stress Test Study Under Varying Data Distributions
📚 Books worth reading
Data structures and algorithm analysis in CMark Allen Weiss · 1993
Starting Out with JavaTony Gaddis · 2004
Data structures & algorithm analysis in JavaMark Allen Weiss · 1999
Fundamentals of data structures in CEllis Horowitz · 1993
Data structures and algorithms in JavaAdam Drozdek · 2001
Algorithm designMichael T. Goodrich, Roberto Tamassia · 2001
Data structures, algorithms, and applications in C++Sartaj Sahni · 1998
C++ Plus Data StructuresNell Dale, Chip Weems · 2016
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Weight-balanced tree In computer science, weight-balanced binary trees (WBTs) are a type of self-balancing binary search trees that can be used to implement dynamic sets, dictionari…
- Join-based tree algorithms In computer science, join-based tree algorithms are a class of algorithms for self-balancing binary search trees. This framework aims at designing highly-parall…
- Red–black tree In computer science, a red–black tree is a self-balancing binary search tree data structure noted for fast storage and retrieval of ordered information…
- Scapegoat tree In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Arne Andersson in 1989 and rediscovered by Igal Galperin and…
- WAVL tree In computer science, a WAVL tree or weak AVL tree is a self-balancing binary search tree. WAVL trees are named after AVL trees, another type of balanced…
- Binary search tree In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each…
- Treap In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain…
- AA tree An AA tree in computer science is a form of balanced tree used for storing and retrieving ordered data efficiently. AA trees are named after their originator…