Mündəricat
Problem bəyanat
İkili Axtarış Ağacını (BST) nəzərə alaraq, BST-ni Balanslı İkili Axtarış Ağacına çevirmək üçün bir alqoritm yazın. Balanslaşdırılmış İkili Axtarış ağacı, sol alt ağac ilə sağ alt ağacın hündürlüyü arasındakı fərq 1-dən az və ya bərabər olan ikili axtarış ağacından başqa bir şey deyildir.
Nümunələr
Input
Buraxılış
Ön sifariş: 31 17 3 23 48 45 50 62
Input
Buraxılış
Ön sifariş: 8 7 9
Normal BST-nin balanslaşdırılmış BST-yə çevrilməsi alqoritmi
Bir yanaşma, verilmiş ikili axtarış ağacını nizamlı bir şəkildə keçmək və elementləri özünə bənzəyən bir ağacda saxlamaq olar. AVL ağacı ya da qırmızı-qara bir ağac. Bu yanaşma o qədər də səmərəli deyil, O (N log N) vaxt aparır və O (N) əlavə yer istifadə edir.
Verilən problem, sıralanmış bir sıra içərisindən balanslaşdırılmış ikili axtarış ağacının qurulmasına bənzəyir və sıralanmış bir sıra və ya siyahının balanslı ikili axtarış ağacına necə çevriləcəyini bilirik. Verilən məsələyə daha yaxından baxsaq, problemi sıralanmış bir sıra içərisindən balanslı ikili axtarış ağacının qurulmasına çevirə bilərik.
Fikir verilmiş BST-ni nizamlı keçidlə keçmək və qovşaqları bir sıra içində saxlamaqdır. Massivdə verilənlər sıralanmış qaydada olacaqdır. Sonra sıralanmış massivi balanslaşdırılmış vəziyyətə gətiririk ikili axtarış ağacı.
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.
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi = O (n), çünki bütün ağacları gəzirik n qovşaqlar. Bu alqoritm üçün xətti zaman mürəkkəbliyimiz var.
Kosmik Mürəkkəblik = O (n), çünki ölçülü bir sıra istifadə edirik n ikili axtarış ağacının inorder keçişini saxlamaq üçün.
burada n - verilən ikili axtarış ağacındakı qovşaq sayı.
Normal BST-nin balanslaşdırılmış BST-yə çevrilməsi üçün JAVA kodu
/* 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
Normal BST-nin balanslaşdırılmış BST-yə çevrilməsi üçün C ++ kodu
#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
