Developer Cafe

트리는 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조이다. 이진트리 모든 노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 이진 트리는 왼쪽 서브 트리와 오른쪽 서브 트리를 가지는데, 서브 트리 역시 이진 트리가 된다. n개의 노드로 구성된 이진 트리는 (n-1)개의 간선을 가지며, 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개며, 노드의 최대 개수는 (2^h+1 - 1)개가 되는 성질을 가진다. 이진 트리를 순차 자료구조 방식을 이용하여 표현하는 방법은 높이가 h인 포화이진트리의 노드 번호를 배열의 인덱스로 사용하여 1창원 배열로 표현하는 것이다. 1차원 배열에서 인덱스 계산을 간단히 하기 위해서 인덱스 0번은 실제로 사용하지 않고 비..

트리 - 트리에는 가장 상위 노드를 루트라 부른다. 여기선 2가 루트다 - 90은 50, 150의 부모고 반대로 50, 150은 90의 자식이다. - 트리는 레벨이 있다. 여기선 4 레벨이다 (맨위가 1 레벨) 이진 트리(+트리 특징) - 각 노드의 작식은 0개나 1개, 2개다. - 한 노드에 자식이 둘이면 한자식은 부모보다 작은 값을, 다른 자식은 부모보다 큰 값을 가져야한다. 검색 - 111을 찾는다고 가정하고 두 자식중 부모가 111보다 큰지 작은지 비교 후 조건에 맞는 자식에게 타고 들어가면서 찾고자하는 값을 찾는다. (여기선 111이 부모 90보다 크다 고로 우측 150으로 타고옴) - 이진 트리 검색은 O(log N) 단계이다. 삽입 - 100을 삽입한다고 가정하면 먼저 루트90부터 큰지 작은..