Tree
•
계층적인 구조를 표현
◦
조직도
◦
디렉토리와 서브디렉토리 구조
◦
가계도
◦
트리는 노드들과 노드를 연결하는 링크(혹은 브랜치)들로 구성됨
◦
맨 위의 노드를 루트라고 부름
◦
부모와 자식의 관계로 구성
동일한 부모를 가진 노드들을 형제(sibling)관계라고 한다
◦
자식이 없는 노드들을 리프(Leaf) 노드라고 한다
이진 검색 트리 (Binary Search Tree)
•
여러 개의 키를 저장
•
다음과 같은 연산들을 지원하는 자료구조
◦
insert - 새로운 키 삽입
◦
search - 키 탐색
◦
delete - 키의 삭제
•
정렬된 혹은 정렬되지 않은 배열, 혹은 연결 리스트를 사용할 경우 insert, search, delete 중 적어도 하나는 O(n)