Ordered Data Structures # WEEK 2 : BST Analysis, How to build balanced BST

이진탐색트리를 만드는 방법은 N!가지이며, worst case의 경우 find, insert, remove의 시간복잡도가 배열이나 연결리스트보다 좋지 못함.

따라서 균형잡힌 이진탐색 트리를 만드는 것이 중요한데, 여기서 사용되는 개념이 균형 계수 등이 있고, 다음 시간에 b tree나, avl tree 등을 만드는 방법을 알아볼 것임.

 

2.5 BST Analysis

Binary Search Trees(BSTs) can take on many forms and structures even containing the same data:

둘다 BST 조건 충족하지만 삽입 순서를 다르게 했더니 모양이 다름

 

So we want to think about how can we build trees that are both efficient, and what happens when we build a tree that's not so great? average case, worst case, best

 

Puzzle

How many possible ways can we insert the same data into a BST?

 

1~7까지 넣는다 치면 7!가지

가장 먼저 넣는 노드가 루트 노드가 됨. 5먼저 넣으면 5가 루트가 되는 식.

즉, 이진 탐색트리에 삽입하는 방법은 n!가지

 

 

The best outcome, the only algorithm that runs in log n time for both find, insert, and remove is this average binary search tree. we can't do that with array and sorted list.

 

모두 로그엔 시간 복잡도를 가지는 것은 BST뿐 그래서 균형잡힌 이진 탐색트리를 고안하는 방법을 알고 싶음

 

BST의 worst case는 배열을 능가하지 못함

 

Height Balance Factor(균형계수)

The height balance factor(b) of a node is the difference in height between its two subtree:

왼쪽은 0 이므로 perfect balance

 

Balanced BST

A balanced BST is a BST where every node's balance factor has a magnititude(크기) of 0 or 1:

 

By having a magnitude of 0 or 1, that means the balance factor can either be -1, 0, or 1. Only if these three are the only valance factors that appear in every single node in the tree do we say this binary tree is balanced

 

 

BST Analysis

• There are n! different ways to create BSTs with the same data.
  • The worst-case BST will have a height proportional to the number of nodes
  • An average BST will have a height proportional to the argorithm of the number of nodes.
• Using a height balance factor, we can formalize if a given BST is balanced.