BST-ро ба дарахти дуӣ табдил диҳед, ба тавре ки ҷамъи ҳамаи калидҳои бузургтар ба ҳар як тугма илова карда шавад


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Facebook
Дарахти ҷустуҷӯи бинарӣ Дарахти дуӣ Дарахт

Бо дарахти ҷустуҷӯи бинарӣ дода шуда, алгоритми тағир додани BST ба дуӣ бинависед Дарахт ба тавре ки ҷамъи ҳамаи калидҳои бузургтар ба ҳар як калид илова карда мешавад.

мисол

вуруди

BST-ро ба дарахти дуӣ табдил диҳед, ба тавре ки ҷамъи ҳамаи калидҳои бузургтар ба ҳар як тугма илова карда шавад

Натиҷаи

BST-ро ба дарахти дуӣ табдил диҳед, ба тавре ки ҷамъи ҳамаи калидҳои бузургтар ба ҳар як тугма илова карда шавад

Пешакӣ фармоиш: 81 87 88 54 69 34

Усули соддалавҳона

Идея хеле содда аст, бӯриш ҳама гиреҳҳоро як ба як ва барои ҳар як гиреҳ дубора тамоми дарахтро убур кунед ва ҷамъи гиреҳҳои аз он бузургтарро пайдо кунед. Ҷамъро дар массив нигоҳ доред ва пас аз ҳисобкунӣ, барои ҳамаи гиреҳҳо суммаро афзоиш диҳед ва гиреҳҳоро бо суммаи мувофиқи худ афзоиш диҳед. Ин равиш барои ҳама дарахтони дуӣ умумӣ ва махсусан барои BST татбиқ карда мешавад.

  1. БСТ-и додашударо ба тариқи тартиб гузаред.
  2. Барои ҳар як гиреҳ, дарахтро бо тартиби навбатӣ убур кунед ва ҷамъи ҳамаи гиреҳҳоро, ки аз гиреҳи ҷорӣ бузургтаранд, ёбед.
  3. Маблағро дар массив ё рӯйхат нигоҳ доред.
  4. Пас аз гузаштани ҳамаи гиреҳҳо, дарахтро бо тартиби муқаррарӣ убур кунед ва ҳар гиреҳро бо суммаи мувофиқи он дар массив ё рӯйхат афзоиш диҳед.

Мураккабии вақт = О (н2)
Мураккабии фазо = О (ч)
ки дар он n шумораи гиреҳҳо дар дарахт аст.

Кодекси JAVA барои табдил додани BST ба дарахти дуӣ

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class ConvertABSTToABinaryTreeSuchThatSumOfAllGreaterKeysIsAddedToEveryKey {
    // class representing the node of a binary tree
    static class Node {
        int data;
        Node left, right;

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

    // function to print the 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);
        }
    }

    private static int findSum(Node root, int value) {
        // if root is null, sum is 0
        if (root == null) {
            return 0;
        }

        // initialize sum as 0
        int sum = 0;

        // traverse the tree and find the sum of all the values greater than value
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            if (curr.data > value) {
                sum += curr.data;
            }

            if (curr.left != null)
                queue.add(curr.left);
            if (curr.right != null)
                queue.add(curr.right);
        }

        // return sum
        return sum;
    }

    private static void formSumList(Node root, Node curr, ArrayList<Integer> sumList) {
        // traverse the tree in in-order form and for each node
        // calculate the sum of elements greater than it
        if (curr != null) {
            formSumList(root, curr.left, sumList);

            // Check for all the nodes to find the sum
            int sum = findSum(root, curr.data);
            sumList.add(sum);

            formSumList(root, curr.right, sumList);
        }
    }

    private static void  convertToGreaterSumTree(Node root, ArrayList<Integer> sumList) {
        // traverse the tree in in-order form and for each node
        // increment its value by sum
        if (root != null) {
            convertToGreaterSumTree(root.left, sumList);

            // increment this value
            root.data += sumList.get(0);
            sumList.remove(0);

            convertToGreaterSumTree(root.right, sumList);
        }
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(12);
        root.left = new Node(6);
        root.right = new Node(20);
        root.left.left = new Node(1);
        root.right.left = new Node(15);
        root.right.right =  new Node(34);

        ArrayList<Integer> sumList = new ArrayList<>();
        formSumList(root, root, sumList);

        convertToGreaterSumTree(root, sumList);

        preOrder(root);
        System.out.println();
    }
}
81 87 88 54 69 34

Кодекси C ++ барои табдил додани BST ба дарахти дуӣ

#include <iostream> 
#include<vector> 
#include<queue> 
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 the preorder traversal of a binary tree 
void preOrder(Node *root) { 
    if (root != NULL) { 
        cout<<root->data<<" "; 
        preOrder(root->left); 
        preOrder(root->right); 
    } 
} 

int findSum(Node *root, int value) { 
    // if root is null, sum is 0 
    if (root == NULL) { 
        return 0; 
    } 
    
    // initialize sum as 0 
    int sum = 0; 
    
    // traverse the tree and find the sum of all the values greater than value 
    queue<Node*> q; 
    q.push(root); 
    while (!q.empty()) { 
        Node *curr = q.front(); 
        q.pop(); 
        if (curr->data > value) { 
            sum += curr->data; 
        } 
        if (curr->left != NULL) { 
            q.push(curr->left); 
        } 
        if (curr->right != NULL) { 
            q.push(curr->right); 
        } 
    } 
    
    // return sum 
    return sum; 
} 

