Μετατροπή ενός κανονικού BST σε Balanced BST


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις American Express ByteDance Capital One Grofers Intel Splunk Zoho
Δυαδικό δέντρο αναζήτησης Δυαδικό δέντρο Δέντρο

Δήλωση προβλήματος

Δεδομένου ενός δέντρου δυαδικής αναζήτησης (BST), γράψτε έναν αλγόριθμο για να μετατρέψετε το BST σε ένα δέντρο ισορροπημένης δυαδικής αναζήτησης. Ένα ισορροπημένο δέντρο δυαδικής αναζήτησης δεν είναι τίποτα άλλο από ένα δέντρο δυαδικής αναζήτησης του οποίου η διαφορά μεταξύ του ύψους του αριστερού και του δεξιού υποδέντρου είναι μικρότερη ή ίση με 1.

Παραδείγματα

Εισαγωγή

Μετατροπή ενός κανονικού BST σε Balanced BST

Παραγωγή

Μετατροπή ενός κανονικού BST σε Balanced BST

Προπαραγγελία: 31 17 3 23 48 45 50 62

Εισαγωγή

Μετατροπή ενός κανονικού BST σε Balanced BST

Παραγωγή

Μετατροπή ενός κανονικού BST σε Balanced BST

Προπαραγγελία: 8 7 9

 

Αλγόριθμος για τη μετατροπή ενός κανονικού BST σε ισορροπημένο BST

Μία προσέγγιση θα μπορούσε να είναι να διασχίσουμε το δεδομένο δέντρο δυαδικής αναζήτησης με τάξη και να αποθηκεύσουμε τα στοιχεία σε ένα δέντρο αυτο-εξισορρόπησης, όπως Δέντρο AVL ή ένα κόκκινο-μαύρο δέντρο. Αυτή η προσέγγιση δεν είναι πολύ αποτελεσματική, παίρνει χρόνο O (N log N) και χρησιμοποιεί επιπλέον χώρο O (N).

Το δεδομένο πρόβλημα είναι παρόμοιο με τη δημιουργία ενός ισορροπημένου δυαδικού δέντρου αναζήτησης από έναν ταξινομημένο πίνακα και ξέρουμε πώς να μετατρέψουμε έναν ταξινομημένο πίνακα ή μια λίστα σε ένα ισορροπημένο δυαδικό δέντρο αναζήτησης. Εάν ρίξουμε μια ματιά πιο κοντά στο δεδομένο πρόβλημα, μπορούμε να μετατρέψουμε το πρόβλημα σε κατασκευή ενός ισορροπημένου δέντρου δυαδικής αναζήτησης από έναν ταξινομημένο πίνακα.

Η ιδέα είναι να διασχίσετε το δεδομένο BST σε διαδοχική σειρά και να αποθηκεύσετε τους κόμβους σε έναν πίνακα. Ο πίνακας θα περιέχει τα δεδομένα σε ταξινομημένη σειρά. Στη συνέχεια μετατρέπουμε τον ταξινομημένο πίνακα σε ισορροπημένο δυαδικό δέντρο αναζήτησης.

1. Traverse the given binary search tree in in-order traversal and store the nodes in an array, let the array be inOrderNodes.
2. The middle element of the array forms the root of the balanced BST and all the elements to the left of middle element forms the left sub-tree and all the elements to the right of middle element forms the right sub-tree.
3. Make root's left as the result of a recursive call for step 2. For left sub-tree the start index is start in step 2 and end index is mid - 1.
4. Make root's right as the result of a recursive call for step 2. For right sub-tree the start index is mid + 1 and end index is end in step 2.
5. Return root.

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας = Επί), αφού διασχίζουμε ολόκληρο το δέντρο που έχει κόμβοι. Έχουμε γραμμική πολυπλοκότητα χρόνου για αυτόν τον αλγόριθμο.
Διαστημική πολυπλοκότητα = Επί), γιατί χρησιμοποιούμε μια σειρά μεγεθών n για την αποθήκευση της ενδοπεριφοράς του δέντρου δυαδικής αναζήτησης.
όπου n είναι ο αριθμός των κόμβων στο δεδομένο δυαδικό δέντρο αναζήτησης.

Κωδικός JAVA για τη μετατροπή ενός κανονικού BST σε ισορροπημένο BST

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

