AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

JavaScript 数据结构与算法 之 树

2022-05-26 125
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： JavaScript 数据结构与算法 之 树

树

数据结构

  • 相关术语

    • 位于树顶部的节点叫作根节点
    • 至少有一个子节点的节点称为内部节点
    • 没有子元素的节点称为外部节点或叶节点
    • 子树由节点和它的后代构成
    • 节点的深度取决于它的祖先节点的数量
    • 树的高度取决于所有节点深度的最大值。一棵树也可以被分解成层级，根节点在第 0 层。

二叉树

二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。二叉搜索树（BST）是二叉树的一种，但是只允许在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。 
class Node {
  constructor() {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}
class BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    this.compareFn = compareFn;
    this.root = null;
  }
  insert(key) {
    if (this.root == null) {
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key);
    }
  }
  insertNode(node, key) {
    if (compareFn(key, node.key) === Compare.LESS_THAN) {
      if (node.left != null) {
        node.left = new Node(key);
      } else {
        this.insertNode(node.left, key);
      }
    } else {
      if (node.right != null) {
        node.right = new Node(key);
      } else {
        this.insertNode(node.right, key);
      }
    }
  }
  // 中序遍历
  inOrderTraverse(cb) {
    this.inOrderTraverseNode(this.root, cb);
  }
  inOrderTraverseNode(node, cb) {
    if (node != null) {
      this.inOrderTraverseNode(node.left, cb);
      cb(node.key);
      this.inOrderTraverseNode(node.right, cb);
    }
  }
  // 先序遍历
  preOrderTraverse(cb) {
    this.preOrderTraverseNode(this.root, cb);
  }
  preOrderTraverseNode(node, cb) {
    if (node != null) {
      cb(node.key);
      this.preOrderTraverseNode(node.left, cb);
      this.preOrderTraverseNode(node.right, cb);
    }
  }
  // 后续遍历
  postOrderTraverse(cb) {
    this.postOrderTraverseNode(this.root, cb);
  }
  postOrderTraverseNode(node, cb) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, cb);
      this.postOrderTraverseNode(node.right, cb);
      cb(node.key);
    }
  }
  // 搜索最小值
  min() {
    return this.miniNode(this.root);
  }
  miniNode(node) {
    let current = node;
    while(current != null && node.left != null) {
      current = current.left;
    }
    return current;
  }
  // 最大值
  max() {
    return this.maxNode(this.root);
  }
  maxNode(node) {
    let current = node;
    while(current != null && node.right != null) {
      current = current.right
    }
    return current;
  }
  // 搜索特定的值
  search(key) {
    return this.searchNode(this.root, key);
  }
  searchNode(node, key) {
    if (node == null) {
      return false;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      return this.searchNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      return this.searchNode(node.right, key);
    } else {
      return true;
    }
  }
  
  remove(key) {
    this.root = this.removeNode(this.root, key);
  }
  removeNode(node, key) {
    if (node == null) {
      return null;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.removeNode(node.left, key);
      return node;
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.removeNode(node.right, key);
      return node;
    } else {
      // 无子节点
      if (node.left == null && node.right == null) {
        node = null;
        return node;
      }
      // 有一个子节点
      if (node.left == null) {
        node = node.right;
        return node;
      } else if (node.right == null) {
        node = node.left;
        return node;
      }
      // 有两个子节点
      const aux = this.miniNode(node.right);
      node.key = aux.key;
      node.right = this.removeNode(node.right, aux.key);
      return node;
    }
  }
}

自平衡树

Adelson-Velskii-Landi 树（ AVL 树）是一种自平衡二叉搜索树，意思是任何一个节点左右两侧子树的高度之差最多为 1。

在 AVL 树中，需要对每个节点计算右子树高度（ hr）和左子树高度（ hl）之间的差值，该值（ hr－ hl）应为 0、 1 或1。如果结果不是这三个值之一，则需要平衡该 AVL 树。这就是平衡因子的概念。

  • 平衡操作——AVL 旋转

    • 左-左（LL）：向右的单旋转


    • 右-右（RR）：向左的单旋转


    • 左-右（LR）：向右的双旋转（先 LL 旋转，再 RR 旋转）


    • 右-左（RL）：向左的双旋转（先 RR 旋转，再 LL 旋转）

