반응형 Computer Science/자료구조11 균형 탐색 트리 (AVL)에 대하여 이번 포스트에서는 이전 포스트의 이진탐색트리의 보완버전인 균형탐색트리 (AVL)에 대하여 포스트 하도록 하겠습니다. 균형탐색트리(AVL Tree) AVL 트리는 각 노드의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1 이하인 이진탐색트리입니다. 삽입과 삭제 과정에서 높이차가 1 이상인 경우가 발생하면, 트리 회전을 통해 균형을 맞추는 동작을 수행합니다. 이 과정에서 각 노드의 높이 차를 저장하기 위해 각 노드는 균형 인자를 가집니다. 균형인자는 노드의 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값을 가집니다. 공백 트리의 경우에는 -1로 정의됩니다. 따라서, AVL 트리는 균형인자가 -1, 0, 1 중 하나의 값을 가져야 합니다. 트리의 불균형 AVL 트리에서 불균형은 다음 4가지로.. 2023. 9. 5. 이진 탐색 트리에 대하여 이번 포스트에서는 이진트리 중 어떤 성질을 만족하는 이진트리인 이진 탐색 트리를 포스팅하겠습니다. 이진탐색트리 이진트리는 다음 4가지 성질을 만족하는 이진 트리로 정의됩니다. 모든 원소는 유일한 키(value)를 가진다. 왼쪽 서브트리 내 키들은 루트의 키보다 작다. 오른쪽 서브트리 내 키들은 루트의 키보다 크다. 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리이다. 위 성질을 가진 이진탐색트리를 중위순회 하게 되면 오름차순 목록을 얻을 수 있습니다. 이진탐색트리의 구현 이진탐색트리의 연산중 먼저 삽입연산입니다. 이진탐색트리의 4가지 성질을 만족하게 끔, 입력받은 키값을 각 노드들과 비교하며 입력받은 키의 위치를 찾아 삽입합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 Node* create.. 2023. 9. 3. 비선형 자료구조 (트리) 이번 포스트에서는 트리에 대한 내용과 이진 트리의 순회방법에 대해 포스팅하겠습니다. 트리 트리란, 한개 이상의 노드로 이루어진 유한집합으로 각 노드들은 루트 노드와 나머지 노드들의 분리 집합으로 이루어 집니다. 이때, 각 집합은 하나의 트리이고, 이를 루트의 서브트리라고 부릅니다. 위 설명으로 이루어 볼때, 트리는 재귀적 형태를 띄고 있다는걸 확인할 수 있습니다. 트리는 후에 설명할 그래프 자료구조의 일종으로, 반사관계, 대칭관계, 추이관계 중 추이관계만을 성립하는 관계입니다. 따라서, 트리는 위에서 아래로 일정한 방향으로 진행하는 모양을 띄고 역으로 거슬러서 올라갈 수 없습니다. 이진트리 이진트리는 공집합이거나, 루트와 왼쪽 서브트리, 오른쪽 서브트리로 분리되어 두 개의 이진트리로 구성된 노드의 유한집.. 2023. 8. 29. 연결리스트와 선형 자료구조 (2) 지난 포스트에 이어 이번 포스트에서는 양방향 연결리스트의 구현에 대해서 소개하도록 하겠습니다. 연결리스트의 노드생성 먼저 연결리스트에서의 노드 생성입니다. 다음 코드는 연결리스트 뿐만아니라, 노드의 형태를 가지는 자료구조 (트리, 그래프) 등에서 적절히 내용을 수정하여 사용해도 무관합니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Node* createNode(int data) { //더미리스트를 사용한 양방향 연결리스트에서의 노드생성. Node* p = (Node*)malloc(sizeof(Node)); p->data = data; p->prev = p->next = p; return p; } Node* createNode(int data) { //더미.. 2023. 8. 24. 이전 1 2 3 다음 반응형