avl tree heap data structure c
このチュートリアルでは、理解を深めるためのAVLツリーの例とともに、C ++でのAVLツリーとヒープデータ構造の詳細な説明を提供します。
AVLツリーは高さのバランスが取れた二分木です。各ノードは、左側のサブツリーと右側のサブツリーの高さの差として計算されるバランスの取れた係数に関連付けられています。
AVLツリーは、2人の発明者、つまりG.M. Abelson-VelvetyとE.M.Landisは、1962年に彼らの論文「情報の組織化のためのアルゴリズム」で発表されました。
=> ここでC ++トレーニングシリーズ全体を探してください。
学習内容：
C ++のAVLツリー
ツリーのバランスをとるには、各ノードのバランス係数を-1から1の間にする必要があります。そうでない場合、ツリーは不均衡になります。
AVLツリーの例を以下に示します。
上記のツリーでは、左右のサブツリーの高さの差が1であることがわかります。これは、バランスの取れたBSTであることを意味します。バランス係数が1であるため、これは、左側のサブツリーが右側のサブツリーより1レベル高いことを意味します。
バランス係数が0の場合、左右のサブツリーが同じレベルにあることを意味します。つまり、それらのサブツリーの高さは同じです。バランス係数が-1の場合、左側のサブツリーは右側のサブツリーより1レベル低くなります。
AVLツリーは、二分探索木の高さを制御し、それが歪むのを防ぎます。二分木が歪むと、すべての操作で最悪の場合（O（n））になるためです。バランス係数を使用することにより、AVLツリーはバイナリツリーに制限を課し、すべての操作をO（log n）に保ちます。
AVLツリー操作
以下は、AVLツリーでサポートされている操作です。
IT管理ソフトウェアと監視ツール
＃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ツリーのインオーダートラバーサルは次のとおりです。
4 5 8 11 12 17 18
ノード5の削除後の順序どおりのトラバーサル：
4 8 11 12 17 18
プログラムでAVLツリーを示すために、上記のサンプルツリーを使用していることに注意してください。
AVL木のアプリケーション
- AVLツリーは、主にメモリ内の種類のセットや辞書に使用されます。
- AVLツリーは、挿入と削除が少ないが、必要なデータのルックアップが頻繁に行われるデータベースアプリケーションでも広く使用されています。
- データベースアプリケーションとは別に、検索の改善が必要なアプリケーションで使用されます 。
C ++でのHEAPデータ構造
C ++のヒープは、特別なツリーベースのデータ構造であり、完全なバイナリツリーです。
ヒープには次の2つのタイプがあります。
- 最小ヒープ ：最小ヒープでは、最小の要素はツリーのルートであり、各ノードはその親以上です。
- 最大ヒープ ：max-heapでは、最大の要素はツリーのルートであり、各ノードはその親以下です。
次の要素の配列について考えてみます。
10 20 30 40 50 60 70
上記のデータの最小ヒープを以下に示します。
上記のデータを使用した最大ヒープを以下に示します。
バイナリヒープC ++
バイナリヒープは、ヒープデータ構造の一般的な実装です。
バイナリヒープには次のプロパティがあります。
- おそらく最後のレベルを除いてすべてのレベルが完全に満たされ、最後のレベルのキーが可能な限り残っている場合、これは完全な二分木です。
- バイナリヒープは、最小ヒープまたは最大ヒープにすることができます。
バイナリヒープは完全なバイナリツリーであるため、配列として表すのが最適です。
バイナリヒープの配列表現を調べてみましょう。
次のバイナリヒープについて考えてみます。
上の図では、バイナリヒープのトラバーサルはレベルオーダーと呼ばれています。
したがって、上記のバイナリヒープの配列は、以下にHeapArrとして示されています。
上に示したように、HeapArr (0)はバイナリヒープのルートです。他の要素を一般的な用語で次のように表すことができます。
HeapArr (i)がiの場合thバイナリヒープ内のノード、次にiからの他のノードのインデックスthノードは次のとおりです。
- HeapArr (（i-1）/ 2) =>親ノードを返します。
- HeapArr (（2 * i）+1) =>左の子ノードを返します。
- HeapArr (（2 * i）+2) =>正しい子ノードを返します。
バイナリヒープは、以下の2つのタイプの「順序付けプロパティ」を満たします。
- 最小ヒーププロパティ： 最小値はルートにあり、各ノードの値はその親以上です。
- 最大ヒーププロパティ： 最大値はルートにあり、各ノードの値はその親以下です。
バイナリヒープの操作
以下は、最小ヒープで実行される基本的な操作です。最大ヒープの場合、それに応じて操作が逆になります。
＃1）Insert（） –ツリーの最後に新しいキーを挿入します。挿入されたキーの値によっては、ヒーププロパティに違反せずにヒープを調整する必要がある場合があります。
＃2）Delete（） –キーを削除します。 注意 ヒープの挿入操作と削除操作の両方の時間計算量はO（log n）です。
＃3）decreaseKey（） –キーの値を減らします。この操作が行われるとき、ヒーププロパティを維持する必要があるかもしれません。ヒープのdecreaseKey操作の時間計算量もO（log n）です。
＃4）extractMin（） –最小ヒープから最小要素を削除します。最小要素を削除した後、ヒーププロパティを維持する必要があります。したがって、その時間計算量はO（log n）です。
＃5）getMin（） –最小ヒープのルート要素を返します。これは最も単純な操作であり、この操作の時間計算量はO（1）です。
ヒープデータ構造の実装
以下に示すのは、最小ヒープの基本機能を示すための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: '< 出力：
挿入後のヒープ：2 4 6 8 10 12
ヒープのルート：2
deletekey（2）の後のヒープ：2 4 12 8 10
ヒープ内の最小要素：2
減少後のヒープの新しいルートKey：1
ヒープのアプリケーション
- ヒープソート： ヒープソートアルゴリズムは、バイナリヒープを使用して効果的に実装されます。
- 優先キュー： バイナリヒープは、O（log n）時間で優先キューを正常に実装するために必要なすべての操作をサポートします。
- グラフアルゴリズム： グラフに関連する一部のアルゴリズムは優先度付きキューを使用し、次に優先度付きキューはバイナリヒープを使用します。
- クイックソートアルゴリズムの最悪の場合の複雑さは、ヒープソートを使用することで克服できます。
結論
このチュートリアルでは、AVLツリーとヒープソートの2つのデータ構造を詳しく見てきました。
AVLツリーは、データベースのインデックス作成で主に使用されるバランスの取れたバイナリツリーです。
AVLツリーで実行されるすべての操作は、バイナリ検索ツリーの操作と似ていますが、AVLツリーの場合の唯一の違いは、バランス係数を維持する必要があることです。つまり、さまざまな操作の結果として、データ構造はバランスの取れたツリーのままである必要があります。これは、AVLツリーローテーション操作を使用して実現されます。
ヒープは、最小ヒープまたは最大ヒープに分類される完全なバイナリツリー構造です。最小ヒープのルートは最小要素であり、後続のノードは親ノード以上です。 max-heapでは、状況は正反対です。つまり、最大要素はヒープのルートです。
ヒープは、0の配列の形式で表すことができます。thツリーのルートとしての要素。ヒープデータ構造は、主にヒープソートと優先度付きキューを実装するために使用されます。
=> ゼロからC ++を学ぶには、ここにアクセスしてください。
推奨読書
