五、Typescript数据结构与算法-树

树的优点

数组：

• 优点：
  • 数组的主要优点是根据下标值访问效率会很高。
  • 但是如果我们希望根据元素来查找对应的位置呢？
  • 比较好的方式是先对数组进行排序，再进行二分查找。
• 缺点：
  • 需要先对数组进行排序，生成有序数组，才能提高查找效率。
  • 另外数组在插入和删除数据时，需要有大量的位移操作(插入到首位或者中间位置的时候)，效率很低。

链表：

• 优点：
  • 链表的插入和删除操作效率都很高。
• 缺点：
  • 查找效率很低，需要从头开始依次访问链表中的每个数据项，直到找到。
  • 而且即使插入和删除操作效率很高，但是如果要插入和删除中间位置的数据，还是需要重头先找到对应的数据。

哈希表：

• 优点：
  • 哈希表的插入/查询/删除效率都是非常高的。
  • 但是哈希表也有很多缺点。
• 缺点：
  • 空间利用率不高，底层使用的是数组，并且某些单元是没有被利用的。
  • 哈希表中的元素是无序的，不能按照固定的顺序来遍历哈希表中的元素。
  • 不能快速的找出哈希表中的最大值或者最小值这些特殊的值。

树结构：

• 树综合了上面的数据结构的优点(当然优点不足于盖过其他数据结构，比如效率一般情况下没有哈希表高)。并且也弥补了上面数据结构的缺点。
• 而且为了模拟某些场景，我们使用树结构会更加方便。
• 因为数结构的非线性的，可以表示一对多的关系
• 比如文件的目录结构

术语

树（Tree）：n（n≥0）个节点构成的有限集合

• 当 n=0 时，称为空树

对于任一棵非空树（n> 0），它具备以下性质：

• 树中有一个称为“根（Root）”的特殊节点，用 r 表示

• 其余节点可分为 m(m>0)个互不相交的有限集 T1，T2，..。，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”

  1.节点的度（Degree）：节点的子树个数。

  2.树的度 （Degree） ：树的所有节点中最大的度数。

  3.叶节点（Leaf）：度为 0 的节点。(也称为叶子节点)

  4.父节点（Parent）：有子树的节点是其子树的根节点的父节点

  5.子节点（Child）：若 A 节点是 B 节点的父节点，则称 B 节点是 A 节点的子节点；子节点也称孩子节点。

  6.兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点。

  7.路径和路径长度：从节点 n1 到 nk 的路径为一个节点序列 n1 ，n2，… ，nk

• ni 是 n(i+1)的父节点

• 路径所包含 边 的个数为路径的长度。

  8.节点的层次（Level）：规定根节点在 1 层，其它任一节点的层数是其父节点的层数加 1。

  9.树的深度（Depth）：对于任意节点 n, n 的深度为从根到 n 的唯一路径长，根的深度为 0。

  10.树的高度（Height）：对于任意节点 n,n 的高度为从 n 到一片树叶的最长路径长，所有树叶的高度为 0

表示方式

普通的表示方式

儿子 - 兄弟表示方式

儿子-兄弟表示法旋转

二叉树

如果树中每个节点最多只能有两个子节点，这样的树就成为”二叉树”。

二叉树的定义

• 二叉树可以为空，也就是没有节点。
• 若不为空，则它是由根节点 和 称为其 左子树 TL 和 右子树 TR 的两个不相交的二叉树组成。

特性

一颗二叉树第 i 层的最大节点数为：2^(i-1)，i >= 1

深度为 k 的二叉树有最大节点总数为： 2^k - 1，k >= 1

对任何非空二叉树 T，若 n0 表示叶节点的个数、n2 是度为 2 的非叶节点个数，那么两者满足关系 n0 = n2 + 1

完美二叉树

完全二叉树

除二叉树最后一层外，其他各层的节点数都达到最大个数。

且最后一层从左向右的叶节点连续存在，只缺右侧若干节点。

完美二叉树是特殊的完全二叉树

存储

数组存储

链表存储

二叉搜索树

二叉搜索树的封装

class Node<T> {
  constructor(public value: T) {
    this.value = value;
  }
}

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
}
class BsTree<T> {
  root: TreeNode<T> | null = null;
}
export {};

插入

