数据结构 --树结构

树结构

• 二叉树
  • 特性：
    • 一个二叉树第i层的最大节点数为 2^(i-1) i>=1
    • 深度为k的二叉树有最大节点总数为 2^k-1 k>=1
    • 任何非空二叉树T 若n0表示叶节点的个数, n2是度为2的非叶结点个数 n0=n2+1
  • 二叉树的存储:
    • 使用数组:完全二叉树 取得时候左=父2 右=父2+1
    • 最常见的方式使用链表存储
  • 二叉搜索树(Binary Serch Tree)BST:
    • 性质：
      • 非空左子树所有键值小于其根节点的键值
      • 非空右子树所有键值大于其根节点的键值
      • 左右子树本身也都是二叉搜索树
      • 理解: 根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，
    • 特性:相对较小的值总是保存在左节点上,相对较大的值总是保存在右节点上
  • 遍历:
    • 先序遍历: 1)访问根节点 2)先序遍历其左子树 3)先序遍历其右子树
    • 中序遍历 1)中序遍历左子树 2)访问根节点 3)中序遍历右子树
    • 后序遍历 1)后序遍历左子树 2)中序遍历右子树 3)访问根节点 用的比较少的层序遍历
  • 删除操作
    • 情况一：没有子节点
    • 情况二：该节点有一个子节点
    • 情况三：该节点有两个子节点：如果有两个子节点查找要删除的节点
    • 情况三规律：
      • 前驱： 比current小一点点的节点 一定是current左子树的最大值
      • 后继：比current大一点点的节点 一定是current右子树的最小值
  • 对于一个平衡二叉树来说 插入查找效率为 O（logN）
  • 缺陷： 插入连续数据 深度会非常的深 二叉搜索树在比较极端i情况就相当于一个链表了查找效率就很低了插入连续数据后分布不均匀 的树叫非平衡树 查找效率变成O（n）

