JavaScript(ES6)数据结构与算法之树-Toy模板网

这篇具有很好参考价值的文章主要介绍了JavaScript(ES6)数据结构与算法之树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

6. 树

6.1 概念

非线性结构
n(n>=0)个节点构成的有限集合，n=0时称为空树

对于任一非空树
- 有一个根节点
- 其余节点可以构成子树
树的术语：
- 节点的度：节点的子树个数
- 树的度：树所有节点中最大的度数
- 叶节点/叶子节点：度为零的节点
- 父节点：有子树的的节点是子树根节点的父节点
- 路径和路径长度：节点n1到nk的路径为一个节点序列，路径长度即所包含边的个数
- 节点层次：根节点在1层，往下层数递增
- 树的深度：所有节点中的最大层次

6.2 二叉树

所有的树本质上可以使用二叉树模拟出来（将树进行旋转就能得到二叉树）

概念：
- 如果树的每个节点最多只能有两个子节点，这样的树就是二叉树
- 二叉树可以为空（没有节点）
- 由根节点、左子树、右子树组成
- 一共有五种形态：空树、单根节点、只有左/右子树、具有左右子树
重要特性（笔试常见）
- 二叉树第i层的最大节点数为：2^(i-1)，i>=1;
- 深度为k的二叉树最大节点总数：2^k-1，k>=1;
- 任何非空二叉树，叶子节点个数n0和其他节点（度为2）个数n2满足：n0=n2+1
完全二叉树：除最后一层，其他各层节点数都达到最大个数（子节点个数要么0要么2）
完美二叉树/满二叉树：除最下一层的叶节点外，每层节点都有2个子节点，是特殊的完全二叉树
二叉树的存储
- 常见方式：数组和链表
  - 数组：完全二叉树，从上至下，从左到右；非完全二叉树，方案相同但造成很大空间浪费
  - （最常用）链表：每个节点封装一个node，node中包含存储的数据，左右节点的引用

6.3 二叉搜索树

实际运用中常见的数据结构，一种特殊的二叉树

概念

BST(Binary Search Tree)，也称二叉排序树或二叉查找树
如果不为空，满足性质：
- 非空左子树的所有键值小于根节点的键值
- 非空右子树的所有键值大于根节点的键值
- 左右子树本身也是二叉搜索树（递归）
特点：
- 相对较小的值保存在左节点，相对较大的值保存在右节点
- 这个特点使得查找效率非常高，包括查找最值和特定的值
利用二分查找思想：
- 查找所需最大次数等于二叉搜索树的深度
- 插入节点也可以如此，逐层比较找到新节点合适的位置
缺陷:
- 如果插入有序数据,会分布不均,称为非平衡树
- 平衡二叉树,插入/查找效率O(logN),而非平衡二叉树相当于链表,查找效率为O(N)

代码实现

常见操作
- insert(key)：插入一个新的键
- search(key)：查找键，存在返回true，否则返回false
- preOrderTraverse：先序遍历
- inOrderTraverse：中序遍历
- postOrderTraverse：后序遍历
- min：返回最小值
- max：返回最大值
- remove(key)：移除某个键
注意：这里的三种遍历操作适用于所有二叉树，二叉树遍历还有层序遍历（队列实现）使用较少

封装：

class Node{
    constructor(){
        this.key=key;
        this.left=null;
        this.right=null;
    }
}

export class BinarySearchTree{
    constructor(){
        this.root = null;
    }    
   
    
}

插入

 //插入操作(需要是一个可以进行比较的键)
    insert(key){
        //1.根据key创建节点
        const newNode = new Node(key);
        
        //2.判断原来的树是否空树
        if(this.root === null){
            this.root = newNode;
        }else{
            //调用插入节点方法递归查找到合适位置进行插入
            this.insertNode(this.root,newNode);
        }
        
    }
    
    //插入节点方法
    insertNode(node,newNode){
        if(newNode.key>node.key){
            if(node.right === null){
                node.right = newNode
            }else{
                this.insertNode(node.right,newNode)
            }
        }else{
            if(node.left === null){
                node.left = newNode
            }else{
                this.insertNode(node.left,newNode)
            }
        }
    }

遍历

先序遍历 root->left->right
中序遍历 left-root->right
后序遍历 left->right->root

  //先序遍历
    preOrderTraverse(){
        //递归调用
        this.preOrderTraverseNode(root);
    }
    
    preOrderTraverseNode(node){
        if(node === null)return;
        
        console.log(node.key);//先操作
        this.preOrderTraverseNode(node.left);
        this.preOrderTraverseNode(node.right);
    }
    
    //中序遍历
    inOrderTraverse(){
        //递归调用
        this.inOrderTraverseNode(root);
    }
    
    inOrderTraverseNode(node){
        if(node === null)return;
        
        this.inOrderTraverseNode(node.left);
        console.log(node.key);//中间操作
        this.inOrderTraverseNode(node.right);
    }
    
    //后序遍历
    postOrderTraverse(){
        //递归调用
        this.postOrderTraverseNode(root);
    }
    
    postOrderTraverseNode(node){
        if(node === null)return;
        
        this.postOrderTraverseNode(node.left);
        this.postOrderTraverseNode(node.right);
        console.log(node.key);//后操作
    }

获取最值

 
    //获取最大值，一直右找
    max(){
        let node = this.root;
        while(node.right!==null){
            node = node.right;
        }
        return node.key;
    }
    
    //获取最小值，一直左找
    min(){
        let node = this.root;
        while(node.left!==null){
            node = node.left;
        }
        return node.key;
    }