class Node<T> {
  constructor(public value: T) {
    this.value = value;
  }
}
class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
}
class BsTree<T> {
  private root: TreeNode<T> | null = null;
  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    // 递归处理
    if (newNode.value < node.value) {
      node.left === null
        ? (node.left = newNode)
        : this.insertNode(node.left, newNode);
    } else {
      node.right === null
        ? (node.right = newNode)
        : this.insertNode(node.right, newNode);
    }
  }
  insert(value: T) {
    const newNode = new TreeNode(value);
    if (!this.root) this.root = newNode;
    else this.insertNode(this.root, newNode);
  }
}

遍历

import { Node } from "../types/INode";
class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
}
class BsTree<T> {
  private root: TreeNode<T> | null = null;
  // 前序
  preOrderTraverse() {
    this.preOrderTraverseNode(this.root);
  }
  private preOrderTraverseNode(node: TreeNode<T> | null) {
    if (!node) return null;
    else {
      console.log(node.value);
      this.preOrderTraverseNode(node.left);
      this.preOrderTraverseNode(node.right);
    }
  }
  // 中序
  inOrderTraverse() {
    this.inOrderTraverseNode(this.root);
  }
  private inOrderTraverseNode(node: TreeNode<T> | null) {
    if (!node) return null;
    else {
      this.inOrderTraverseNode(node.left);
      console.log(node.value);
      this.inOrderTraverseNode(node.right);
    }
  }
  // 后序
  postOrderTraverse() {
    this.postOrderTraverseNode(this.root);
  }
  private postOrderTraverseNode(node: TreeNode<T> | null) {
    if (!node) return null;
    else {
      this.postOrderTraverseNode(node.left);
      this.postOrderTraverseNode(node.right);
      console.log(node.value);
    }
  }
  // 层序
  levelOrderTraverse() {
    if (!this.root) return;
    const queue: TreeNode<T>[] = [this.root];
    while (queue.length) {
      const current = queue.shift();
      console.log(current?.value);
      current?.left && queue.push(current.left);
      current?.right && queue.push(current.right);
    }
  }
}

最大值 最小值 搜索

class Node<T> {
  constructor(public value: T) {
    this.value = value;
  }
}
class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
}
class BsTree<T> {
  private root: TreeNode<T> | null = null;
  // 最大值
  getMax() {
    let current = this.root;
    while (current && current.right) {
      current = current.right;
    }
    return current?.value ?? null;
  }
  // 最小值
  getMin() {
    let current = this.root;
    while (current && current.left) {
      current = current.left;
    }
    return current?.value ?? null;
  }
  // 搜索
  search(value: T) {
    let current = this.root;
    while (current) {
      if (current.value === value) return true;
      else if (current.value < value) current = current.right;
      else current = current.left;
    }
    return false;
  }
}

删除

删除操作分很多种情况

1、删除子节点：

• 要拿到此子节点，同时拿到此节点的父节点，
• 如果是右子节点，父节点.right = null
• 如果是左子节点，父节点.left = null

先找到对应节点及父节点

remove(value: T) {
    let current = this.root;
    let parent: TreeNode<T> | null = null;
    while (current) {
      if (current.value === value) break;
      parent = current;
      if (current.value < value) current = current.right;
      else current = current.left;
    }
    console.log(current?.value, parent?.value);
  }

这段代码是和 search 有重复部分的

// 搜索
  search(value: T) {
    let current = this.root;
    while (current) {
      if (current.value === value) return true;
      else if (current.value < value) current = current.right;
      else current = current.left;
    }
    return false;
  }

所以可以抽离函数

private searchNode(value: T) {
    let current = this.root;
    let parent: TreeNode<T> | null = null;
    while (current) {
      if (current.value === value) return current;
      parent = current;
      if (current.value < value) current = current.right;
      else current = current.left;
    }
  }

search 可以修改为

// 搜索
  search(value: T) {
    return !!this.searchNode(value);
  }

那 parent 如何获取呢？

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;

  // remove 寻找父节点
  parent: TreeNode<T> | null;
}

修改 searchNode

private searchNode(value: T) {
  let current = this.root;
  let parent: TreeNode<T> | null = null;
  while (current) {
    if (current.value === value) return current;
    parent = current;
    if (current.value < value) current = current.right;
    else current = current.left;
    if (current) current.parent = parent;
  }
  return null;
}

