עץ בינארי מאוזן


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית בלומברג Google מיקרוסופט
עץ בינארי עומק חיפוש ראשון רקורסיה עֵץ

בבעיית העץ הבינארי המאוזן, נתנו את השורש של a עץ בינארי. עלינו לקבוע האם מדובר באיזון גובה או לא.

דוגמאות

קֶלֶט

עץ בינארי מאוזן

תְפוּקָה

נכון

קֶלֶט

עץ בינארי מאוזן

פלט:

שקר

עץ בינארי מאוזן

כל צומת בבינארי מאוזן עץ יש הבדל של 1 או פחות בין גובה עץ העץ השמאלי והימני. עץ ריק תמיד עוקב אחרי איזון הגובה.
כלומר, עבור עץ בינארי מאוזן,
-1 <= גובה עץ העץ השמאלי - גובה העץ הימני <= 1

גישה נאיבית לעץ בינארי מאוזן

כדי שכל צומת יחשב את גובה העץ השמאלי והימני שלו, אם ההפרש גדול מ -1, החזירו שקר, אחרת תחזרו לעץ העץ השמאלי והימני שלו והחזירו אמת אם שניהם מאוזנים, בכל המקרים האחרים מחזירים שקר.
מקרה יסוד: עץ ריק עוקב אחרי איזון הגובה.

  1. התחל מהשורש. אם השורש הוא אפס, החזירו אמת.
  2. חשב את גובה עץ העץ השמאלי והימני שלו ואחסן אותם במשתנים בשם שמאל גובה וימין גובה בהתאמה.
  3. התקשרו רקורסיבית לפונקציית גובה האיזון לעץ המשנה הימני והשמאלי של השורש. אם שני העצים השמאליים והימניים מאוזנים וההבדל בין גובה שמאל לימין גובה קטן או שווה ל- 1, החזיר אמת, אחרת השב כוזב.

מורכבות זמן = O (n ^ 2)

קוד JAVA

public class BalancedBinaryTree {
    static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Function to calculate height of a tree rooted at root
    private static int height(Node root) {
        if (root == null) {
            // Height of empty tree is 0
            return 0;
        }
        // Height of tree is 1 + maximum of height of left or right subtree
        return 1 + Math.max(height(root.left), height(root.right));
    }

    // Function to check if given tree is balanced or not
    private static boolean isBalanced(Node root) {
        if (root == null) {
            // Empty tree is always balanced
            return true;
        }

        // Find the left subtree height and right subtree height
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);

        // If this node is balanced and also its left and right subtree are balanced return true
        // else return false
        return (Math.abs(leftHeight - rightHeight) <= 1) && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public static void main(String[] args) {
        // Tree in example 1
        Node root = new Node(18);
        root.left = new Node(4);
        root.right = new Node(20);
        root.right.left = new Node(13);
        root.right.right = new Node(70);

        System.out.println(isBalanced(root));

        // Tree in example 2
        Node root2 = new Node(3);
        root2.left = new Node(4);
        root2.right = new Node(8);
        root2.left.left = new Node(5);
        root2.left.right = new Node(9);
        root2.right.right = new Node(7);
        root2.right.right.left = new Node(6);

        System.out.println(isBalanced(root2));
    }
}

קוד C ++

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
    if (root == NULL) {
        // Height of empty tree is 0
        return 0;
    }
    // Height of tree is 1 + maximum of height of left or right subtree
    return 1 + std::max(height(root->left), height(root->right));
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
    if (root == NULL) {
        // Empty tree is always balanced
        return true;
    }

    // Find the left subtree height and right subtree height
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    // If this node is balanced and also its left and right subtree are alanced return true
    // else return false
    return (abs(leftHeight - rightHeight) <= 1) && isBalanced(root->left)
            && isBalanced(root->right);
}

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

