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

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

 

 

KEYWORDS

• 이진 탐색 트리(Binary Search Tree): 빠르게 탐색할 수 있는 이진트리
  
  
• Splay 트리: 자주 탐색하는 키를 가진 노드를 루트 가깝게 위치하게 구성한 이진 탐색 트리
  
  
• AVL 트리: 노드의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이 나는 조건을 만족하는 트리
  
  
• 트리의 높이: 노드가 가질 수 있는 가장 높은 레벨에 1을 더한 값, 루트에서 잎까지 가장 긴 경로 길이
  
  
• 트리의 무게: 트리에 속한 잎 노드의 개수
• 무게가 균형 잡힌 트리: 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리

 

 

이진 탐색 트리(BS Tree)

탐색에 최적화된 이진 트리

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

 

노드 삽입

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

 

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

• 왼쪽 자식 노드 < 부모
• 오른쪽 자식 노드 > 부모

 

 

스플레이(SPLAY) 트리

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

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

비교 횟수 줄이자는 접근

 

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

 

 

균형 트리

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

=> BB트리, AVL 트리

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

 

 

search by Kevin Laminto #unsplash