3.js-树

非顺序数据结构：散列表、树（存储需要快速查找的数据）
节点的的深度取决于它的祖先节点数量，树的高度取决于所有节点深度的最大值
1.二叉搜索树（BST）是二叉树的一种，但它只允许左侧节点存储比父节点值小，右侧节点存储比父节点大

//代码实现
//创建BinarySearchTree
function BinarySearchTree(){
    let Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
    let root = null;
    this.insert = function(key){
        let node = new Node(key);
        if(root === null){
            root = node;
        }else{
            insertNode(root,node)
        }
    }
    //遍历只实现中序遍历
    this.inOrderTraverse = function(printNode){
        inOrderTraverseNode(root,printNode)
    }
    //查找特定值
    this.select = function(key){
        return selectkey(root,key)
    }
    //移除一个节点
    this.remove = function(key){
        //这里的返回值是处理要删除节点的父节点指向的，比如5的右指针指向6，删除6之后除了将6设置为null,还需要将5的左指针设置为null
        //原因：let a = {},b = a; a = null; 此时的b为{},原因是改变了a的指向为null;b指向的堆内存并没有改变还是原来的
        //在处理链表的时候，也遇到过这个问题，仅仅赋一个null是不够的，还需要除了前驱指向
        root = removeNode(root,key)
    }
}
function 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)
        }
    }
}

function inOrderTraverseNode(node,printNode){
    if(node !== null){
        inOrderTraverseNode(node.left,printNode);
        printNode(node.key);
        inOrderTraverseNode(node.right,printNode)
    }
   
}
function selectkey(root,key){
    if(root === null) return false;
    if(key < root.key){
        return selectkey(root.left,key)
    }else if(key > root.key){
        return selectkey(root.right,key)
    }else{
        return true;
    }
}
function removeNode(root,key){
    if(root === null) return false;
    if(key <  root.key){
        root.left = removeNode(root.left,key)
        return root;
    }else if(key > root.key){
        root.right = removeNode(root.right,key)
        return root;
    }else{
        if(root.left === null && root.right === null){
            root = null;
            return root
        }else if(root.left === null){
            root = root.right
            return root
        }else if(root.right === null){
            root = root.left
            return root;
        }else{
            //左节点和右节点都不为空的情况下，找到右节点中的最小节点替换该元素
            let minNode = findMiniNode(root.right);
            root.key = minNode.key;
            root.right = removeNode(root.right,minNode.key)
            return root
        }
    }
}

function findMiniNode(root){
    while(root.left){
        root = root.left
    }
    return root
}

let tree = new BinarySearchTree();
tree.insert(4);
tree.insert(2);
tree.insert(1);
tree.insert(3);
tree.insert(5);
// tree.inOrderTraverse((key)=>{
//     console.log(key)
// })
// console.log(tree.select(4))
tree.remove(2)
tree.inOrderTraverse((key)=>{
    console.log(key)
})

2.自平衡树（AVL）添加或移除节点的时候，AVL树会尝试自平衡。任意一个节点的左子树和右子树高度最多相差1

//代码实现
function BinarySearchTree(){
    let Node = function(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
    let root = null;
    this.insert = function(key){
        let node = new Node(key);
        if(root === null){
            root = node;
        }else{
            root = insertNode(root,node)
        }
    }
    //只实现先序遍历
    this.preOrderTraverse = function(printNode){
        preOrderTraverseNode(root,printNode)
    }
}
function insertNode(root,node){
    //AVL树的不同之处在于我们需要检验它的平衡因子，如果有需要，则将其逻辑应用于树的自平衡
    if(node.key < root.key){
        if(root.left === null){
            root.left = node
        }else{
            //平衡因子的计算是需要节点插入完成之后计算的，所以这里需要返回
            root.left = insertNode(root.left,node)
        }
        if(root.left !== null){
            //确认是否需要平衡
            if((heightNode(root.left) - heightNode(root.right)) > 1){
                if(node.key < root.left.key){
                   root = rotationLL(root)
                }else{
                    root = rotationLR(root)
                }
            }
        }
    }else{
        if(root.right === null){
            root.right = node
        }else{
            root.right=insertNode(root.right,node)
        }
        if(root.right !== null){
            //确认是否需要平衡
            if((heightNode(root.right) - heightNode(root.left)) > 1){
                if(node.key > root.right.key){
                    root = rotationRR(root)
                }else{
                    root = rotationRL(root)
                }
            }
        }
    }
    return root
}
function preOrderTraverseNode(node,printNode){
    if(node !== null){
        printNode(node.key);
        preOrderTraverseNode(node.left,printNode);
        preOrderTraverseNode(node.right,printNode)
    }
   
}
//该函数为计算树高度的函数，每递归一层，则深度+1，如果当前节点的右子树比左子树深，即该树的高度为 右子树的高度
function heightNode(root){
    if(root === null){
        // 返回-1的原因是，计算树的高度时候，（不计算根节点所在层，根节点所在是第0层），
        // 在这里计算树的高的时候是相反的
        // 叶子节点所在的为0层，而叶子的上一级（父节点）为1,在上一级为2..以此类推
        return -1
    }else{
        return Math.max(heightNode(root.left),heightNode(root.right))+1
    }
}
//实现左旋 RR:(以当前节点为根，第一个R指当前节点的右子树（tr），第二个R指右子树（tr）的右子树）
//需要左旋是由于在当前节点的右子树的右子树的子树插入了一个节点
function rotationRR(root){
    let tmp = root.right
    root.right = tmp.left;
    tmp.left = root;
    return tmp
}
//实现右旋LL:需要右旋是由于在当前节点的左子树的左子树的子树插入了一个节点
function rotationLL(root){
    let tmp = root.left
    root.left = tmp.right;
    tmp.right = root;
    return tmp
}
//先右旋后左旋RL：需要先右旋后左旋的原因是因为在当前节点的右子树的左子树插入了一个节点（先将右子树右旋，再将当前节点左旋）
function rotationRL(root){
    root.right = rotationLL(root.right)
    return rotationRR(root);
}
//先左旋后右旋LR：需要先左旋后右旋的原因是因为在当前节点的左子树的右子树插入了一个节点（先将左子树左旋，再将当前节点右旋）
function rotationLR(root){
    root.left = rotationRR(root.left)
    return rotationLL(root);
}

let tree = new BinarySearchTree();
//测试左旋
// tree.insert(4);
// tree.insert(2);
// tree.insert(1);
// tree.insert(3);
// tree.insert(5);
//测试右旋
// tree.insert(5);
// tree.insert(4);
// tree.insert(3);
// tree.insert(2);
// tree.insert(1);
//测试LR
// tree.insert(10);
// tree.insert(7);
// tree.insert(14);
// tree.insert(5);
// tree.insert(9);
// tree.insert(8);
//测试RL
tree.insert(10);
tree.insert(7);
tree.insert(14);
tree.insert(13);
tree.insert(18);
tree.insert(12);
//这里用先序遍历测试
tree.preOrderTraverse((key)=>{
    console.log(key)
})