修改 remove

remove(value: T) {
    const current = this.searchNode(value);
    console.log(current?.value, current?.parent?.value);
  }

判断左右节点封装

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;

  // remove 寻找父节点
  parent: TreeNode<T> | null = null;

  isLeft() {
    return this.parent?.left === this;
  }
  isRight() {
    return this.parent?.right === this;
  }
}

情况一：删除叶子结点

remove(value: T) {
   const current = this.searchNode(value);
   if (!current) return false;
   const parent = current?.parent;

   // 叶子结点
   if (current.left === null && current.right === null) {
     // 判断根节点
     if (current === this.root) this.root = null;
     else if (current.isLeft) parent!.left = null;
     else parent!.right = null;
   }
   return true;
 }

情况二：有一个子节点为左子结点

remove(value: T) {
    const current = this.searchNode(value);
    if (!current) return false;
    const parent = current?.parent;

    // 叶子结点
    if (current.left === null && current.right === null) {
      // 判断根节点
      if (current === this.root) this.root = null;
      else if (current.isLeft) parent!.left = null;
      else parent!.right = null;
    }
    // 只有一个子节点 为左节点
    else if (current.right === null) {
      if (current === this.root) this.root = current.left;
      else if (current.isLeft) parent!.left = current.left;
      else parent!.right = current.left;
    }
    return true;
  }

情况三：有一个子节点为右子结点

remove(value: T) {
  const current = this.searchNode(value);
  if (!current) return false;
  const parent = current?.parent;

  // 叶子结点
  if (current.left === null && current.right === null) {
    // 判断根节点
    if (current === this.root) this.root = null;
    else if (current.isLeft) parent!.left = null;
    else parent!.right = null;
  }
  // 只有一个子节点 为左节点
  else if (current.right === null) {
    if (current === this.root) this.root = current.left;
    else if (current.isLeft) parent!.left = current.left;
    else parent!.right = current.left;
  }
  // 只有一个子节点 为右节点
  else if (current.left === null) {
    if (current === this.root) this.root = current.right;
    else if (current.isLeft) parent!.left = current.right;
    else parent!.right = current.right;
  }
  return true;
}

情况四：有两个字节点

前驱&后继

• 在二叉搜索树中，这两个特别的节点，有两个特别的名字。
• 比 current 小一点点的节点，称为 current 节点的前驱。
• 比 current 大一点点的节点，称为 current 节点的后继。
• 也就是为了能够删除有两个子节点的 current，要么找到它的前驱，要么找到它的后继。
• 所以，找到这样的节点(前驱或者后继都可以，以找后继为例)

// 两个子节点
    else {
      const successorNode = this.successorNode(current);
      if (current === this.root) this.root = successorNode;
      else if (current.isLeft) parent!.left = successorNode;
      else parent!.right = successorNode;
    }

// 寻找后继节点
private successorNode(delNode: TreeNode<T>) {
    let current = delNode.right;
    // 后继结点
    let successor: TreeNode<T> | null = null;
    while (current) {
      successor = current;
      current = current.left;
      if (current) current.parent = successor;
    }
    /**
     * 如果删除节点的right不等于后继结点
     * 删除节点的right赋给后继结点的right
     */
    if (successor !== delNode.right) {
      /**
       * 后继结点如果有右子节
       * 要把右子节点放到后继结点的父节点的左节点上
       */
      successor!.parent!.left = successor!.right;
      successor!.right = delNode.right;
    }
    // 删除节点的left赋给后继结点的left
    successor!.left = delNode.left;
    return successor;
  }

完整代码

class Node<T> {
  constructor(public value: T) {
    this.value = value;
  }
}
class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  // remove 寻找父节点
  parent: TreeNode<T> | null = null;
  get isLeft() {
    return this.parent?.left === this;
  }
  get isRight() {
    return this.parent?.right === this;
  }
}
class BsTree<T> {
  private root: TreeNode<T> | null = null;

