자료구조 강의 11화 :: 이진 탐색 트리, SPLAY 트리, 균형 트리

자료구조 강의 11화 :: 이진 탐색 트리, SPLAY 트리, 균형 트리

자료구조 11화를 듣고 배운내용

KEYWORDS

이진 탐색 트리(Binary Search Tree) : 빠르게 탐색할 수 있는 이진트리

: 빠르게 탐색할 수 있는 이진트리 Splay 트리 : 자주 탐색하는 키를 가진 노드를 루트 가깝게 위치하게 구성한 이진 탐색 트리

: 자주 탐색하는 키를 가진 노드를 루트 가깝게 위치하게 구성한 이진 탐색 트리 AVL 트리 : 노드의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이 나는 조건을 만족하는 트리

: 노드의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이 나는 조건을 만족하는 트리 트리의 높이 : 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값, 루트에서 잎까지 가장 긴 경로 길이

: 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값, 루트에서 잎까지 가장 긴 경로 길이 트리의 무게 : 트리에 속한 잎 노드의 개수

: 트리에 속한 잎 노드의 개수 무게가 균형 잡힌 트리: 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리

이진 탐색 트리(BS Tree)

탐색에 최적화된 이진 트리

노드를 삽입, 삭제하는 문제가 가장 효과적인 이진 트리

노드 삽입

루트부터 키 값은 비교해서 왼쪽/오른쪽을 정하며 내려가서 삽입

이진 트리가 이진 탐색 트리가 될 조건

왼쪽 자식 노드 < 부모

오른쪽 자식 노드 > 부모

스플레이(SPLAY) 트리

이진 탐색 트리를 변형한 트리

자주 탐색하는 키를 가진 노드를 루트에 가깝에 올린다.

비교 횟수 줄이자는 접근

Splay 연산을 이용해서 사용하려는 노드로 트리를 재구성한다

균형 트리

균형을 맞춰서 탐색을 더 효율적으로 만든 트리

=> BB트리, AVL 트리

균형을 잡으면 비교 횟수가 줄어든다

search by Kevin Laminto #unsplash

from http://forgottenknowledge.tistory.com/158 by ccl(A) rewrite - 2021-10-18 12:00:32