//封装二叉搜索树
  function BinarySearchTree(){
    function Node(key){
      this.key = key
      this.left=null
      this.right=null
    }
    //属性
    this.root=null
    //方法
    //    插入数据
    //  给用户调用的方法
    BinarySearchTree.prototype.insert=function (key){
      //1.根据key创建节点
      let newNode=new Node(key)

      //2.判断根节点是否有值
      if(this.root==null){
        this.root=newNode
      }else {
        this.insertNode(this.root,newNode)
      }
    }

    //内部调用的
    BinarySearchTree.prototype.insertNode=function (node,newNode){
      if(newNode.key<node.key){  //向左查找
        if(node.left==null){
          node.left=newNode
        }else {
          this.insertNode(node.left,newNode)
        }
      }else {//向右查找
        if(node.right==null){
          node.right= newNode
        }else {
          this.insertNode(node.right,newNode)
        }
      }
    }
    //树的遍历
    //1.先序遍历
    BinarySearchTree.prototype.preOrderTraversal=function (handler){
      this.preOrderTraversalNode(this.root,handler)
    }
    //内部方法  递归
    BinarySearchTree.prototype.preOrderTraversalNode=function (node,handler){
      if(node!=null){
        //1.处理经过的节点
        handler(node.key)

        //2.查找经过节点的左子节点
        this.preOrderTraversalNode(node.left,handler)
        //3.查找经过节点的右子节点
        this.preOrderTraversalNode(node.right,handler)
      }
    }


    //2.中序遍历
    BinarySearchTree.prototype.midOrderTraversal=function (handler){
      this.midOrderTraversalNode(this.root,handler)
    }
    BinarySearchTree.prototype.midOrderTraversalNode=function (node,handler){
      if(node!=null){
        //查找左子树中的节点
        this.midOrderTraversalNode(node.left,handler)

        //处理节点
        handler(node.key)

        //查找右子树的节点
        this.midOrderTraversalNode(node.right,handler)

      }
    }

    //3.后序遍历
    BinarySearchTree.prototype.postOrderTraversal=function (handler){
      this.postOrderTraversalNode(this.root,handler)
    }
    BinarySearchTree.prototype.postOrderTraversalNode=function (node,handler){
      if (node!=null){
        this.postOrderTraversalNode(node.left,handler)

        this.postOrderTraversalNode(node.right,handler)

        handler(node.key)
      }
    }
    //获取最大最小值
    BinarySearchTree.prototype.min=function (){
      //获取根节点
      let node=this.root
      //依次向右不断查找，直到节点为null
      while (node.left!==null){
        node=node.left
      }
      return node.key
    }
    BinarySearchTree.prototype.max=function (){
      let node=this.root
      while (node.right!==null){
        node=node.right
      }
      return node.key
    }

    //搜索key  非递归实现
    BinarySearchTree.prototype.search=function (key){
      //1.获取根节点
      let node=this.root

      //2.循环搜索key
      while (node != null){
        if (key<node.key){
          node=node.left
        }else if (key>node.key){
          node=node.right
        }else {
          return true
        }
      }
      return false
    }
    //搜索key递归实现
    // BinarySearchTree.prototype.search=function (key){
    // return this.searchNode(this.root,key)
    // }
    // BinarySearchTree.prototype.searchNode=function (node,key){
    //   if (node==null){
    //     return false
    //   }
    //
    //   if (key<node.key){
    //     return this.searchNode(node.left,key)
    //   }else if (key>node.key){
    //     return this.searchNode(node.right,key)
    //   }else { //相同说明找到了
    //     return true
    //   }
    // }

    //删除节点
    BinarySearchTree.prototype.remove=function (key){
      //1.寻找要删除的节点
      //1.1定义变量 保存一些信息
      let current=this.root
      let parent=null
      let isLeftChild =true

      //根据对应的情况删除节点
      //1.2开始寻找删除的节点
      while (current.key!==key){
        parent=current
        if (key<current.key){
          isLeftChild=true
          current=current.left
        }else {
          isLeftChild=false
          current=current.right
        }
        //某种情况是  已经找到了最后的节点 ，依旧没有找到 ==key  这里的current 经过了if之后
        if (current==null){return false}
      }

      //2.根据对应情况删除节点
      //2.1删除的节点是叶子节点（没有子节点）
      if(current.left==null&&current.right==null){
        if(current === this.root){
          this.root=null
        }else if(isLeftChild){
          parent.left=null
        }else {
          parent.right=null
        }
      }

      //2.2删除的节点有一个子节点
      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的左孩子 代表删除的节点在parent左子树
          parent.left=current.right
        }else {
          parent.right=current.right
        }
        
      }
      //2.3删除的节点有两个子节点
      else{
        //1.获取后继节点
        let successor = this.getSuccessor(current);
        //2.判断是否是根节点
        if(this.root=== current){
          this.root=successor
        }else if(isLeftChild){
          parent.left=successor
        }else{
          parent.right=successor
        }
        successor.left=current.left
      }
      return true
    }
    //找后继的方法
    BinarySearchTree.prototype.getSuccessor=function(deleteNode){
      //1.定义变量 存储临时节点
      let successorParent=deleteNode;
      let successor = deleteNode;
      let current=deleteNode.right;

      //2.寻找节点
      while(current!=null){
        successorParent=successor // suc作为下一级的parent
        successor=current
        current=current.left
      }
      //3.如果后继节点不是删除节点的右节点
      if(successor!=deleteNode.right){
        successorParent.left=successor.right   //
        successor.right=deleteNode.right  //后继取代删除节点 右节点为删除节点的右节点
      }
      return successor
    }
  }

红黑树

• 规则

  1. 节点是红色或者黑色
  2. 根节点是黑色
  3. 每个叶子节点都是黑色的空节点（NIL）
  4. 每个红色节点的两个子节点都是黑色。 （从每个叶子到根的所有路径上不能有两个连续的红色节点）
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

• 变色

  • 通常插入新的节点默认是红色

• 左旋转

• • 逆时针旋转红黑树的两个节点，让父节点被自己的右孩子取代 自己成为自己的左孩子

• 右旋转

• • 顺时针旋转红黑树的两个节点，让父节点被自己的左孩子取代 自己成为自己的右孩子

• 插入节点：N 插入节点父节点：P 插入节点父节点的父节点：G 插入节点叔叔节点：U

  • 插入节点的几种情况：
    1. 新节点是根节点
       1. 将插入 节点红色变为黑色
    2. 新插入节点的父节点P是黑色
    3. 父节点为红色 叔叔节点也为红色 祖父一定为黑 -> 变成父黑叔黑祖红
    4. 父节点为红色 叔叔节点为黑色 N为左孩子
       1. ->父黑
       2. ->祖红
       3. ->G右旋转
    5. 父节点为红色 叔叔节点为黑色 N为右孩子
       • 以P为根左旋转
         • 将P作为新插入的红色节点考虑
       • 插入节点自己变成黑色
       • 祖变为红色
       • 以祖为根进行右旋转