void formSumList(Node *root, Node *curr, vector<int> &sumList) { 
    // traverse the tree in in-order form and for each node 
    // calculate the sum of elements greater than it 
    if (curr != NULL) { 
        formSumList(root, curr->left, sumList); 
        
        // Check for all the nodes to find the sum 
        int sum = findSum(root, curr->data); 
        sumList.push_back(sum); 
        formSumList(root, curr->right, sumList); 
    } 
} 

void convertToGreaterSumTree(Node *root, vector<int> &sumList) { 
    // traverse the tree in in-order form and for each node 
    // replace its value with the corresponding sum 
    if (root != NULL) { 
        convertToGreaterSumTree(root->left, sumList); 
        // change this value 
        root->data += sumList[0]; 
        sumList.erase(sumList.begin()); 
        convertToGreaterSumTree(root->right, sumList); 
    } 
} 

int main() { 
    // Example Tree 
    Node *root = new Node(12); 
    root->left = new Node(6); 
    root->right = new Node(20); 
    root->left->left = new Node(1); 
    root->right->left = new Node(15); 
    root->right->right = new Node(34); 
    
    vector<int> sumList; 
    formSumList(root, root, sumList); 
    
    convertToGreaterSumTree(root, sumList); 
    preOrder(root); 
    cout<<endl; 
    
    return 0; 
}
81 87 88 54 69 34

Усули оптималӣ

Усули дар боло овардашударо барои BST оптималӣ кардан мумкин аст, зеро BST маълумотро бо усули мушаххас нигоҳ медорад.
БСТ-ро бо тартиби баръакс, яъне рост-> root-> шакли чап убур кунед. Бо ин роҳ мо гиреҳҳоро бо тартиби камшавӣ убур хоҳем кард ва пеш аз боздид ба ягон гиреҳ гиреҳҳоеро, ки аз он бузургтаранд, дидан хоҳем кард, аз ин рӯ мо метавонем ҷамъи ҳамаи гиреҳҳоро аз гиреҳ бузургтар аз танҳо як гардиш пайдо кунем ва аз ин рӯ дар ин афзоиши гардиш ҳар гиреҳ бо ҷамъи гиреҳҳо аз он бузургтар.

  1. Маблағи тағирёбандаро ҳамчун 0 оғоз кунед, он тавассути истинод гузаронида мешавад ё дар саросари ҷаҳон муайян карда мешавад.
  2. BST-ро бо тартиби баръакс убур кунед, бо ин роҳ мо маълумотро бо тартиби камшумор мегирем.
  3. Барои ҳар як гиреҳе, ки мо мегузарем, арзиши онро ба маблағ афзоиш диҳед ва ҷамъро бо арзиши аслии гиреҳ афзоиш диҳед (пеш аз навсозӣ).

Мураккабии вақт = Эй (н)
Мураккабии фазо = О (ч)
ки дар он n шумораи умумии гиреҳҳо дар BST-и додашуда мебошад.

Кодекси JAVA барои табдил додани BST ба дарахти дуӣ

public class ConvertABSTToABinaryTreeSuchThatSumOfAllGreaterKeysIsAddedToEveryKey {
    // 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 the 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);
        }
    }

    // sum defined globally and initialized as 0
    private static int sum = 0;

    private static void convertToGreaterSumTree(Node root) {
        // traverse the tree in reverse in-order form
        if (root != null) {
            convertToGreaterSumTree(root.right);

            // update the sum and increment the node's value
            int prevValue = root.data;
            root.data += sum;
            sum += prevValue;

            convertToGreaterSumTree(root.left);
        }
    }

    public static void main(String[] args) {
        // Example Tree
        Node root = new Node(12);
        root.left = new Node(6);
        root.right = new Node(20);
        root.left.left = new Node(1);
        root.right.left = new Node(15);
        root.right.right =  new Node(34);

        convertToGreaterSumTree(root);

        preOrder(root);
        System.out.println();
    }
}
81 87 88 54 69 34

Кодекси C ++ барои табдил додани BST ба дарахти дуӣ

#include <iostream>
#include<vector>
#include<queue>
using namespace std;

// sum defined globally and initialized as 0
int sum = 0;

// 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 the preorder traversal of a binary tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

void convertToGreaterSumTree(Node *root) {
    // traverse the tree in reverse in-order form
    if (root != NULL) {
        convertToGreaterSumTree(root->right);
        
        // update the sum and the node's value
        int prevValue = root->data;
        root->data += sum;
        sum += prevValue;
        
        convertToGreaterSumTree(root->left);
    }
}

int main() {
    // Example Tree
    Node *root = new Node(12);
    root->left = new Node(6);
    root->right = new Node(20);
    root->left->left = new Node(1);
    root->right->left = new Node(15);
    root->right->right =  new Node(34);

    convertToGreaterSumTree(root);

    preOrder(root);
    cout<<endl;
    
    return 0;
}
81 87 88 54 69 34

Маълумот1     истинод2