Binary Tree (2) 썸네일형 리스트형 Tree - Binary Search Tree , heap 이진 탐색 트리 탐색작업을 효율적으로 하기 위한 자료 구조 모든 원소는 다른 키를 가짐 key(왼쪽 서브트리) 오른차순으로 정렬된 값을 얻을 수 있음 탐색 연산 루트에서 시작 키 값 x 루트노드 키 값 r - x = r : 원하는 원소이므로 탐색연산 성공 - x r : 루트노드의 오른쪽 서브트리에 대해 탐색연산 서브트리에 대해 순환적으로 탐색 연산을 반복하기 삽입 연산 탐색연산을 수행하다 탐색 실패한 위치에 원소 삽입 검색 알고리즘의 시간복잡도 검색 알고리즘 시간 복잡도 (정렬된) 배열에서의 순차 검색 O(N) 정렬된 배열에서의 이진탐색 (고정.. Tree - Binary Tree 트리란 비선형 구조 원소들 간 1:n관계를 가짐 계층형 자료구조 상위에서 하위로 내려가며 확장되는 구조 subtree : 루트를 제외하고 나머지 노드들은 분리 집합이 되며, 이를 루트의 부트리(subtree)라 함 node : 트리의 원소 edge(간선) : 노드를 연결하는 선. 부모 노드와 자식 노드를 연결 sibling node : 형제 노드. 같은 부모 노드의 자식 노드들 ex) B,C,D는 형제 노드 조상 노드 : 루트 노드까지 이르는 경로에 있는 모든 노드들 ex) K의 조상 노드 : F,B,A 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 ex) B의 자손 노드 : E,F,K degree - 노드의 차수 : 노드에 연결된 자식 노드의 수 ex) B의 차수:2, C의 차수:1 - 트리의 차.. 이전 1 다음
