BST ກັບຕົ້ນໄມ້ທີ່ມີ Sum of Aller Keys  



ຖາມເລື້ອຍໆໃນ Bloomberg Drishti ອ່ອນ Microsoft ServiceNow Twitter Zopper
ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ ຕົ້ນໄມ້ຖານສອງ ຕົ້ນໄມ້ Traversal ຕົ້ນໄມ້

ໃນບັນຫານີ້ພວກເຮົາໄດ້ໃຫ້ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ, ຂຽນ an ຂັ້ນຕອນວິທີ ການປ່ຽນທີ່ດີທີ່ສຸດເປັນ ເປັນໄມ້ຢືນຕົ້ນ ພ້ອມດ້ວຍກະແຈນ້ອຍທັງ ໝົດ.

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ

BST ກັບຕົ້ນໄມ້ທີ່ມີ Sum of Aller KeysPin

ຜົນຜະລິດ

BST ກັບຕົ້ນໄມ້ທີ່ມີ Sum of Aller KeysPin

ສັ່ງກ່ອນໄດ້ກ່ອນ: 19 7 1 54 34 88

ວິທີການ Naive  

ຕາມທາງ ທຸກໆຂໍ້ຂອງແຕ່ລະຂໍ້ໃນແຕ່ລະຮູບແບບ, ແລະ ສຳ ລັບແຕ່ລະ node ອີກຄັ້ງລ້ຽວຂ້າມຕົ້ນໄມ້ທັງ ໝົດ ແລະພົບຜົນລວມຂອງຂໍ້ທັງ ໝົດ ທີ່ນ້ອຍກວ່າມັນ. ເກັບຄ່າລວມນີ້ໄວ້ ສຳ ລັບທຸກໆ node ໃນ array, ເພີ່ມຂື້ນທຸກໆ node ພ້ອມກັບ sums ທີ່ສອດຄ້ອງກັນ. ວິທີການນີ້ແມ່ນໃຊ້ໄດ້ກັບຕົ້ນໄມ້ໄບນາລີທົ່ວໄປແລະບໍ່ແມ່ນໂດຍສະເພາະ ສຳ ລັບ BST.

  1. ລອກເອົາແບບ BST ຕາມແບບຕາມ ລຳ ດັບ.
  2. ສຳ ລັບແຕ່ລະ node, ອີກເທື່ອ ໜຶ່ງ ຈະຂ້າມຕົ້ນໄມ້ໃນຮູບແບບໃດກໍ່ຕາມແລະຊອກຫາຜົນລວມຂອງຂໍ້ທັງ ໝົດ ທີ່ນ້ອຍກວ່າ node ປັດຈຸບັນ.
  3. ເກັບຮັກສາຍອດລວມໄວ້ເປັນແຖວຫລືລາຍຊື່.
  4. ຫຼັງຈາກທີ່ຜ່ານເສັ້ນກ່າງທັງ ໝົດ, ໃຫ້ຂ້າມຕົ້ນໄມ້ຕາມ ລຳ ດັບ (ຕ້ອງເປັນແບບດຽວກັບຂັ້ນຕອນທີ 1) ແລະເພີ່ມທຸກຮຸ່ນພ້ອມກັບຜົນບວກທີ່ສອດຄ້ອງກັນໃນແຖວຫລືບັນຊີລາຍຊື່.

ຄວາມສັບສົນເວລາ = ໂອ (ນ2)
ຄວາມສັບສົນໃນອະວະກາດ = O (h)
ບ່ອນທີ່ n ແມ່ນຕົວເລກຂອງຂໍ້ໃນຕົ້ນໄມ້.

ລະຫັດ JAVA ສຳ ລັບການສ້າງ Tree with Sum of all Smaller Keys

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

public class BSTToATreeWithSumOfAllSmallerKeys {
    // 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();
    }
}
19 7 1 54 34 88

ລະຫັດ C ++ ສຳ ລັບການສ້າງ Tree with Sum of all Smaller Keys

#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 the pre-order 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
    // increment its value by sum
    if (root != NULL) {
        convertToGreaterSumTree(root->left, sumList);
        
        // increment 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;
}
19 7 1 54 34 88

ວິທີການທີ່ດີທີ່ສຸດ  

ລອກເອົາແບບ BST ໃນຮູບແບບຕາມ ລຳ ດັບ, ນັ້ນແມ່ນເບື້ອງຊ້າຍ -> ຮາກ -> ຮູບແບບທີ່ຖືກຕ້ອງ. ດ້ວຍວິທີນີ້ພວກເຮົາຈະຂ້າມຜ່ານຂໍ້ມູນຕາມລໍາດັບທີ່ເພີ່ມຂື້ນແລະກ່ອນທີ່ຈະໄປຢ້ຽມຢາມ node ໃດກໍ່ຕາມພວກເຮົາຈະໄປຢ້ຽມຢາມ node ທີ່ນ້ອຍກວ່າມັນ, ເພາະສະນັ້ນພວກເຮົາສາມາດຊອກຫາຜົນລວມຂອງ node ທັງ ໝົດ ທີ່ນ້ອຍກວ່າ node ໃນພຽງ traversal ແລະເພາະສະນັ້ນໃນໄລຍະ traversal ນີ້ເພີ່ມທຸກໆ node ໂດຍຜົນລວມຂອງຂໍ້ທີ່ນ້ອຍກວ່າມັນ.

  1. ເລີ່ມຕົ້ນຜົນລວມຕົວປ່ຽນເປັນ 0, ມັນຖືກສົ່ງຜ່ານເອກະສານອ້າງອີງຫລື ກຳ ນົດທົ່ວໂລກ.
  2. Traverse BST ໃນແບບຟອມຄໍາສັ່ງ, ໃນວິທີການນີ້ພວກເຮົາຈະໄດ້ຮັບຂໍ້ມູນໃນການເພີ່ມຂື້ນຂອງລໍາດັບ.
  3. ສຳ ລັບແຕ່ລະ node ທີ່ພວກເຮົາຜ່ານໄປ, ເພີ່ມມູນຄ່າຂອງມັນໂດຍ sum, ແລະ sum increment ໂດຍຄ່າຕົ້ນສະບັບຂອງ node (ກ່ອນທີ່ຈະອັບເດດ).
ເບິ່ງ
ກວດເບິ່ງວ່າຕົ້ນໄມ້ຖານສອງທີ່ມອບໃຫ້ແມ່ນແລ້ວຫຼືບໍ່

ຄວາມສັບສົນເວລາ = O (n)
ຄວາມສັບສົນໃນອະວະກາດ = O (h)
ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນທັງ ໝົດ ຂອງຂໍ້ໃນ BST ທີ່ໃຫ້.

ລະຫັດ JAVA ສຳ ລັບການສ້າງ Tree with Sum of all Smaller Keys

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

    // 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.left);

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

            convertToGreaterSumTree(root.right);
        }
    }

    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();
    }
}
19 7 1 54 34 88

ລະຫັດ C ++ ສຳ ລັບການສ້າງ Tree with Sum of all Smaller Keys

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

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

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

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;
}
19 7 1 54 34 88

ເອກະສານ