Mathlife
Mathlife의 학습 노트
Mathlife
전체 방문자
오늘
어제
  • 분류 전체보기
    • CS
      • 알고리즘
      • 자료구조
      • 운영체제
      • 네트워크
      • 데이터베이스
    • 프로그래밍 언어
      • Java
      • JavaScript
      • C·C++
      • Python
    • Backend
      • Spring
    • Frontend
      • HTML
      • CSS
    • Math
      • Linear Algebra
      • Calculus
    • AI
      • ML
      • DL
      • RL
    • Git

블로그 메뉴

  • 홈
  • 관리
  • 글쓰기
  • 태그
  • 방명록

공지사항

인기 글

태그

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Mathlife

Mathlife의 학습 노트

Balanced BST
CS/자료구조

Balanced BST

2022. 4. 18. 19:31

BST에 1, 2, 3, 4, 5, 6, 7 을 넣는다고 생각해보자.

 

1, 2, 3, 4, 5, 6, 7 순서로 값을 추가하면

 

4, 2, 6, 1, 3, 5, 7 순서로 값을 추가하면

 

 

전자의 경우 linked list와 별반 차이가 없다.

 

후자의 경우 탐색에 $O(\log{n})$의 시간이 소요되지만, 전자의 경우 탐색에 $O(n)$의 시간이 소요된다.

 

 

따라서 unbalanced BST보다는 rotation 개념을 이용해 balance를 맞춘 balanced BST가 자주 사용된다.

 

Balanced tree의 예로 AVL tree, red-black tree, splay tree 등이 있다.

'CS > 자료구조' 카테고리의 다른 글

AVL Tree  (0) 2022.04.19
Tree rotation  (0) 2022.04.18
Binary Search Tree (BST)  (0) 2022.04.18
Max Heap  (0) 2022.04.18
Tree (Introduction)  (0) 2022.04.18
    'CS/자료구조' 카테고리의 다른 글
    • AVL Tree
    • Tree rotation
    • Binary Search Tree (BST)
    • Max Heap
    Mathlife
    Mathlife

    티스토리툴바