트리구조란?
우리는 트리구조를 접한적이 있다. 바로 HTML이다. HTML은 우리가 아는 대표적인 트리구조이다. 부모노드가 있고 그 자식노드,부모자식 관계, 형제관계 등 이 트리구조라고 할수 있다.
트리는 반드시 하나의 시작점(RootNode)으로 부터 여러 자식노드가 자신의 자식노드가 연결된 구조, 즉 부모로부터 뻗어나온 여러 자식노드의 집합이라고 볼수있다. 나무를 연상케 하는 데이터 구조이다.
트리구조는 어디에 쓰이는가
트리구조에 저장하면 더 효율적인 자료들이 있다. 회사나 정부의 조직 구조를 예로 들수있다
최 상위 노드 Root부터 밑으로 하나 하나 뻗어나온걸 볼수있다. 일반적인 트리구조에는 자식 노드 수의 제한은 없다.
Binary search Tree
보통 그냥Tree자료구조를 쓰는 경우는 많지 않다. Tree구조중 이진 탐색 트리(Binary search Tree)를 이용해 검색에 많이 활용되고 있다.
Binary search Tree 란?
한개의 RootNode로 부터 최대 2개의 Child Node를 갖고 그 Child Node는 최대 2개의 Child Node를 가질수 있는 자료구조 이다.
자식 노드를 각각 왼쪽 자식 노드, 오른쪽 자식 노드라고 한다.
트리 구조중 하나인 이진 검색 트리가 있다. 중복 데이터가 없다는 가정 하에 두개의 크기를 쉽게 구분할 수 있기 때문이다. 따라서 한 번 정렬하게 된다면 빠르게 찾을수 있다.
- 이진 트리구조는 각 노드의 자식 노드는 최대 2개로 오른쪽 노드 왼쪽노드 2개만 가질수 있다
트리구조의 명칭
- RootNode에서 마지막 Text까지 가는 길을 경로 (Pach)
- 노드와 노드 사이를 이어주는 것 (edge)
- 부모노드에서 자식노드 사이의 edge의 개수를 높이(height)
Binary search property,Tree property
children: 여러 하위 트리를 포함하는 배열
Root: 트리의 최 상단 노드
Child: 자식노드
Parent: 부모노드
leaf: 자식 노드가 없는 노드
Tree Methods
addChild(): 노드에 자식노드를 추가한다.
contents(): 트리내에 해당 값이 있는지 확인한다.Tree Methods
.insert():입력 값을 자식 노드에 추가
.contains(): 트리안에 입력값과 일치하는 값이 있는지 확인
.depthFirstLog() 트리에 저장된 모든값 가져오기
수도코드.addChild
입력값을 받아 노드의 value부분에 값을 담고 next에 노드와 연결시켜준다.
contetens 입력값과 value와 일치하면 true 없으면 while문을 이용해 Node의 next를 타고 들어가 value를 확인해 값을 비교한다.
insert() 노드의 head부분이 null이면 첫번째 노드에 value부분에 값을 넣어준다.
null이 아니라면 node의 next부분에 value값을 가진 새로운 node를 추가해준다.
contains 입력값이 들어오면 while이 head의 값이 null이 될때까지 반복해준다.
if문으로 입력값과 node의 value값이 같다면 true를 리턴해준다.
node의 next로 전점 파고들어 값을 찾는다.