Avl Tree C++ Code

MUAZHAN

6 min read

·

Jun 28, 2024

17

Share

Implementasi AVL Tree dalam Bahasa C++

AVL Tree adalah struktur data pohon pencarian biner yang seimbang sendiri. Ini berarti bahwa pohon secara otomatis menyeimbangkan dirinya sendiri untuk memastikan bahwa ketinggian subtree kiri dan kanan dari setiap node tidak berbeda lebih dari 1, sehingga mempertahankan kompleksitas waktu logaritmik untuk operasi seperti penyisipan, penghapusan, dan pencarian.

Berikut adalah implementasi dasar AVL Tree dalam C++:

#include 

using namespace std;

// Node struktur untuk AVL Tree
struct Node {
    int data;
    int height;
    Node *left;
    Node *right;

    Node(int data) {
        this->data = data;
        this->height = 1;
        this->left = nullptr;
        this->right = nullptr;
    }
};

// Fungsi untuk mendapatkan tinggi node
int height(Node *node) {
    if (node == nullptr) {
        return 0;
    }
    return node->height;
}

// Fungsi untuk mendapatkan faktor keseimbangan node
int balanceFactor(Node *node) {
    if (node == nullptr) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

// Fungsi untuk melakukan rotasi kanan pada node yang diberikan
Node* rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    // Melakukan rotasi
    x->right = y;
    y->left = T2;

    // Memperbarui tinggi
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // Mengembalikan root baru
    return x;
}

// Fungsi untuk melakukan rotasi kiri pada node yang diberikan
Node* leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

    // Melakukan rotasi
    y->left = x;
    x->right = T2;

    // Memperbarui tinggi
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // Mengembalikan root baru
    return y;
}

// Fungsi untuk menyisipkan node baru ke dalam AVL Tree
Node* insert(Node* node, int data) {
    // Kasus dasar: pohon kosong
    if (node == nullptr) {
        return new Node(data);
    }

    // Jika data lebih kecil dari data node, sisipkan ke subtree kiri
    if (data < node->data) {
        node->left = insert(node->left, data);
    }
    // Jika data lebih besar dari data node, sisipkan ke subtree kanan
    else if (data > node->data) {
        node->right = insert(node->right, data);
    }
    // Jika data sudah ada, jangan sisipkan
    else {
        return node;
    }

    // Memperbarui tinggi node saat ini
    node->height = 1 + max(height(node->left), height(node->right));

    // Mendapatkan faktor keseimbangan untuk memeriksa apakah perlu dirotasi
    int balance = balanceFactor(node);

    // Kasus rotasi: LL
    if (balance > 1 && data < node->left->data) {
        return rightRotate(node);
    }

    // Kasus rotasi: RR
    if (balance < -1 && data > node->right->data) {
        return leftRotate(node);
    }

    // Kasus rotasi: LR
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // Kasus rotasi: RL
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // Tidak perlu rotasi
    return node;
}

// Fungsi untuk mencetak AVL Tree dalam bentuk inorder
void inorder(Node *root) {
    if (root != nullptr) {
        inorder(root->left);
        cout << root->data << " ";
        inorder(root->right);
    }
}

int main() {
    Node *root = nullptr;

    // Menyisipkan node
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    // Mencetak AVL Tree dalam bentuk inorder
    cout << "AVL Tree (Inorder): ";
    inorder(root);
    cout << endl;

    return 0;
}

Kode ini berisi fungsi untuk menyisipkan node baru ke dalam AVL Tree, menghitung tinggi dan faktor keseimbangan node, dan melakukan rotasi kiri dan kanan untuk menjaga keseimbangan pohon.

Cara Kerja:

• Fungsi insert menangani penginsertan node baru.
• Fungsi height dan balanceFactor menghitung tinggi dan faktor keseimbangan dari setiap node.
• Fungsi rightRotate dan leftRotate melakukan rotasi kanan dan kiri sesuai kebutuhan untuk menjaga keseimbangan pohon.

Keuntungan AVL Tree:

• Keseimbangan: AVL Tree selalu seimbang, sehingga memastikan kompleksitas waktu logaritmik untuk semua operasi.
• Pencarian efisien: Pencarian node dalam AVL Tree lebih efisien daripada pohon pencarian biner biasa.

Kekurangan AVL Tree:

• Kompleksitas implementasi: Implementasi AVL Tree lebih kompleks dibandingkan dengan pohon pencarian biner biasa.
• Overhead rotasi: Rotasi yang terjadi selama penginsertan atau penghapusan dapat menimbulkan overhead tambahan.

Implementasi ini adalah contoh dasar. Anda dapat memperluasnya dengan menambahkan fungsi untuk penghapusan, pencarian, dan operasi lainnya.