搜索

 //搜索操作
    //递归实现
    search(key){
        this.searchNode(this.root,key)
    }
    
    searchNode(node,key){
        if(node.key === key)return true;
        
        if(key<node.key){
            return this.searchNode(node.left,key);
        }else if(key>node.key){
            return this.searchNode(node.right,key);
        }else{
            return false;
        }
    }
    //循环实现
    search2(key){
        let node = this.root;
        
        while(node !== null){
            if(key < node.key){
                node = node.left;
            }else if(key > node.key){
                node = node.right;
            }else{
                return true;
            }
        }
        return false
    }

删除节点

有时为避免删除操作添加isDeleted标记,简单不改变树结构但浪费空间

找到要删除的节点，如果没有找到说明不需要删除
找到要删除的节点，三种情况
- 删除叶子节点
- 删除只有一个子节点的节点
- 删除有两个子节点的节点
  
  需要从下面的子节点中找到节点来替换current
  
  也就是左子树的最大节点或右子树的最小节点
  
  根据二叉搜索树特点，上面两个节点最接近current
  
  比current小一点点的节点称为current的前驱
  
  比current大一点点的节点称为current的后继

//删除操作
remove(key){
    //1.定义一些变量记录状态
    let current = this.root;
    let parent = null;
    let isLeftChild = true;
    
    //2.开始查找要删除的节点
    while(current.key !== key){
        parent = null;
        if(key<current.key){
            isLeftChild = true;
            current = current.left;
        }else{
            isLeftChild = false;
            current = current.right;
        }
        if(current === null)return false;
    }
    
    //找到要删除的节点，记录为current,父节点为parent
    
    //情况一：删除的节点是叶子节点
    if(current.left === null && current.right === null){
        if(current === this.root){
            this.root = null;
        }else if(isLeftChild){
            parent.left = null;
        }else{
            parent.right = null;
        }
    }
    
    //情况二：只有一个子节点（直接替代）
    else if(current.right === null){//只有左子节点
        if(current === this.root){
            this.root = current.left;
        }else if(isLeftChild){
            parent.left = current.left;
        }else{
            parent.right = current.left;
        }
    }else if(current.left === null){//只有右子节点
        if(current === this.root){
            this.root = current.right;
        }else if(isLeftChild){
            parent.left = current.right;
        }else{
            parent.right = current.right;
        }
        return true;
    }
    
    //情况三：有两个子节点
    else{
        //1.获取后继节点
        let successer = this.getSuccesser(current);
        
        //2.判断是否根节点
        if(this.root === current){
            this.root = successer;
        }else if(isLeftChild){
            parent.left = successer;
        }else{
            parent.right = successer;
        }
        successer.left = current.left;//原来的左子树赋给后继
    }

    return true;
}

//找到需要删除节点的后继(或前驱，方法一样)
getSuccesser(delNode){
    //1.定义变量存储临时节点
    let successerParent = delNode;
    let successer = delNode;
    let current = delNode.right;

    //2.寻找节点（右子树最小节点）
    while(current !== null){
        successerParent = successer;
        successer = current;
        current = current.left;
    }
    //3.后继节点有右子节点（意味着后继节点不直接是delNode的右子节点）
    if(successer !== delNode.right){
        successerParent.left = successer.right;
        successer.right = delNode.right;
    }
    return successer;
}

6.4 红黑树

树的平衡性
- 每个节点左边子孙节点数尽量等于右边子孙节点数
- 保持平衡是为了维持树的操作时间复杂度在O(logN)
AVL树
- 最早的平衡树
- 每个节点的左子树和右子树的高度最多相差1，这被称为平衡因子
- 每个节点多存储一个键值对以助于保持平衡
- 每次插入/删除操作需要执行旋转来重新平衡,相对红黑树效率低,整体效率不如红黑树
- AVL树适用注重读取操作的场景，因为它更严格地保持了树的平衡性，使得树的高度相对较低，查找操作的时间复杂度更稳定

红黑树概念

通过一些特性保持树的平衡
时间复杂度O(logN)
插入/删除操作性能优于AVL树,适用于更多修改操作的场景
现在平衡树的应用基本都是红黑树

红黑树规则

除二叉搜索树基本规则,添加了五条特性

节点红色或黑色
根节点黑色
每个叶子节点都是黑色的空节点(NIL节点)
每个红色节点的两个子节点为黑色(从叶子节点到根的所有路径不能有两个及以上连续红色节点)
从任一节点到每个叶子节点的所有路径包含相同数目的黑色节点

平衡原理

确保了红黑树的关键特性:

从根到叶子的最长可能路径不超过最短可能路径的两倍,这样确保树的高度相对较低,近似平衡
- 性质4决定路径不能有两个相连的红色节点
- 最短的可能路径都是黑色节点
- 最长的可能路径是红色和黑色交替
- 性质5保证所有路径黑色节点数一样
- 综上那么没有路径可以长于其他任何路径的两倍
插入新节点,可能需要变换保持平衡(换色-左旋-右旋)

插入到二叉搜索树的合适位置，并将该节点着色为红色

6种情况:文章来源地址https://www.toymoban.com/news/detail-765529.html
- 是树的根节点.将根节点的颜色设置为黑色
- 父节点是黑色,由于没有破坏红黑树的性质，不需要进行额外的调整
- 父节点和叔叔节点都是红色, 将父节点和叔叔节点的颜色设置为黑色，祖父节点的颜色设置为红色
- 父节点是红色，但叔叔节点是黑色或空,并且插入节点是其父节点的右子节点，而父节点又是祖父节点的左子节点, 父节点左旋
- 父节点是红色，但叔叔节点是黑色或空，并且插入节点是其父节点的左子节点，而父节点又是祖父节点的左子节点,需要祖父节点右旋
- 父节点是红色，但叔叔节点是黑色或空，并且插入节点是其父节点的左子节点，而父节点又是祖父节点的右子节点, 父节点右旋进入上一种情况