const BalanceFactor = {
  UNBALANCED_RIGHT: 1,
  SLIGHTLY_UNBALANCED_RIGHT: 2,
  BALANCED: 3,
  SLIGHTLY_UNBALANCED_LEFT: 4,
  UNBALANCED_LEFT: 5
};
class AVLTree extends BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
    this.compareFn = compareFn;
    this.root = null;
  }
  // 计算节点高度
  getNodeHeight(node) {
    if (node == null) {
      return -1;
    }
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
  }
  // 计算平衡因子
  getBalanceFactor(node) {
    const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch(heightDifference) {
      case -2:
        return BalanceFactor.UNBALANCED_RIGHT;
      case -1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
      case 1:
        return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
      case 2:
        return BalanceFactor.UNBALANCED_LEFT;
      default:
        return BalanceFactor.BALANCED;
    }
  }
  rotationLL(node) {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
  }
  rotationRR(node) {
    const tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    return tmp;
  }
  rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
  }
  rotationRL(node) {
    node.right = this.rotationLL(node.right);
    return this.rotationRR(node);
  }

  insert(key) {
    this.root = this.insertNode(this.root, key);
  }
  insertNode(node, key) {
    // 先像 BST 中一样插入
    if (node == null) {
      return new Node(key);
    } else if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      node.left = this.insertNode(node.left, key);
    } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
      node.right = this.insertNode(node.right, key);
    } else { // 重复的键
      return node;
    }
    // 如果结果不平衡就进行调整
    const balanceFactor = this.getBalanceFactor(node);
    if balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
        node = this.rotationLL(node);
      } else {
        return this.rotationLR(node);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
        node = this.rotationRR(node);
      } else {
        return this.rotationRL(node);
      }
    }
    return node;
  }

  removeNode(node, key) {
    node = super.removeNode(node, key);
    if (node == null) {
      return node;
    }
    const balanceFactor = this.getBalanceFactor(node);
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
      const balanceFactorLeft = this.getBalanceFactor(node.left);
      if (balanceFactorLeft === BalanceFactor.BALANCED ||
        balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
        return this.rotationLL(node);
      }
      if (balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
        return this.rotationLR(node);
      }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
      const balanceFactorRight = this.getBalanceFactor(node.right);
      if (balanceFactorRight === BalanceFactor.BALANCED ||
        balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
        return this.rotationRR(node);
      }
      if (balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
        return this.rotationRL(node);
      }
    }
    return node;
  }
}

红黑树

红黑树也是一个自平衡二叉搜索树。如果插入和删除频率较低，AVL 树比红黑树更好。

  • 红黑树定义规则

    • 每个节点不是红的就是黑的
    • 树的根节点是黑的
    • 所有叶节点都是黑的（用 NULL 引用表示的节点）
    • 如果一个节点是红的，那么它的两个子节点都是黑的
    • 不能有两个相邻的红节点，一个红节点不能有红的父节点或子节点
    • 从给定的节点到它的后代节点（ NULL 叶节点）的所有路径包含相同数量的黑色节点

  • 旋转和颜色变换规则

    • 变颜色：当前节点的父亲是红色，且它的祖父节点的另一个子节点（叔叔节点）也是红色

      1. 把父节点设为黑色
      2. 把叔叔节点也设为黑色
      3. 把祖父节点设为红色
      4. 把指针定义到祖父节点设为当前要操作的，分析节点变换规则
    • 左旋：当前父亲节点是红色，叔叔节点是黑色，且当前节点是右子树，左旋以父节点作为左旋

    • 右旋：当前父节点是红色，叔叔是黑色的时候，且当前的节点是左子树

      1. 把父节点变为黑色
      2. 将祖父节点变为红色
      3. 以祖父节点旋转
