기술 블로그

[알고리즘] 이진 검색 트리

여러 개의 키 저장INSERT, SEARCH, DELETE여러 개의 키를 저장하고 검색, 삽입, 삭제 작업을 효율적으로 수행하기 위해 다양한 자료구조가 사용됩니다. 아래는 배열과 연결 리스트를 사용할 경우, 정렬 여부에 따른 시간 복잡도를 정리한 표입니다:자료구조정렬여부SearchInsertDelete배열 (Array)정렬됨O(log n)O(n)O(n)배열 (Array)정렬되지 않음O(n)O(1), O(n)O(1)연결 리스트 (Linked List)정렬됨O(n)O(n)O(1)연결 리스트 (Linked List)정렬되지 않음O(n)O(1)O(1)🔍 배열이나 연결 리스트를 사용하는 경우, 정렬 여부와 상관없이 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n)의 시간 복잡도를 가집니다. 이..

트리

트리 루트(Root): 트리 구조에서 가장 위에 있는 노드입니다.부모-자식 관계: 한 노드 아래에 연결된 노드를 ‘자식 노드’라고 하며, 연결 위쪽의 노드를 ‘부모 노드’라고 합니다.형제 노드: 동일한 부모를 가진 노드들을 형제(sibling)라고 합니다.리프(Leaf) 노드: 자식 노드가 없는 노드입니다. 트리의 말단에 위치합니다.조상-자손 관계: 부모-자식 관계를 확장한 개념으로, 조상은 부모의 부모까지 포함하며, 자손은 자식의 자식까지 모두 포함합니다. 이진트리이진트리는 모든 노드가 최대 두 개의 자식 노드를 가지는 트리입니다. 각각의 자식 노드는 왼쪽 자식(left child) 또는 오른쪽 자식(right child)으로 구분됩니다. 자식이 하나뿐인 경우에도 해당 자식이 왼쪽인지 오른쪽인지를 명확..