Chapter 7. Binary Search Trees - 보충 자료-

Presentation on theme: "Chapter 7. Binary Search Trees - 보충 자료-"— Presentation transcript:

1 Chapter 7. Binary Search Trees - 보충 자료-
[INA240] Data Structures and Practice Youn-Hee Han

2 0. BST Reviews Binary Search Tree (이진 탐색 트리)의 삭제
When we delete a node, we need to consider how we take care of the children of the deleted node. This has to be done such that the property of BST is maintained.

3 0. BST Reviews Binary Search Tree (이진 탐색 트리)의 삭제 Flash 예제 (Click)
Data Structure

4 0. BST Reviews Binary Search Tree (이진 탐색 트리)의 삭제
get max of left subtree get min of right subtree Data Structure

5 0. BST Reviews 키 Lee인 노드를 찾기 키 Yoo인 노드 찾기
Park, Kim, Lee(왼쪽 트리) 대 Cho, Kim, Lee(오른쪽 트리) 키 Yoo인 노드 찾기 Park, Seo, Yoo: (왼쪽 트리) 대 Cho, Kim, Lee, Park, Seo, Yoo (오른쪽 트리) Data Structure

6 0. BST Reviews 균형 최악의 경우 탐색은 Leaf Node까지 왼쪽 트리는 완전한 균형.
오른쪽 트리는 왼쪽 서브트리 Height: 0(빈 트리), 오른쪽 서브트리 (Root가 Kim인 트리) Height: 5로서 균형이 현저히 무너져 있음 최악의 경우 탐색은 Leaf Node까지 왼쪽 트리는 최악의 경우에도 높이가 3. 오른쪽 트리는 최악의 경우 높이 6를 모두 타고 내려와야 함. 오른쪽 트리는 연결 리스트(Linked List)에 가까움. 연결이 한쪽으로 일직선으로(Linear Structure) 진행하는 트리  편향 이진트리 (Skewed Binary Tree) Data Structure

7 0. BST Reviews 이진 탐색 트리에서의 탐색 효율 균형이 잘 잡혀있는 경우 균형이 무너진 경우
높이는 lgN에 가까움. 높이만큼 키 비교를 요함. 효율 O(lgN) 균형이 무너진 경우 최악의 경우 연결 리스트에 가까움 효율 O(N) Data Structure