  // 寻找后继节点
  private successorNode(delNode: TreeNode<T>) {
    let current = delNode.right;
    // 后继结点
    let successor: TreeNode<T> | null = null;
    while (current) {
      successor = current;
      current = current.left;
      if (current) current.parent = successor;
    }
    /**
     * 如果删除节点的right不等于后继结点
     * 删除节点的right赋给后继结点的right
     */
    if (successor !== delNode.right) {
      /**
       * 后继结点如果有右子节
       * 要把右子节点放到后继结点的父节点的左节点上
       */
      successor!.parent!.left = successor!.right;
      successor!.right = delNode.right;
    }
    // 删除节点的left赋给后继结点的left
    successor!.left = delNode.left;
    return successor;
  }
  // 删除节点
  remove(value: T) {
    const current = this.searchNode(value);
    if (!current) return false;
    const parent = current?.parent;

    // 叶子结点
    if (current.left === null && current.right === null) {
      // 判断根节点
      if (current === this.root) this.root = null;
      else if (current.isLeft) parent!.left = null;
      else parent!.right = null;
    }
    // 只有一个子节点 为左节点
    else if (current.right === null) {
      if (current === this.root) this.root = current.left;
      else if (current.isLeft) parent!.left = current.left;
      else parent!.right = current.left;
    }
    // 只有一个子节点 为右节点
    else if (current.left === null) {
      if (current === this.root) this.root = current.right;
      else if (current.isLeft) parent!.left = current.right;
      else parent!.right = current.right;
    }
    // 两个子节点
    else {
      const successorNode = this.successorNode(current);
      if (current === this.root) this.root = successorNode;
      else if (current.isLeft) parent!.left = successorNode;
      else parent!.right = successorNode;
    }
    return true;
  }
}

优化：

看以上代码有很多重复地方

比如

if (current === this.root) this.root =
else if (current.isLeft) parent!.left =
else parent!.right =

这一段出现很多次，可以定义一个变量来优化

 remove(value: T) {

  const current = this.searchNode(value);
  if (!current) return false;

  let replaceNode: TreeNode<T> | null = null;
  // 叶子结点
  if (current.left === null && current.right === null) replaceNode = null;
  // 只有一个子节点 为左节点
  else if (current.right === null) replaceNode = current.left;
  // 只有一个子节点 为右节点
  else if (current.left === null) replaceNode = current.right;
  // 两个子节点
  else replaceNode = this.successorNode(current);

  if (current === this.root) this.root = replaceNode;
  else if (current.isLeft) current.parent!.left = replaceNode;
  else current.parent!.right = replaceNode;
  return true;
}

最终代码