class RedBlackNode extends Node {
  constructor(key) {
    super(key);
    this.key = key;
    this.color = Colors.RED;
    this.parent = null;
  }
  isRed() {
    return this.color === Colors.RED;
  }
}
class RedBlackTree extends BinarySearchTree {
  constructor(compareFn = defaultCompare) {
    super(compareFn);
    this.compareFn = compareFn;
    this.root = null;
  }
  insert(key: T) {
    if (this.root == null) {
      this.root = new RedBlackNode(key);
      this.root.color = Colors.BLACK;
    } else {
      const newNode = this.insertNode(this.root, key);
      this.fixTreeProperties(newNode);
    }
  }
  insertNode(node, key) {
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (node.left == null) {
        node.left = new RedBlackNode(key);
        node.left.parent = node;
        return node.left;
      } else {
        return this.insertNode(node.left, key);
      }
    } else if (node.right == null) {
      node.right = new RedBlackNode(key);
      node.right.parent = node;
      return node.right;
    } else {
      return this.insertNode(node.right, key);
    }
  }
  fixTreeProperties(node) {
    while (node && node.parent && node.parent.isRed()
      && node.color !== Colors.BLACK) {
      let parent = node.parent;
      const grandParent = parent.parent;
      // 父节点是左侧子节点
      if (grandParent && grandParent.left === parent) {
        const uncle = grandParent.right;
        // 叔叔节点也是红色——只需要重新填色
        if (uncle && uncle.color === Colors.RED) {
          grandParent.color = Colors.RED;
          parent.color = Colors.BLACK;
          uncle.color = Colors.BLACK;
          node = grandParent;
        } else {
          // 节点是右侧子节点——左旋转
          if (node === parent.right) {
            this.rotationRR(parent);
            node = parent;
            parent = node.parent;
          }
          // 节点是左侧子节点——右旋转
          this.rotationLL(grandParent);
          parent.color = Colors.BLACK;
          grandParent.color = Colors.RED;
          node = parent;
        }
      } else {
        // 父节点是右侧子节点
        const uncle = grandParent.left;
        // 叔叔节点是红色——只需要重新填色
        if (uncle && uncle.color === Colors.RED) {
          grandParent.color = Colors.RED;
          parent.color = Colors.BLACK;
          uncle.color = Colors.BLACK;
          node = grandParent;
        } else {
          // 节点是左侧子节点——右旋转
          if (node === parent.left) {
            this.rotationLL(parent);
            node = parent;
            parent = node.parent;
          }
          // 节点是右侧子节点——左旋转
          this.rotationRR(grandParent);
          parent.color = Colors.BLACK;
          grandParent.color = Colors.RED;
          node = parent;
        }
      }
    }
    this.root.color = Colors.BLACK;
  }
  rotationLL(node) {
    const tmp = node.left;
    node.left = tmp.right;
    if (tmp.right && tmp.right.key) {
      tmp.right.parent = node;
    }
    tmp.parent = node.parent;
    if (!node.parent) {
      this.root = tmp;
    } else {
      if (node === node.parent.left) {
        node.parent.left = tmp;
      } else {
        node.parent.right = tmp;
      }
    }
    tmp.right = node;
    node.parent = tmp;
  }
  rotationRR(node) {
    const tmp = node.right;
    node.right = tmp.left;
    if (tmp.left && tmp.left.key) {
      tmp.left.parent = node;
    }
    tmp.parent = node.parent;
    if (!node.parent) {
      this.root = tmp;
    }
    else {
      if (node === node.parent.left) {
        node.parent.left = tmp;
      }
      else {
        node.parent.right = tmp;
      }
    }
    tmp.left = node;
    node.parent = tmp;
  }
}
文章标签：
JavaScript
前端开发
算法
存储
关键词：
数据结构树
数据结构与算法树
算法树
JavaScript算法
JavaScript树
1759666346247123
目录
相关文章
XIAZHI
|
1月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索（DFS）算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历，按预序（根、左、右）输出节点值。接着，通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表，展示了如何将树结构转换为线性结构。最后，讨论了此算法的优点，如实现简单和内存效率高，同时也指出了潜在的内存管理问题，并分析了算法的时间复杂度。
XIAZHI
54 0
龙大吉
|
1月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
55 5
html的七十二变
|
1月前
|
监控 JavaScript 算法
深度剖析 Vue.js 响应式原理：从数据劫持到视图更新的全流程详解
本文深入解析Vue.js的响应式机制，从数据劫持到视图更新的全过程，详细讲解了其实现原理和运作流程。
html的七十二变
63 2
ephemerals__
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
94 16
dufadayang
|
1月前
|
算法
树的遍历算法有哪些？
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题；广度优先搜索则在图的最短路径、层次相关的问题中较为常用；而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
dufadayang
39 2
奔跑的数据
|
1月前
|
数据采集 存储 JavaScript
如何使用Puppeteer和Node.js爬取大学招生数据：入门指南
本文介绍了如何使用Puppeteer和Node.js爬取大学招生数据，并通过代理IP提升爬取的稳定性和效率。Puppeteer作为一个强大的Node.js库，能够模拟真实浏览器访问，支持JavaScript渲染，适合复杂的爬取任务。文章详细讲解了安装Puppeteer、配置代理IP、实现爬虫代码的步骤，并提供了代码示例。此外，还给出了注意事项和优化建议，帮助读者高效地抓取和分析招生数据。
奔跑的数据
82 0
如何使用Puppeteer和Node.js爬取大学招生数据：入门指南
XIAZHI
|
1月前
|
算法
数据结构之文件系统模拟（树数据结构）
本文介绍了文件系统模拟及其核心概念，包括树状数据结构、节点结构、文件系统类和相关操作。通过构建虚拟环境，模拟文件的创建、删除、移动、搜索等操作，展示了文件系统的基本功能和性能。代码示例演示了这些操作的具体实现，包括文件和目录的创建、移动和删除。文章还讨论了该算法的优势和局限性，如灵活性高但节点移除效率低等问题。
XIAZHI
55 0
神明木佑
|
2月前
|
前端开发 JavaScript
JS-数据筛选
JS-数据筛选
神明木佑
39 7
万少！
|
2月前
|
JavaScript 数据安全/隐私保护
2024了，你会使用原生js批量获取表单数据吗
2024了，你会使用原生js批量获取表单数据吗
万少！
59 4
java冯坚持
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
32 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）

