JavaScript data structures – trees

1. What is it?

Tree A hierarchical data structure. It is a hierarchical set of one or more nodes. It’s called a tree because it looks like a tree hanging upside down. The roots face up, the leaves face down. The node that has no parent node is called the root node. A node has only one parent, and a parent has several children.

2. Binary Search Tree (BST)

The left child of a node is smaller than its parent, and the right child of a node is larger than its parent.

2.1, the realization of binary search tree traversal, new, query, delete

function BinarySearchTree(){// Initialize the root node var root = null; // Create a Node class var Node =function(key) { this.key = key; this.left = null; this.right = null; }; // Create the node this.insert =function(key) {
            var node = new Node(key);
            if (root === null) {
                root = node;
            } else{ insertNode(root, node); }}; // Find the minimum value this.min =function() {
            var node = root;
            if (node) {
                while(node && node.left ! == null) { node = node.left; }return node.key;
            }
            returnnull; }; // Find the maximum this.max =function() {
            var node = root;
            if (node) {
                while(node && node.right ! == null) { node = node.right; }return node.key;
            }
            returnnull; }; // Find the specific value this.search =function(key) {
            returnsearchNode(root, key); }; // Delete the specified node this.remove =function(key) { root = removeNode(root, key); }; This.inordertraverse =function(callback) {
            inOrderTraverseNode(root, callback); }; // This. PreOrderTraverse =function(callback) { preOrderTraverseNode(root, callback); }; // Follow this. PostOrderTraverse =function(callback) { postOrderTraverseNode(root, callback); }; // Create a node helper classfunction insertNode(root, node) {
            if (node.key < root.key) {
                if (root.left === null) {
                    root.left = node;
                } else{ insertNode(root.left, node); }}else {
                if (root.right === null) {
                    root.right = node;
                } else{ insertNode(root.right, node); }}} // Find a specific value helper classfunction searchNode(node, key) {
            if (node) {
                if (key < node.key) {
                    return searchNode(node.left, key);
                } else if (key > node.key){
                    return searchNode(node.right, key);
                } else {
                    return true; }}else {
                return false; }} // Delete the specified value helper classfunction removeNode(node, key) {
            if (node === null) {
                return null;
            }
            if (key < node.key) {
                node.left = removeNode(node.left, key);
                return node;
            } else if (key > node.key) {
                node.right = removeNode(node.right, key);
                return node;
            } else{// In the first case, the deleted node has no child nodesif(node.left === null && node.right === null) {
                    node = null;
                    returnnode; } // In Chapter 2, the deleted node has a child nodeif(node.left === null) {
                    node = node.right;
                    return node;
                } else if (node.right === null) {
                    node = node.left;
                    returnnode; } var aux = findM; var aux = findM; var aux = findMinNode(node.right);
                node.key = aux.key;
                node.right = removeNode(node.right, aux.key);
                returnnode; }} // Find the minimum value of the nodefunction findMinNode(node) {
            while(node && node.left) {
                node = node.left;
            }
            returnnode; } // in order traversalfunction inOrderTraverseNode(node, callback) {
            if(node) { 
                inOrderTraverseNode(node.left, callback);
                callback(node.key);
                inOrderTraverseNode(node.right, callback); }} //function preOrderTraverseNode(node, callback) {
            if(node) { callback(node.key); preOrderTraverseNode(node.left, callback); preOrderTraverseNode(node.right, callback); }} //function postOrderTraverseNode(node, callback) {
            if(node) { 
                preOrderTraverseNode(node.left, callback);
                preOrderTraverseNode(node.right, callback);
                callback(node.key);
            }
        }
    }
    var tree = new BinarySearchTree();
    tree.insert(11);
    tree.insert(7);
    tree.insert(15);
    tree.insert(5);
    tree.insert(3);
    tree.insert(9);
    tree.insert(8);
    tree.insert(10);
    tree.insert(10);
    tree.insert(13);
    tree.insert(12);
    tree.insert(14);
    tree.insert(20);
    tree.insert(18);
    tree.insert(25);
    function printNode(value) {
        console.log(value);
    }
    // tree.inOrderTraverse(printNode);
    // tree.preOrderTraverse(printNode);
    // tree.postOrderTraverse(printNode);
    var min = tree.min();
    var max = tree.max();
    var search = tree.search(7);
    tree.remove(10);
    tree.inOrderTraverse(printNode);
Copy the code

3, binary search tree (BST) advantages

Binary tree combines the optimization of data query with the advantages of insertion and deletion of linked list. This is useful when dealing with large amounts of dynamic data. It helps to query, insert and delete data more efficiently.

4, binary search tree (BST) shortcomings

When the number of nodes is added, an edge may be very deep.

5. Solve the disadvantages of binary search tree (BST), self-balanced binary search tree (AVL)

When adding nodes in the self-balanced binary search tree, the hl of the left subtree and the height of the right subtree of each node in the AVL tree are calculated. If the difference between HR-HL is not one of 1, -1, or 0. The AVL tree needs to be balanced. This is the equilibrium factor. AVL rotation is used to balance AVL. To deal with the imbalance.