Scribd Logo
Upload

Welcome to Scribd!

  • 14 views

    Avl WSTR

    Uploaded by

    Barath
    This C++ program implements functions for an AVL self-balancing binary search tree including node creation, insertion, deletion, rotation, height calculation, and traversal. It creates an example AVL tree, performs insertions and deletions, and prints the inorder traversal before and after a node is removed.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd

    Avl WSTR

    Uploaded by

    Barath
    14 views4 pages
    This C++ program implements functions for an AVL self-balancing binary search tree including node creation, insertion, deletion, rotation, height calculation, and traversal. It creates an example AVL tree, performs insertions and deletions, and prints the inorder traversal before and after a node is removed.

    Original Title

    avl wstr

    Copyright

    © © All Rights Reserved

    Available Formats

    TXT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This C++ program implements functions for an AVL self-balancing binary search tree including node creation, insertion, deletion, rotation, height calculation, and traversal. It creates an example AVL tree, performs insertions and deletions, and prints the inorder traversal before and after a node is removed.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    14 views4 pages

    Avl WSTR

    Uploaded by

    Barath
    This C++ program implements functions for an AVL self-balancing binary search tree including node creation, insertion, deletion, rotation, height calculation, and traversal. It creates an example AVL tree, performs insertions and deletions, and prints the inorder traversal before and after a node is removed.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    of 4

    #include <iostream>

    using namespace std;

    // AVL Tree Node


    class Node {
    public:
    int key;
    Node* left;
    Node* right;
    int height;
    };

    // Calculate height of a node


    int height(Node* node) {
    if (node == nullptr) return 0;
    return node->height;
    }

    // Calculate balance factor of a node


    int balanceFactor(Node* node) {
    if (node == nullptr) return 0;
    return height(node->left) - height(node->right);
    }

    // Create a new node with the given key


    Node* newNode(int key) {
    Node* node = new Node();
    node->key = key;
    node->left = nullptr;
    node->right = nullptr;
    node->height = 1;
    return node;
    }

    // Rotate right subtree rooted with y


    Node* rotateRight(Node* y) {
    Node* x = y->left;
    Node* T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

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

    return x;
    }

    // Rotate left subtree rooted with x


    Node* rotateLeft(Node* x) {
    Node* y = x->right;
    Node* T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;
    // Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
    }

    // Insert a key into the AVL tree


    Node* insert(Node* root, int key) {
    // Perform standard BST insert
    if (root == nullptr) return newNode(key);

    if (key < root->key)


    root->left = insert(root->left, key);
    else if (key > root->key)
    root->right = insert(root->right, key);
    else // Duplicate keys not allowed
    return root;

    // Update height of this ancestor node


    root->height = 1 + max(height(root->left), height(root->right));

    // Get the balance factor


    int balance = balanceFactor(root);

    // Perform rotations if needed


    if (balance > 1 && key < root->left->key)
    return rotateRight(root);

    if (balance < -1 && key > root->right->key)


    return rotateLeft(root);

    if (balance > 1 && key > root->left->key) {


    root->left = rotateLeft(root->left);
    return rotateRight(root);
    }

    if (balance < -1 && key < root->right->key) {


    root->right = rotateRight(root->right);
    return rotateLeft(root);
    }

    return root;
    }

    // Get the node with the minimum key value


    Node* minValueNode(Node* node) {
    Node* current = node;
    while (current->left != nullptr)
    current = current->left;
    return current;
    }

    // Delete a key from the AVL tree


    Node* deleteNode(Node* root, int key) {
    if (root == nullptr) return root;

    if (key < root->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 == nullptr || root->right == nullptr) {
    Node* temp = root->left ? root->left : root->right;

    // No child case
    if (temp == nullptr) {
    temp = root;
    root = nullptr;
    } else // One child case
    *root = *temp;

    delete temp;
    } else {
    // Node with two children, get the inorder successor
    Node* temp = minValueNode(root->right);

    // Copy the inorder successor's data to this node


    root->key = temp->key;

    // Delete the inorder successor


    root->right = deleteNode(root->right, temp->key);
    }
    }

    if (root == nullptr) return root;

    // Update height of the current node


    root->height = 1 + max(height(root->left), height(root->right));

    // Get the balance factor


    int balance = balanceFactor(root);

    // Perform rotations if needed


    if (balance > 1 && balanceFactor(root->left) >= 0)
    return rotateRight(root);

    if (balance > 1 && balanceFactor(root->left) < 0) {


    root->left = rotateLeft(root->left);
    return rotateRight(root);
    }

    if (balance < -1 && balanceFactor(root->right) <= 0)


    return rotateLeft(root);

    if (balance < -1 && balanceFactor(root->right) > 0) {


    root->right = rotateRight(root->right);
    return rotateLeft(root);
    }

    return root;
    }

    // Inorder traversal of the AVL tree


    void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
    }

    int main() {
    Node* root = nullptr;

    root = insert(root, 10);


    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    cout << "Inorder traversal of the AVL tree: ";


    inorder(root);
    cout << endl;

    root = deleteNode(root, 30);

    cout << "Inorder traversal after deletion of 30: ";


    inorder(root);
    cout << endl;

    return 0;
    }

    You might also like