[자료구조] 이진 탐색 트리(Binary Search Tree, BST) - 정의, 조건, 탐색, 삽입, 삭제, 시간복잡도

복습 겸 정리를 위해 새로운 카테고리를 만들었습니다 ㅎㅎ! (글 순서는 공부했던 순서가 아닙니다!)

1. 이진 탐색 트리 (Binary Search Tree, BST)?

: 이진 트리로서 탐색을 효율적으로 하기 위한 자료구조 2. BST(이진 탐색 트리) 조건 (공백 트리도 BST이다!)

① 이진 트리(자식 최대 2개) 여야 한다. ② 모든 원소는 서로 다른 유일한 key를 가져야 한다. ③ 왼쪽 서브 트리의 key 값 < 루트의 key 값 < 오른쪽 서브 트리의 key 값이어야 한다. ④ 왼쪽 서브 트리 & 오른쪽 서브 트리 모두 BST(이진 탐색 트리) 여야 한다. 3. BST(이진 탐색 트리) 탐색 - root에서 시작해서, if 탐색할 key 값 x = root 노드 key 값 → 탐색 성공 if 탐색할 key 값 x < root 노드 key 값 → 왼·서(왼쪽 서브 트리)로 가서 탐색 if 탐색할 key 값 x > root 노드 key 값 → 오·서(오른쪽 서브 트리)로 가...

요청 처리 중입니다...

[자료구조] 이진 탐색 트리(Binary Search Tree, BST) - 정의, 조건, 탐색, 삽입, 삭제, 시간복잡도

등록된 다른 글