import java.util.ArrayList;
class ConvertANormalBSTToBalancedBST {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;
        public Node(int data) {
            this.data = data;
        }
    }
    // function to print pre-order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    // function to store the in-order traversal of a binary tree to an array
    private static void storeInOrderTraversal(Node root, ArrayList<Integer> inOrderNodes) {
        if (root != null) {
            storeInOrderTraversal(root.left, inOrderNodes);
            inOrderNodes.add(root.data);
            storeInOrderTraversal(root.right, inOrderNodes);
        }
    }
    private static Node convertSortedArrayToBalancedBST(ArrayList<Integer> inOrderNodes, int start, int end) {
        // Base Case
        if (start > end) {
            return null;
        }
        // middle element of the array forms the node
        int mid = (start + end) / 2;
        Node root = new Node(inOrderNodes.get(mid));
        // elements to the left of middle element forms left subtree
        root.left = convertSortedArrayToBalancedBST(inOrderNodes, start, mid - 1);
        // elements to the right of middle element forms right subtree
        root.right = convertSortedArrayToBalancedBST(inOrderNodes, mid + 1, end);
        // return root
        return root;
    }
    private static Node convertToBalancedBST(Node root) {
        // create an array
        ArrayList<Integer> inOrderNodes = new ArrayList<>();
        // store the in-order traversal in the array
        storeInOrderTraversal(root, inOrderNodes);
        // make balanced BST from sorted array
        return convertSortedArrayToBalancedBST(inOrderNodes, 0, inOrderNodes.size() - 1);
    }
    public static void main(String[] args) {
        // Example 1
        Node root1 = new Node(50);
        root1.left = new Node(23);
        root1.right = new Node(62);
        root1.left.left = new Node(17);
        root1.left.right = new Node(45);
        root1.left.left.left = new Node(3);
        root1.left.right.left = new Node(31);
        root1.left.right.right = new Node(48);
        root1 = convertToBalancedBST(root1);
        preOrder(root1);
        System.out.println();
        // Example 2
        Node root2 = new Node(7);
        root2.right = new Node(8);
        root2.right.right = new Node(9);
        root2 = convertToBalancedBST(root2);
        preOrder(root2);
        System.out.println();
    }
}
31 17 3 23 48 45 50 62 
8 7 9

Κωδικός C ++ για τη μετατροπή ενός κανονικού BST σε ισορροπημένο BST

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

// function to print pre-order traversal of a binary tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// function to store the in-order traversal of a binary tree to an array
void storeInOrderTraversal(Node *root, vector<int> &inOrderNodes) {
    if (root != NULL) {
        storeInOrderTraversal(root->left, inOrderNodes);
        inOrderNodes.push_back(root->data);
        storeInOrderTraversal(root->right, inOrderNodes);
    }
}

Node* convertSortedArrayToBalancedBST(vector<int> &inOrderNodes, int start, int end) {
    // Base Case
    if (start > end) {
        return NULL;
    }
    
    // middle element of the array forms the node
    int mid = (start + end) / 2;
    Node *root = new Node(inOrderNodes[mid]);
    
    // elements to the left of middle element forms left subtree
    root->left = convertSortedArrayToBalancedBST(inOrderNodes, start, mid - 1);
    // elements to the right of middle element forms right subtree
    root->right = convertSortedArrayToBalancedBST(inOrderNodes, mid + 1, end);
    
    // return root
    return root;
}

Node* convertToBalancedBST(Node *root) {
    // create an array
    vector<int> inOrderNodes;
    // store the in-order traversal in the array
    storeInOrderTraversal(root, inOrderNodes);
    
    // make balanced BST from sorted array
    return convertSortedArrayToBalancedBST(inOrderNodes, 0, inOrderNodes.size() - 1);
}

int main() {
    // Example 1
    Node *root1 = new Node(50);
    root1->left = new Node(23);
    root1->right = new Node(62);
    root1->left->left = new Node(17);
    root1->left->right = new Node(45);
    root1->left->left->left = new Node(3);
    root1->left->right->left = new Node(31);
    root1->left->right->right = new Node(48);
    root1 = convertToBalancedBST(root1);
    preOrder(root1);
    cout<<endl;

    // Example 2
    Node *root2 = new Node(7);
    root2->right = new Node(8);
    root2->right->right = new Node(9);
    root2 = convertToBalancedBST(root2);
    preOrder(root2);
    cout<<endl;
    
    return 0;
}
31 17 3 23 48 45 50 62 
8 7 9