다른 컬렉션이나 자료구조에 대한 정보가 필요하다면 아래의 링크로 들어오시라😎
01. [자바] 컬렉션 프레임워크(Collections Framework)
컬렉션 프레임워크란? 다수의 데이터를 다루는 데 필요한 배열과 비슷하지만 더 성능이 뛰어난 많은 클래스들을 제공한다 크게 3가지 그룹이 있는데 List, Set, Map이다. 계층도와 같이 Map인터페이
staticclass.tistory.com
Binary Tree
이진 트리(binary tree)는 링크드리스트 처럼 여러 개의 노드가 서로 연결된 구조이며
'루트(root)' 라고 불리는 하나의 노드에서계속 확장해 나갈 수 있다.
위 아래로 연결된 두 노드를 '부모-자식관계'에 있다고 하고
위의 노드를 부모, 아래의 노드를 자식 노드라 한다.
하나의 부모는 최대 2개의 자식 노드와 연결될 수 있다.
Binary Search Tree
이진 검색 트리(binary Search Tree)는 부모노드의 왼쪽에는 부모 보다 작은 값의 노드를
오른쪽에는 부모 노드 보다 큰 값의 노드를 저장하는 이진 트리이다.
예를 들어 이진검색트리에 7, 4, 9, 1 ,5의 순서로 값을 저장한다고 한다면.
첫 번째로 저장되는 값 '7'이 루트가 된다,
두 번째 값은 루트에서 부터 값의 크기를 비교하면서 트리를 따라 내려간다
작은 값은 왼쪽에 큰 값은 오른쪽에 저장되는데 이렇게 트리를 구성하면
왼쪽 마지막 레벨이 제일 작은 값이 되고 오른쪽 마지막 레벨의 값이 제일 큰 값이 된다.
| 이진 검색 트리(binary search tree) - 모든 노드는 최대 두 개의 자식노드를 가질 수 있다. - 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽자식노드의 값은 부모노드의 값보다 커야한다. - 노드의 추가 삭제에 시간이 걸린다. 순차적으로 저장하지 않고 위치를 찾아야 하고 삭제의 경우 트리의 일부를 재구성 해야하기 때문 - 검색(범위검색)과 정렬에 유리하다. 저장된 값의 개수에 비례해서 검색시간이 증가하긴 하지만 개수가 10배 증가해도 특정 값을 찾는데 필요한 비교 횟수가 3~4번만 증가할 정도로 검색 효율이 뛰어나다 - 중복된 값을 저장하지 못한다. |
댓글