avl tree heap data structure c
이 자습서에서는 더 나은 이해를 위해 AVL 트리 예제와 함께 C ++의 AVL 트리 및 힙 데이터 구조에 대한 자세한 설명을 제공합니다.
AVL 트리는 높이 균형 이진 트리입니다. 각 노드는 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이로 계산되는 균형 요소와 연결됩니다.
AVL 트리는 두 발명가 즉 G.M. Abelson-Velvety와 E.M. Landis는 1962 년 논문“정보 조직을위한 알고리즘”에 발표되었습니다.
=> 여기에서 전체 C ++ 교육 시리즈를 찾아보십시오.
학습 내용 :
C ++의 AVL 트리
트리가 균형을 이루려면 각 노드의 균형 요소가 -1과 1 사이 여야합니다. 그렇지 않으면 트리가 균형이 맞지 않게됩니다.
AVL 트리의 예가 아래에 나와 있습니다.
애니메이션을 볼 수있는 웹 사이트
위의 트리에서 왼쪽 및 오른쪽 하위 트리의 높이 차이가 1임을 알 수 있습니다. 이는 균형 잡힌 BST임을 의미합니다. 밸런싱 팩터가 1이므로 왼쪽 하위 트리가 오른쪽 하위 트리보다 한 수준 높습니다.
균형 요소가 0이면 왼쪽 및 오른쪽 하위 트리가 동일한 수준에 있음을 의미합니다. 즉, 동일한 높이를 포함합니다. 균형 요소가 -1이면 왼쪽 하위 트리가 오른쪽 하위 트리보다 한 수준 낮습니다.
AVL 트리는 이진 검색 트리의 높이를 제어하고 왜곡되는 것을 방지합니다. 이진 트리가 치우쳐지면 모든 작업에 대해 최악의 경우 (O (n))이기 때문입니다. 균형 요소를 사용하여 AVL 트리는 이진 트리에 제한을 적용하므로 모든 작업이 O (log n)로 유지됩니다.
AVL 트리 작업
다음은 AVL 트리에서 지원하는 작업입니다.
# 1) AVL 트리 삽입
C ++ AVL 트리의 삽입 작업은 이진 검색 트리의 작업과 동일합니다. 유일한 차이점은 균형 요소를 유지하려면 균형이 맞지 않도록 트리를 왼쪽이나 오른쪽으로 회전해야한다는 것입니다.
# 2) AVL 트리 삭제
삭제 작업도 이진 검색 트리의 삭제 작업과 동일한 방식으로 수행됩니다. 다시 한 번 AVL 트리 회전을 수행하여 트리의 균형을 재조정해야합니다.
AVL 트리 구현
다음은 AVL 트리 및 해당 작업을 보여주는 C ++ 프로그램입니다.
// C++ program for AVL Tree #include using namespace std; // An AVL tree node class AVLNode { public: int key; AVLNode *left; AVLNode *right; int depth; }; //get max of two integers int max(int a, int b){ return (a > b)? a : b; } //function to get height of the tree int depth(AVLNode *n) { if (n == NULL) return 0; return n->depth; } // allocate a new node with key passed AVLNode* newNode(int key) { AVLNode* node = new AVLNode(); node->key = key; node->left = NULL; node->right = NULL; node->depth = 1; // new node added as leaf return(node); } // right rotate the sub tree rooted with y AVLNode *rightRotate(AVLNode *y) { AVLNode *x = y->left; AVLNode *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->depth = max(depth(y->left), depth(y->right)) + 1; x->depth = max(depth(x->left), depth(x->right)) + 1; // Return new root return x; } // left rotate the sub tree rooted with x AVLNode *leftRotate(AVLNode *x) { AVLNode *y = x->right; AVLNode *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->depth = max(depth(x->left), depth(x->right)) + 1; y->depth = max(depth(y->left), depth(y->right)) + 1; // Return new root return y; } // Get Balance factor of node N int getBalance(AVLNode *N) { if (N == NULL) return 0; return depth(N->left) - depth(N->right); } //insertion operation for node in AVL tree AVLNode* insert(AVLNode* node, int key) { //normal BST rotation if (node == NULL) return(newNode(key)); if (key key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys not allowed return node; //update height of ancestor node node->depth = 1 + max(depth(node->left), depth(node->right)); int balance = getBalance(node); //get balance factor // rotate if unbalanced // Left Left Case if (balance > 1 && key left->key) return rightRotate(node); // Right Right Case if (balance node->right->key) return leftRotate(node); // Left Right Case if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } // Right Left Case if (balance <-1 && key right->key) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } // find the node with minimum value AVLNode * minValueNode(AVLNode* node) { AVLNode* current = node; // find the leftmost leaf */ while (current->left != NULL) current = current->left; return current; } // delete a node from AVL tree with the given key AVLNode* deleteNode(AVLNode* root, int key) { if (root == NULL) return root; //perform BST delete if ( key key ) root->left = deleteNode(root->left, key); else if( key > root->key ) root->right = deleteNode(root->right, key); else { // node with only one child or no child if( (root->left == NULL) || (root->right == NULL) ) { AVLNode *temp = root->left ? root->left : root->right; if (temp == NULL) { temp = root; root = NULL; } else // One child case *root = *temp; free(temp); } else { AVLNode* temp = minValueNode(root->right); root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } } if (root == NULL) return root; // update depth root->depth = 1 + max(depth(root->left), depth(root->right)); // get balance factor int balance = getBalance(root); //rotate the tree if unbalanced // Left Left Case if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Left Right Case if (balance > 1 && getBalance(root->left) left = leftRotate(root->left); return rightRotate(root); } // Right Right Case if (balance right) <= 0) return leftRotate(root); // Right Left Case if (balance right)> 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } // prints inOrder traversal of the AVL tree void inOrder(AVLNode *root) { if(root != NULL) { inOrder(root->left); cout 산출:
AVL 트리의 Inorder traversal은 다음과 같습니다.
4 5 8 11 12 17 18
노드 5 삭제 후 Inorder traversal :
4 8 11 12 17 18
프로그램에서 AVL 트리를 보여주기 위해 위에 표시된 예제 트리를 사용했습니다.
AVL 트리의 응용
- AVL 트리는 주로 메모리 내 종류의 집합 및 사전에 사용됩니다.
- AVL 트리는 삽입 및 삭제가 적지 만 필요한 데이터를 자주 조회하는 데이터베이스 애플리케이션에서도 광범위하게 사용됩니다.
- 데이터베이스 응용 프로그램과 별도로 향상된 검색이 필요한 응용 프로그램에 사용됩니다. .
C ++의 HEAP 데이터 구조
C ++의 힙은 특별한 트리 기반 데이터 구조이며 완전한 이진 트리입니다.
힙은 두 가지 유형이 있습니다.
- 최소 힙 : min-heap에서 가장 작은 요소는 트리의 루트이고 각 노드는 상위 노드보다 크거나 같습니다.
- 최대 힙 : max-heap에서 가장 큰 요소는 트리의 루트이고 각 노드는 부모보다 작거나 같습니다.
다음 요소 배열을 고려하십시오.
10 20 30 40 50 60 70
위 데이터의 최소 힙은 다음과 같습니다.
위 데이터를 사용한 최대 힙은 다음과 같습니다.
바이너리 힙 C ++
이진 힙은 힙 데이터 구조의 일반적인 구현입니다.
바이너리 힙에는 다음과 같은 속성이 있습니다.
- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워지고 마지막 레벨에 가능한 한 많은 키가 남아있을 때 완전한 이진 트리입니다.
- 바이너리 힙은 최소 힙 또는 최대 힙일 수 있습니다.
이진 힙은 완전한 이진 트리이므로 배열로 가장 잘 표현할 수 있습니다.
바이너리 힙의 배열 표현을 살펴 보겠습니다.
vr box 용 최고의 vr 앱
다음 바이너리 힙을 고려하십시오.
위의 다이어그램에서 바이너리 힙에 대한 순회를 레벨 순서라고합니다.
따라서 위의 이진 힙에 대한 배열은 아래에 HeapArr로 표시됩니다.
위와 같이 HeapArr (0)은 바이너리 힙의 루트입니다. 다음과 같이 일반적인 용어로 다른 요소를 나타낼 수 있습니다.
HeapArr (i)가 i 인 경우일바이너리 힙의 노드, i에서 다른 노드의 인덱스일노드는 다음과 같습니다.
- HeapArr ((i-1) / 2) => 부모 노드를 반환합니다.
- HeapArr ((2 * i) +1) => 왼쪽 자식 노드를 반환합니다.
- HeapArr ((2 * i) +2) => 오른쪽 자식 노드를 반환합니다.
바이너리 힙은 아래와 같이 두 가지 유형의 '순서 속성'을 충족합니다.
- 최소 힙 속성 : 최소값은 루트에 있고 각 노드의 값은 부모보다 크거나 같습니다.
- 최대 힙 속성 : 최대 값은 루트에 있으며 각 노드의 값은 상위 노드보다 작거나 같습니다.
바이너리 힙에 대한 작업
다음은 최소 힙에서 수행되는 기본 작업입니다. 최대 힙의 경우 그에 따라 작업이 반대로 진행됩니다.
# 1) 삽입 () – 트리 끝에 새 키를 삽입합니다. 삽입 된 키의 값에 따라 힙 속성을 위반하지 않고 힙을 조정해야 할 수 있습니다.
# 2) 삭제 () – 키를 삭제합니다. 노트 힙의 삽입 및 삭제 작업의 시간 복잡도는 O (log n)입니다.
# 3) 감소 키 () – 키 값을 줄입니다. 이 작업이 수행 될 때 힙 속성을 유지해야 할 수도 있습니다. 힙의 reduceKey 연산의 시간 복잡도도 O (log n)입니다.
# 4) extractMin () – 최소 힙에서 최소 요소를 제거합니다. 최소 요소를 제거한 후 힙 속성을 유지해야합니다. 따라서 시간 복잡도는 O (log n)입니다.
# 5) getMin () – 최소 힙의 루트 요소를 반환합니다. 이것은 가장 간단한 작업이며이 작업의 시간 복잡도는 O (1)입니다.
힙 데이터 구조 구현
다음은 min-heap의 기본 기능을 보여주는 C ++ 구현입니다.
#include #include using namespace std; // swap two integers void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } // Min-heap class class Min_Heap { int *heaparr; // pointer to array of elements in heap int capacity; // maximum capacity of min heap int heap_size; // current heap size public: Min_Heap(int cap){ heap_size = 0; capacity = cap; heaparr = new int(capacity); } // to heapify a subtree with the root at given index void MinHeapify(int ); int parent(int i) { return (i-1)/2; } // left child of node i int left(int i) { return (2*i + 1); } // right child of node i int right(int i) { return (2*i + 2); } // extract minimum element in the heap(root of the heap) int extractMin(); // decrease key value to newKey at i void decreaseKey(int i, int newKey); // returns root of the min heap int getMin() { return heaparr(0); } // Deletes a key at i void deleteKey(int i); // Inserts a new key 'key' void insertKey(int key); void displayHeap(){ for(int i = 0;i heaparr(i)) { swap(&heaparr(i), &heaparr(parent(i))); i = parent(i); } } void Min_Heap::decreaseKey(int i, int newKey) { heaparr(i) = newKey; while (i != 0 && heaparr(parent(i)) > heaparr(i)) { swap(&heaparr(i), &heaparr(parent(i))); i = parent(i); } } int Min_Heap::extractMin() { if (heap_size <= 0) return INT_MAX; if (heap_size == 1) { heap_size--; return heaparr(0); } // Store the minimum value,delete it from heap int root = heaparr(0); heaparr(0) = heaparr(heap_size-1); heap_size--; MinHeapify(0); return root; } void Min_Heap::deleteKey(int i) { decreaseKey(i, INT_MIN); extractMin(); } void Min_Heap::MinHeapify(int i) { int l = left(i); int r = right(i); int min = i; if (l < heap_size && heaparr(l) < heaparr(i)) min = l; if (r < heap_size && heaparr(r) < heaparr(min)) min = r; if (min != i) { swap(&heaparr(i), &heaparr(min)); MinHeapify(min); } } // main program int main() { Min_Heap h(11); h.insertKey(2); h.insertKey(4); h.insertKey(6); h.insertKey(8); h.insertKey(10); h.insertKey(12); cout<<'Heap after insertion:'; h.displayHeap(); cout<<'root of the heap: '< 산출:
삽입 후 힙 : 24 6 8 10 12
힙의 루트 : 2
deletekey (2) 이후 힙 : 2 4 12 8 10
힙의 최소 요소 : 2
라우터의 사용자 이름과 비밀번호는 무엇입니까
reduceKey 후 힙의 새 루트 : 1
힙의 응용
- 힙 정렬 : 힙 정렬 알고리즘은 바이너리 힙을 사용하여 효과적으로 구현됩니다.
- 우선 순위 대기열 : 바이너리 힙은 O (log n) 시간에 우선 순위 큐를 성공적으로 구현하는 데 필요한 모든 작업을 지원합니다.
- 그래프 알고리즘 : 그래프와 관련된 일부 알고리즘은 우선 순위 대기열을 사용하고 우선 순위 대기열은 바이너리 힙을 사용합니다.
- 퀵 정렬 알고리즘의 최악의 복잡성은 힙 정렬을 사용하여 극복 할 수 있습니다.
결론
이 자습서에서는 AVL 트리와 힙 정렬이라는 두 가지 데이터 구조를 자세히 살펴 보았습니다.
AVL 트리는 주로 데이터베이스 인덱싱에 사용되는 균형 잡힌 이진 트리입니다.
AVL 트리에서 수행되는 모든 작업은 이진 검색 트리의 작업과 유사하지만 AVL 트리의 경우 유일한 차이점은 균형 요소를 유지해야한다는 것입니다. 이것은 AVL 트리 회전 작업을 사용하여 수행됩니다.
힙은 최소 힙 또는 최대 힙으로 분류되는 완전한 이진 트리 구조입니다. Min-heap은 루트로 최소 요소를 가지며 후속 노드는 상위 노드보다 크거나 같습니다. max-heap에서 상황은 정반대입니다. 즉, 최대 요소가 힙의 루트입니다.
힙은 0이있는 배열 형태로 표현 될 수 있습니다.일요소를 트리의 루트로 사용합니다. 힙 데이터 구조는 주로 힙 정렬 및 우선 순위 큐를 구현하는 데 사용됩니다.
=> 처음부터 C ++를 배우려면 여기를 방문하십시오.
추천 도서