import { btPrint } from "hy-algokit";
class Node<T> {
  constructor(public value: T) {
    this.value = value;
  }
}
class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  // remove 寻找父节点
  parent: TreeNode<T> | null = null;
  // 判断是否为左节点
  get isLeft() {
    return this.parent?.left === this;
  }
  get isRight() {
    return this.parent?.right === this;
  }
}
class BsTree<T> {
  private root: TreeNode<T> | null = null;
  // 打印树操作
  print() {
    btPrint(this.root);
  }
  // 插入操作 递归寻找符合条件节点
  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    // 递归处理
    if (newNode.value < node.value) {
      node.left === null
        ? (node.left = newNode)
        : this.insertNode(node.left, newNode);
    } else {
      node.right === null
        ? (node.right = newNode)
        : this.insertNode(node.right, newNode);
    }
  }
  // 插入操作
  insert(value: T) {
    const newNode = new TreeNode(value);
    if (!this.root) this.root = newNode;
    else this.insertNode(this.root, newNode);
  }
  // 前序
  preOrderTraverse() {
    this.preOrderTraverseNode(this.root);
  }
  private preOrderTraverseNode(node: TreeNode<T> | null) {
    if (!node) return null;
    else {
      console.log(node.value);
      this.preOrderTraverseNode(node.left);
      this.preOrderTraverseNode(node.right);
    }
  }
  // 中序
  inOrderTraverse() {
    this.inOrderTraverseNode(this.root);
  }
  private inOrderTraverseNode(node: TreeNode<T> | null) {
    if (!node) return null;
    else {
      this.inOrderTraverseNode(node.left);
      console.log(node.value);
      this.inOrderTraverseNode(node.right);
    }
  }
  // 后序
  postOrderTraverse() {
    this.postOrderTraverseNode(this.root);
  }
  private postOrderTraverseNode(node: TreeNode<T> | null) {
    if (!node) return null;
    else {
      this.postOrderTraverseNode(node.left);
      this.postOrderTraverseNode(node.right);
      console.log(node.value);
    }
  }
  // 层序
  levelOrderTraverse() {
    if (!this.root) return;
    const queue: TreeNode<T>[] = [this.root];
    while (queue.length) {
      const current = queue.shift();
      console.log(current?.value);
      current?.left && queue.push(current.left);
      current?.right && queue.push(current.right);
    }
  }
  // 最大值
  getMax() {
    let current = this.root;
    while (current && current.right) {
      current = current.right;
    }
    return current?.value ?? null;
  }
  // 最小值
  getMin() {
    let current = this.root;
    while (current && current.left) {
      current = current.left;
    }
    return current?.value ?? null;
  }
  // 搜索符合条件节点
  private searchNode(value: T) {
    let current = this.root;
    let parent: TreeNode<T> | null = null;
    while (current) {
      if (current.value === value) return current;
      parent = current;
      if (current.value < value) current = current.right;
      else current = current.left;
      if (current) current.parent = parent;
    }
    return null;
  }
  // 搜索操作
  search(value: T) {
    return !!this.searchNode(value);
  }
  // 寻找后继节点
  private successorNode(delNode: TreeNode<T>) {
    let current = delNode.right;
    // 后继结点
    let successor: TreeNode<T> | null = null;
    while (current) {
      successor = current;
      current = current.left;
      if (current) current.parent = successor;
    }
    /**
     * 如果删除节点的right不等于后继结点
     * 删除节点的right赋给后继结点的right
     */
    if (successor !== delNode.right) {
      /**
       * 后继结点如果有右子节
       * 要把右子节点放到后继结点的父节点的左节点上
       */
      successor!.parent!.left = successor!.right;
      successor!.right = delNode.right;
    }
    // 删除节点的left赋给后继结点的left
    successor!.left = delNode.left;
    return successor;
  }
  // 删除操作
  remove(value: T) {
    const current = this.searchNode(value);
    if (!current) return false;

    let replaceNode: TreeNode<T> | null = null;
    // 叶子结点
    if (current.left === null && current.right === null) replaceNode = null;
    // 只有一个子节点 为左节点
    else if (current.right === null) replaceNode = current.left;
    // 只有一个子节点 为右节点
    else if (current.left === null) replaceNode = current.right;
    // 两个子节点
    else replaceNode = this.successorNode(current);

    if (current === this.root) this.root = replaceNode;
    else if (current.isLeft) current.parent!.left = replaceNode;
    else current.parent!.right = replaceNode;
    return true;
  }
}

二叉搜索树的缺陷

二叉搜索树作为数据存储的结构有重要的优势：

可以快速地找到给定关键字的数据项 并且可以快速地插入和删除数据项。

但是，二叉搜索树有一个很麻烦的问题：

• 如果插入的数据时有序的数据，比如下面的情况
• 有一棵初始化为 9 8 12 的二叉树
• 插入下面的数据：7 6 5 4 3

非平衡树：

• 比较好的二叉搜索树数据应该是左右分布均匀的
• 但是插入连续数据后，分布的不均匀，我称这种树为非平衡树。
• 对于一棵平衡二叉树来说，插入/查找等操作的效率是 O(logN)
• 对于一棵非平衡二叉树，相当于编写了一个链表，查找效率变成了 O(N)

树的平衡性

为了能以较快的时间 O(logN)来操作一棵树，我们需要保证树总是平衡的：

至少大部分是平衡的，那么时间复杂度也是接近 O(logN)的

也就是说树中每个节点左边的子孙节点的个数，应该尽可能的等于右边的子孙节点的个数。

常见的平衡树

AVL 树：

• AVL 树是最早的一种平衡树。它有些办法保持树的平衡(每个节点多存储了一个额外的数据)
• 因为 AVL 树是平衡的，所以时间复杂度也是 O(logN)。
• 但是，每次插入/删除操作相对于红黑树效率都不高，所以整体效率不如红黑树

红黑树：

• 红黑树也通过一些特性来保持树的平衡
• 因为是平衡树，所以时间复杂度也是在 O(logN)。
• 另外插入/删除等操作，红黑树的性能要优于 AVL 树，所以现在平衡树的应用基本都是红黑树。