哈希表与树

哈希表

🏢 提示

底层仍然是由数组来实现的 字符串映射到数组的索引的方式，来储存数据 优点：

1. 插入查询删除效率高 缺点：
2. 空间利用率不高
3. 元素无序
4. 求最值慢

实现和内容暂时略去

树结构

🏢 提示

树是由n(n>=0)个节点构成的有限集合： 对于任何一颗非空树（n>0）,由如下特性：

1. 树中有一个称为‘根(root)’的特殊节点，用r表示
2. 其余节点可以分为m(m>0)个互不相交的有限集合合，T1，T2....Tm,每个集合本身又是一棵树，称为原来树的'子树(subTree)'
3. 没有子节点的节点称为叶子节点，（度为0）
4. 节点的度（Degree）：节点的子树个数 优点： 缺点：

二叉树

🏢 提示

二叉树： 每个节点最多只能 有2个子节点，这样的树称为二叉树 特性：

1. 一棵二叉树第i层最大的节点数为：2^(i-1),i>1
2. 深度为k的二叉树有最大节点总数为：2^k -1,k>1
3. 任何非空二叉树，n0表示叶节点数，n2表示度为2的非叶子节点，那么两者关系满足n0 = n2+1 存放对象时，实现valueOf方法，即可实现

完美二叉树 Perfect Binary Tree/满二叉树 Full Binary Tree

除了叶子节点外，其他所有节点的度都是2

也就是说，所有的节点需要填满

完全二叉树 complete Binary Tree

1. 除了最后一层，其他各层节点数都达到最大个数
2. 最后一层，从左到右的叶子节点连续存在，只缺右侧的若干节点
3. 完美二叉树是特殊的完全二叉树

🏢 提示

完全二叉树可以使用数组来储存 后面的堆结构也可以使用

二叉搜索树 BST （Binary Search Tree）

1. 非空左子树的所有键值小于其根节点的键值
2. 非空右子树的所有键值大于其根节点的键值
3. 左右子树本身也是二叉搜索树

二叉树的遍历

🏢 提示

先/中/后序遍历是指: 在所有的树结构中（包括子树）访问根元素值的顺序

1. 先序遍历

在所有的树结构中（包括子树）

• 先访问根元素
• 再访问所有左子树
• 再访问右子树

preOrderTraverse(){
    console.log('_preOrderTraverse')
    this._preOrderTraverse(this.root)
  }
  private _preOrderTraverse(node:TreeNode<T>|null) {
    if(node){
      console.log(node.value) // 
      this._preOrderTraverse(node.leftNode)
      this._preOrderTraverse(node.rightNode)
    }
  }

1. 中序遍历

• 先访问所有左子树
• 再访问根元素
• 再访问右子树

inOrderTraverse(){
    console.log('_inOrderTraverse')
    this._inOrderTraverse(this.root)
  }
  private _inOrderTraverse(node:TreeNode<T>|null){
    if(node){
      this._inOrderTraverse(node.leftNode)
      console.log( node.value) // 
      this._inOrderTraverse(node.rightNode)
    }
  }

1. 后序遍历

• 先访问所有左子树
• 再访问右子树
• 最后访问根元素

 postOrderTraverse(){
    console.log('_postOrderTraverse')
    this._postOrderTraverse(this.root)
  }
  private _postOrderTraverse(node:TreeNode<T>|null){
    if(node){
      this._postOrderTraverse(node.leftNode)
      this._postOrderTraverse(node.rightNode)
      console.log( node.value) // 
    }
  }

1. 层序遍历

• 按树的层来遍历，从顶往下访问

levelOrderTraverse(){
    //使用队列来解决
    if(!this.root) return
    const queue :TreeNode<T>[]= []
    queue.push(this.root)

    while(queue.length){
      const el = queue.shift()
      console.log( el!.value)
      if(el?.leftNode){
        queue.push(el.leftNode)
      }
      if(el?.rightNode){
        queue.push(el.rightNode)
      }
    }
    
  }

