자료구조_비선형구조 ① 트리 - 이진 탐색 트리

 

[1] 이진검색트리

---

(1) 이진트리 binary tree

• 부모노드에 자식노드가 두 개 이하인 트리
• 컴퓨터 응용에서 가장 많이 사용한다 
• 모든 노드가 최대 2개의 서브 트리를 가진다 
• 왼쪽 서브 트리와 오른쪽 서브 트리로 구분한다 
• 편향 이진트리 , 포화 이진트리 , 완전 이진트리가 있다 

 

 

(2) 이진 검색 트리 binary search tree

• [23,10,48,15,7,22,56] 순으로 자료를 넣은 트리 
• 임의의 키를 가진 원소를 삽입, 삭제, 검색하는데 효율적인 자료구조 
• 모든 연산은 키값을 기준으로 수행 
• 검색을 중심으로 만들어진 트리 
• 자료(key)의 중복을 허용하지 않음
• 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가짐
• 자료를 검색에 걸리는 시간이 평균 log(n) 임
• inorder traversal 탐색을 하게 되면 자료가 정렬되어 출력됨