JavaScript(ES6)数据结构与算法之树

2023-12-26 12:40:02

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树,适用于更多修改操作的场景
  • 现在平衡树的应用基本都是红黑树
红黑树规则

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

  1. 节点红色或黑色
  2. 根节点黑色
  3. 每个叶子节点都是黑色的空节点(NIL节点)
  4. 每个红色节点的两个子节点为黑色(从叶子节点到根的所有路径不能有两个及以上连续红色节点)
  5. 从任一节点到每个叶子节点的所有路径包含相同数目的黑色节点
平衡原理
  • 确保了红黑树的关键特性:

    从根到叶子的最长可能路径不超过最短可能路径的两倍,这样确保树的高度相对较低,近似平衡

    • 性质4决定路径不能有两个相连的红色节点
    • 最短的可能路径都是黑色节点
    • 最长的可能路径是红色和黑色交替
    • 性质5保证所有路径黑色节点数一样
    • 综上那么没有路径可以长于其他任何路径的两倍
  • 插入新节点,可能需要变换保持平衡(换色-左旋-右旋)

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

    6种情况:

    • 是树的根节点.将根节点的颜色设置为黑色
    • 父节点是黑色,由于没有破坏红黑树的性质,不需要进行额外的调整
    • 父节点和叔叔节点都是红色, 将父节点和叔叔节点的颜色设置为黑色,祖父节点的颜色设置为红色
    • 父节点是红色,但叔叔节点是黑色或空,并且插入节点是其父节点的右子节点,而父节点又是祖父节点的左子节点, 父节点左旋
    • 父节点是红色,但叔叔节点是黑色或空,并且插入节点是其父节点的左子节点,而父节点又是祖父节点的左子节点,需要祖父节点右旋
    • 父节点是红色,但叔叔节点是黑色或空,并且插入节点是其父节点的左子节点,而父节点又是祖父节点的右子节点, 父节点右旋进入上一种情况

文章来源:https://blog.csdn.net/bfbshs_ddd/article/details/135217098
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。