最值

1. 最大值 就是树的最右值

 
 /**最大值 */
  max():T|null{
    let current = this.root
    while(current && current.rightNode){
      current = current.rightNode
    }
    return current?.value ?? null
  }

1. 最小值 树的最左值

min():T|null{
    let current = this.root
    while(current && current.leftNode){
      current = current.leftNode
    }
    return current?.value ?? null
  }

搜索

 //迭代
 search(value:T):boolean{
   let current = this.root
   while(current){
     if(current.value == value) return true
     if(current.value > value){
      current = current.leftNode
     } else {
      current = current.rightNode
     }
   }
   return false
  }
  //递归
  

删除节点

🏢 提示

删除节点比较复杂，需要考虑的情况比较多

1. 是叶子节点
2. 有1个子节点
3. 有2个子节点

class TreeNode<T> {
  leftNode:TreeNode<T>|null = null
  rightNode:TreeNode<T>|null = null
  parent:TreeNode<T>|null = null
  get isLeft(){
    return parent && this.parent?.leftNode === this
  }
  get isRight(){
    return parent && this.parent?.rightNode === this
  }
  constructor(public value:T){ }
}

/**
   * 搜索节点
   * @param value 
   * @returns 
   */
private _search(value:T):TreeNode<T>|null {
   let current = this.root,parentNode:TreeNode<T>|null = null
   while(current){
     if(current.value == value) {
      current.parent =parentNode
      return current
     }
     parentNode = current
     if(current.value > value){
      current = current.leftNode
     } else {
      current = current.rightNode
     }
   }
   return null
  }
/**
   * 获取后继节点，右子树的最小值，也就是没有左子树
   * @param delNode  删除的节点
   */
  private getSuccessor(delNode:TreeNode<T>) {
    let current = delNode.rightNode
    let successor: TreeNode<T>|null = null
    while(current){
      successor = current
      current =current.leftNode
      if(current){
        //保留所有的父节点信息
        current.parent = successor
      }
    }
    if(successor !== delNode.rightNode){
      //当后继节点不等删除节点的右节点时，需要替换删除节点的右节点
      successor!.parent!.leftNode = successor!.rightNode
      // 也就是把后继节点的右节点，放到后继节点的父节点的左节点上
      // 如上图中删除 15时，后继节点18的存在右子树，15也存在右子树
      successor!.rightNode = delNode.rightNode
      //删除节点的右节点，放到 后继节点的右节点上
    }

    //后继节点的左节点必须指向 删除节点原来的左节点
    // 如上图中，删除7时，左子树也需要放到后继节点8的左子树，后继节点一定没有左子树
    successor!.leftNode = delNode.leftNode
    
    return successor
  }
  /**
   * 删除节点
   * @param value 
   */
  remove(value:T){
    let current = this._search(value)
    if(!current) return false

    // 1. 叶子节点
    let replaceNode:TreeNode<T>|null = null
    if(current.leftNode === null && current.rightNode === null){
      replaceNode = null
    }
    // 2. 有1个子节点
    // 是右节点，就需要把右节点保存下来
    else if(current.leftNode === null){
       replaceNode =current.rightNode 
    }
    //左节点，需要把左节点保存下来
    else if(current.rightNode === null){
      replaceNode =current.leftNode
    }
    // 3. 有2个子节点
    else {
    // 替换后继节点，后继节点的子节点处理已在getSuccessor函数中处理
      replaceNode = this.getSuccessor(current)
    }
    if(current===this.root){
    // 如果是根元素，那么直接替换根元素
      this.root =replaceNode
    }else if(current.isLeft){ 
    // 如果被删除的节点是父节点的左节点，那么替换左节点
      current.parent!.leftNode = replaceNode
    }else {
    //如果是父节点的右节点，那么替换右节点即可
      current.parent!.rightNode = replaceNode
    }
  }

avl树

红黑树