More actions
imported>minn951120 No edit summary |
imported>minn951120 No edit summary |
||
| Line 14: | Line 14: | ||
** balanced binary search tree | ** balanced binary search tree | ||
** balanced factor = height of left sub tree - height of right search tree | ** balanced factor = height of left sub tree - height of right search tree | ||
** '''모든 노드의 balanced factor는 1이나 0이나 - | ** '''정의 : 모든 노드의 balanced factor는 1이나 0이나 -1인 binary search tree''' | ||
** hieght는 최대 1.44log(n+2) | ** hieght는 최대 1.44log(n+2) | ||
** LL, RR, LR, RL rotation | ** LL, RR, LR, RL rotation | ||
Revision as of 06:20, 29 January 2015
참석자
| 김상헌 | 김정민 | 양종만 |
| O | O | O |
진행
- AVL트리를 공부했습니다.
- balanced binary search tree
- balanced factor = height of left sub tree - height of right search tree
- 정의 : 모든 노드의 balanced factor는 1이나 0이나 -1인 binary search tree
- hieght는 최대 1.44log(n+2)
- LL, RR, LR, RL rotation
- LR은 케이스가 많습니다.
- insert랑 delete할 때, unbalance해지면 이걸 이용해서 조정함
과제
- AVL트리 구현~~(...)~~