জাভাস্ক্রিপ্টে বাইনারি সার্চ ট্রি ক্লাস

এখানে BinarySearchTree ক্লাসের পূর্ণ বাস্তবায়ন দেওয়া হলো:

উদাহরণ

class BinarySearchTree {
    constructor() {
        // একটি রুট এলিমেন্ট নাল দিয়ে ইনিশিয়ালাইজ করুন।
        this.root = null;
    }
    insertIter(data) {
        let node = new this.Node(data);
        // চেক করুন ট্রি খালি কিনা
        if (this.root === null) {
            // প্রথম উপাদান হিসেবে ইনসার্ট করুন
            this.root = node;
            return;
        }
        let currNode = this.root;
        while (true) {
            if (data < currNode.data) {
                // এখানে ভ্যালু সেট করুন কারণ আমরা লীফ নোডে পৌঁছেছি
                if (currNode.left === null) {
                    currNode.left = node;
                    break;
                } else {
                    currNode = currNode.left;
                }
            } else {
                // এখানে ভ্যালু সেট করুন কারণ আমরা লীফ নোডে পৌঁছেছি
                if (currNode.right === null) {
                    currNode.right = node;
                    break;
                } else {
                    currNode = currNode.right;
                }
            }
        }
    }
    insertRec(data) {
        let node = new this.Node(data);
        // চেক করুন ট্রি খালি কিনা
        if (this.root === null) {
            // প্রথম উপাদান হিসেবে ইনসার্ট করুন
            this.root = node;
        } else {
            insertRecHelper(this.root, node);
        }
    }
    searchIter(data) {
        let currNode = this.root;
        while (currNode !== null) {
            if (currNode.data === data) {
                // উপাদানটি পাওয়া গেল!
                return true;
            } else if (data < currNode.data) {
                // ডেটা প্যারেন্ট থেকে ছোট হলে বামে যান
                currNode = currNode.left;
            } else {
                // ডেটা প্যারেন্ট থেকে বড় হলে ডানে যান
                currNode = currNode.right;
            }
        }
        return false;
    }
    searchRec(data) {
        return searchRecHelper(data, this.root);
    }
    getMinVal() {
        if (this.root === null) {
            throw "Empty tree!";
        }
        let currNode = this.root;
        while (currNode.left !== null) {
            currNode = currNode.left;
        }
        return currNode.data;
    }
    getMaxVal() {
        if (this.root === null) {
            throw "Empty tree!";
        }
        let currNode = this.root;
        while (currNode.right !== null) {
            currNode = currNode.right;
        }
        return currNode.data;
    }
    deleteNode(key) {
        return !(deleteNodeHelper(this.root, key) === false);
    }
    inOrder() {
        inOrderHelper(this.root);
    }
    preOrder() {
        preOrderHelper(this.root);
    }
    postOrder() {
        postOrderHelper(this.root);
    }
}
BinarySearchTree.prototype.Node = class {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
};
// HELPER METHODS
function preOrderHelper(root) {
    if (root !== null) {
        console.log(root.data);
        preOrderHelper(root.left);
        preOrderHelper(root.right);
    }
}
function inOrderHelper(root) {
    if (root !== null) {
        inOrderHelper(root.left);
        console.log(root.data);
        inOrderHelper(root.right);
    }
}
function postOrderHelper(root) {
    if (root !== null) {
        postOrderHelper(root.left);
        postOrderHelper(root.right);
        console.log(root.data);
    }
}
function insertRecHelper(root, node) {
    if (node.data < root.data) {
        // এখানে ভ্যালু সেট করুন কারণ আমরা লীফ নোডে পৌঁছেছি
        if (root.left === null) {
            root.left = node;
        } else {
            insertRecHelper(root.left, node);
        }
    } else {
        // এখানে ভ্যালু সেট করুন কারণ আমরা লীফ নোডে পৌঁছেছি
        if (root.right === null) {
            root.right = node;
        } else {
            insertRecHelper(root.right, node);
        }
    }
}
function searchRecHelper(data, root) {
    if (root === null) {
        // লীফে পৌঁছালাম কিন্তু পায়নি।
        return false;
    }
    if (data < root.data) {
        return searchRecHelper(data, root.left);
    } else if (data > root.data) {
        return searchRecHelper(data, root.right);
    }
    // এর মানে উপাদানটি পাওয়া গেল
    return true;
}
/**
 * রুট এবং কি নেয় এবং রিকারসিভলি কিটি খুঁজে বের করে।
 * যদি কিটি পাওয়া যায়, তবে ৩টি কেস হতে পারে:
 * ১. এই নোডটি একটি লীফ নোড।
 * ২. এই নোডটি ট্রির মাঝপথে একটু চাইল্ডসহ।
 * ৩. এই নোডের দুটি চাইল্ড আছে। এটি একটি ট্রিকি কেস।
 */
function deleteNodeHelper(root, key) {
    if (root === null) {
        // খালি ট্রি
        return false;
    }
    if (key < root.data) {
        root.left = deleteNodeHelper(root.left, key);
        return root;
    } else if (key > root.data) {
        root.right = deleteNodeHelper(root.right, key);
        return root;
    } else {
        // কোনো চাইল্ড নেই
        // কেস ১ - একটি লীফ নোড
        if (root.left === null && root.right === null) {
            root = null;
            return root;
        }
        // সিঙ্গল চাইল্ড কেস
        if (root.left === null) return root.right;
        if (root.right === null) return root.left;
        // দুটি চাইল্ড, সুতরাং সাকসেসর খুঁজতে হবে
        let currNode = root.right;
        while (currNode.left !== null) {
            currNode = currNode.left;
        }
        root.data = currNode.data;
        // ডান সাবট্রি থেকে ভ্যালু ডিলিট করুন।
        root.right = deleteNodeHelper(root.right, currNode.data);
        return root;
    }
}