Ordered Data Structures # WEEK 3 : AVL Trees ( Adelson-Velsky and Landis Tree)

3.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

stick을 mountain으로 바꿀 것

 

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.

balance 계수를 저울질해서 -2나 2면 회전이 필요하다

update height 함수와 rotation함수

 

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