Machineboy空
Ordered Data Structures # WEEK 3 : AVL Trees ( Adelson-Velsky and Landis Tree) 본문
Ordered Data Structures # WEEK 3 : AVL Trees ( Adelson-Velsky and Landis Tree)
안녕도라 2024. 2. 16. 10:593.1.1 Balanced BST
Balanced BSTs are height-balanced trees that ensures nearly half of
the data is located in each subtree.
불균형한 BST를 균형하게 바꾸는 알고리즘을 개발해보자.
BST Sub-structures
Example: BST Insert
Consider a new node inserted into an initially balanceed BST:
We identify the deepest node in the tree that is out of balance:
BST Rotation
Generic Left Rotation
*arbitary = random
BST Insert, Example #2
Consider a new node inserted into an initially balanced BST:
BST Rotations
- BST rotations restore the balance property to a tree after an insert causes a BST to be out of balance
- Four possible rotations: L,R,LR,RL
- Rotations are local operations
- Rotations do not impact the broader tree.
- Rotations run in O(1) time.
- These trees are called AVL Trees
3.1.2 AVL Analysis
Balanced BSTs that are kept in balance through tree rotations on insert and remove are called AVL trees, named after computer scientists Adelson-Velsky and Landis.
회전을 통해 균형을 유지하는 트리를 AVL Tree
AVL Tree
Everything about finding , inserting, and removing from a BST remains true.
BST의 find, insert, remove의 특성은 여전히 다 true.
하지만 균형을 유지하기 위해 몇가지 단계를 추가함
In an AVL tree, we add steps to ensure we maintain balance.
- Extra work on insert/remove
- To quickly compute the balance factor, AVL trees store the height of every node as part of the node itself.
AVL Trees
An AVL Tree is an implementation of a balanced Binary Search Tree(BST).
An Implementation of an AVL tree starts with a BST implementation and adds two key ideas:
- Maintains the height at each node
- Maintains the balance factor after insert and remove