int main() {
  // Tree in example 1
    Node *root = newNode(18);
    root->left = newNode(4);
    root->right = newNode(20);
    root->right->left = newNode(13);
    root->right->right = newNode(70);

    if (isBalanced(root) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Tree in example 2
    Node* root2 = newNode(3);
    root2->left = newNode(4);
    root2->right = newNode(8);
    root2->left->left = newNode(5);
    root2->left->right = newNode(9);
    root2->right->right = newNode(7);
    root2->right->right->left = newNode(6);

    if (isBalanced(root2) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}
true
false

גישה אופטימלית לעץ בינארי מאוזן

שנה את פונקציית הגובה כדי להחזיר את גובה העץ אם העץ מסופק על מאפייני איזון הגובה אחר להחזיר -1.

  1. העץ הריק נמצא תמיד בעקבות איזון הגובה (Base Case).
  2. מצא את הגובה השמאלי על ידי קריאת פונקציית הגובה רקורסיבית, אם הגובה הוא -1, עץ המשנה השמאלי אינו מאוזן, החזר -1 באופן מיידי.
  3. מצא את הגובה הנכון על ידי קריאת פונקציית הגובה רקורסיבית, אם הגובה הוא -1, עץ המשנה הנכון הוא לא מאוזן להחזיר -1 באופן מיידי.
  4. אם ההבדל בין גובה שמאל לימין קטן או שווה ל- 1, החזר את הגובה (1 + מקסימום (leftHeight, rightHeight), אחרת החזר -1.

מורכבות זמן = O (n)

קוד JAVA

public class BalancedBinaryTree {
    static class Node {
        int data;
        Node left;
        Node right;

        public Node(int data) {
            this.data = data;
            left = right = null;
        }
    }

    // Modified height function
    // Returns the height of tree if the tree is balanced and returns -1 is the tree is not balanced
    private static int height(Node root) {
        if (root == null) {
            // Empty tree is always balanced
            return 0;
        }

        // Find the left height
        int lh = height(root.left);
        if (lh == -1) {
            // Left subtree is unbalanced
            return -1;
        }
        // Find the right height
        int rh = height(root.right);
        if (rh == -1) {
            // Right subtree is unbalanced
            return -1;
        }
        if (Math.abs(lh - rh) <= 1) {
            // Balanced tree, return the height
            return Math.max(lh, rh) + 1;
        }
        // Unbalanced tree
        return -1;
    }

    private static boolean isBalanced(Node root) {
        // Call the modified height function
        int height = height(root);
        if (height == -1) {
            // Unbalanced tree
            return false;
        }
        // Balanced tree
        return true;
    }

    public static void main(String[] args) {
        // Tree in example 1
        Node root = new Node(18);
        root.left = new Node(4);
        root.right = new Node(20);
        root.right.left = new Node(13);
        root.right.right = new Node(70);

        System.out.println(isBalanced(root));

        // Tree in example 2
        Node root2 = new Node(3);
        root2.left = new Node(4);
        root2.right = new Node(8);
        root2.left.left = new Node(5);
        root2.left.right = new Node(9);
        root2.right.right = new Node(7);
        root2.right.right.left = new Node(6);

        System.out.println(isBalanced(root2));
    }
}

קוד C ++

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
};

// Function to calculate height of a tree rooted at root
int height(Node *root) {
    if (root == NULL) {
        // Empty tree is always balanced
        return 0;
    }
    // Find the left height
    int lh = height(root->left);
    if (lh == -1) {
        // Left subtree is unbalanced
        return -1;
    }
    // Find the right height
    int rh = height(root->right);
    if (rh == -1) {
        // Right subtree is unbalanced
        return -1;
    }
    if (abs(lh - rh) <= 1) {
        // Balanced tree, return the height
        return 1 + std::max(height(root->left), height(root->right));
    }
    // Unbalanced tree
    return -1;
}

// Function to check if given tree is balanced or not
bool isBalanced(Node *root) {
    // Call the modified height function
    int h = height(root);
    if (h == -1) {
        // Unbalanced tree
        return false;
    }
    // Balanced tree
    return true;
}

// Function to allocate new memory to a tree node
Node* newNode(int data) { 
    Node *node = new Node(); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL;
  
    return (node); 
}

int main() {
  // Tree in example 1
    Node *root = newNode(18);
    root->left = newNode(4);
    root->right = newNode(20);
    root->right->left = newNode(13);
    root->right->right = newNode(70);

    if (isBalanced(root) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Tree in example 2
    Node* root2 = newNode(3);
    root2->left = newNode(4);
    root2->right = newNode(8);
    root2->left->left = newNode(5);
    root2->left->right = newNode(9);
    root2->right->right = newNode(7);
    root2->right->right->left = newNode(6);

    if (isBalanced(root2) == true) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    return 0;
}
true
false

הפניות