热门文章

最新文章

  • 1
    Python编程数据结构的深入理解
  • 2
    掌握Pandas核心数据结构：Series与DataFrame的四种创建方式
  • 3
    Python 中的数据结构与其他编程语言数据结构的区别
  • 4
    Python 中数据结构和算法的关系
  • 5
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
  • 6
    Pandas数据结构：Series与DataFrame
  • 7
    HashMap的底层数据结构详解
  • 8
    es采用什么数据结构
  • 9
    Java 集合江湖：底层数据结构的大揭秘！
  • 10
    Redis 5 种基础数据结构？
  • 1
    数据结构与算法 动态规划(启发式搜索、遗传算法、强化学习待完善)
    116
  • 2
    数据结构与算法 回溯
    41
  • 3
    数据结构与算法 分治
    50
  • 4
    数据结构与算法 搜索（下）
    49
  • 5
    数据结构与算法 搜索（上）
    37
  • 6
    数据结构与算法 搜索
    52
  • 7
    数据结构与算法 排序（下）
    68
  • 8
    数据结构与算法 排序（上）
    61
  • 9
    数据结构与算法 图
    37
  • 10
    数据结构与算法 树（B树，B+树，红黑树待完善）
    68

    • 相关课程

    更多
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • JavaScript入门与实战
  • JavaScript 自学手册文档教程
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • JavaScript面向对象的程序设计
  • JavaScript函数
  • JavaScript异步编程

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • Html5和Webpack2：Webpack5打包JS和样式表
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    手把手教你白嫖阿里云服务器(免费领服务器)