远子 💖 Vina

对二叉树的理解

远子 â€¢  2021å¹´02月25日 â€¢ è¯„论

二叉树:最多有俩叉儿的树;

二叉查找树:左小右大的二叉树;

树

树是一种数据结构,用来存储具有层级关系的数据。

比如省市区树:

image-20210226095853570

比如文件目录树:

├── Dockerfile
├── LICENSE
├── README.md
├── app.js
├── docs
│   └── v4
├── jobs
│   └── worker.js
├── middleware
│   └── response-time.js
├── package-lock.json
├── package.json
├── scripts
│   └── healthcheck.js
├── server.js
├── services
│   ├── index.js
│   └── v4
├── start.sh
└── tests
    └── index.test.js

二叉树

二叉树是一种特殊的树,二叉树的定义:

在计算机科学中,二叉树(Binary Tree)是每个节点最多只有两个分支的树结构。通常分支被称为 “左子树” 或 “右子树”。二叉树的分支具有左右次序,不能随意颠倒。

下图是一个有 9 个节点且深度为 3 的二叉树:

image-20210226101041610

二叉树的几个特点:

  1. 二叉树的第 i 层最多有 2^(i - 1) 个节点;
  2. 深度为 k 的二叉树最多有 2^k - 1 个节点;

除了二叉树,计算机科学中还有很多树:

image-20210225170519409

扩展:

  • 满二叉树(Full Binary Tree):一颗深度为 k 且有 2^k - 1 个节点的二叉树,称为 “满二叉树”。
  • 完全二叉树(Complete Binary Tree):在一颗二叉树中,若除最后一层外的其余层都是满的,并且最后一层要么是满的,要么在右边缺少连续若干节点,则此二叉树为完全二叉树。
  • 平衡二叉搜索树(Self-balancing Binary Search Tree):又被称为AVL树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

二叉查找树

二叉查找树是一种特殊的二叉树,二叉查找树的定义:

二叉查找树(Binary Search Tree)是一种特殊的二叉树,相对较小的值保存在左节点,较大的值保存在右节点,这一特性使得查找的效率很高。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,为 O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、多重集、关联数组等。

下图是一个有 7 个节点且深度为 3 的二叉查找树:

image-20210225165916750

操作二叉查找树

假设有以下代码:

class Node {
  constructor(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }

  show() {
    return this.data;
  }
}

class BST {
  constructor() {
    this.root = null;
  }
  
  // 插入节点
  insert(data) {}
  
  // 查找节点
  find(data) {}
  
  // 查找最小值
  findMin() {}
  
  // 查找最大值
  findMax() {}
  
  // 前序遍历
  preOrder() {}
  
  // 中序遍历
  inOrder() {}
  
  // 后序遍历
  postOrder() {}
}

其中 Node 类为二叉树上的节点,data 属性存储了节点值,left 属性存储了左子树,right 属性存储了右子树。

其中 BST 类实现了二叉查找树,root 属性存储了根节点,有 insert、find、findMin、findMax、preOrder、inOrder、postOrder、remove 等方法。

我们来一步一步实现 BST 类。

插入

先从以下测试代码梳理一下 BST 的生成过程:

const nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(100);

第一步:插入节点 23,此时 BST 为:

image-20210225165953551

第二步:插入节点 45, 45 大于 23,放在 23 右边,此时 BST 为:

image-20210225170017487

第三步:插入节点 16,16 小于 23,放在 23 左边,此时 BST 为:

image-20210225170040570

第四步:插入节点 37,37 大于 23,放在 23 的右边,同时 37 小于 45,放在 45 的左边,此时 BST 为:

image-20210225170111638

第五步:插入节点 3,3 小于 23,放在 23 的左边,同时 3 小于 16,放在 16 的左边,此时 BST 为:

image-20210225171035165

第六步:插入节点 99,99 大于 23,放在 23 的右边,同时 99 大于 45,放在 45 的右边,此时 BST 为:

image-20210225171738183

第七步:插入节点 100,100 大于 23,放在 23 的右边,同时 100 大于 45 放在 45 的右边,同时 100 大于 99,放在 99 的右边,此时 BST 为:

image-20210225171849141

至此,BST 生成结束。

下边 insert 方法的实现:

class BST {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const n = new Node(data, null, null);
    // 空树时,作为根节点
    if (this.root === null) {
      this.root = n;
    } else {
      let current = this.root;
      let parent;
      // 循环 BST,找到合适的配置
      while (true) {
        parent = current;
        if (data < current.data) {
          current = current.left;
          // 叶子节点时,执行插入,跳出循环
          if (current === null) {
            parent.left = n;
            break;
          }
        } else {
          current = current.right;
          // 叶子节点时,执行插入,跳出循环
          if (current === null) {
            parent.right = n;
            break;
          }
        }
      }
    }
  }
}

查找

因为 BST 的特性是较小的值在左子树,较大的值在右子树,因此在 BST 上查找最小值和最大值非常简单。

查找最小值时,只需要遍历左子树,直到找到最后一个节点:

class BST {
  constructor() {
    this.root = null;
  }

  findMin() {
    let current = this.root;
    while (!(current.left == null)) {
      current = current.left;
    }
    return current.data;
  }
}

查找最大值时,只需要遍历右子树,直到找到最后一个节点:

class BST {
  constructor() {
    this.root = null;
  }

  findMax() {
    let current = this.root;
    while (!(current.right == null)) {
      current = current.right;
    }
    return current.data;
  }
}

查找指定值时,核心逻辑是遍历和比较 data 和当前节点值:

class BST {
  constructor() {
    this.root = null;
  }

  find(data) {
    let current = this.root;
    while (current) {
      // 命中时,退出循环
      if (data === current.data) {
        return current;
      }
      // 继续在左子树搜索
      if (data < current.data) {
        current = current.left;
      }
      // 继续在右子树搜索
      if (data > current.data) {
        current = current.right;
      }
    }
    return null;
  }
}

遍历

遍历二叉查找树是指沿着某种执行次序,依次对树中每个节点均做一次且仅做一次访问。

遍历过程中有以下三种操作:

  • N(Node):访问节点本身(或者:访问根)
  • L(Left):访问左子树(或者:访问根的左子树)
  • R(Right):访问右子树(或者:访问根的右子树)

以上操作有六种执行次序:NLR、LNR、LRN、NRL、RNL、RLN,后三种和前三种是等价的,只不过顺序相反,估只讨论前三种。

按照 N 的位置,二叉树的遍历方式分为三种:

  • NLR 前序遍历:根节点 -> 左子树 -> 右子树。
  • LNR 中序遍历:左子树 -> 根节点 -> 右子树。(升序遍历所有节点)
  • LRN 后序遍历:左子树 -> 右子树 -> 根节点。

以上边生成的 BST 为例:

image-20210225171035165

前序遍历时,依次执行以下操作:

  1. 访问根节点
  2. 遍历左子树
  3. 遍历右子树

输出结果为:23 -> 16 -> 3 -> 45 -> 37 -> 99 -> 100,代码实现:

class BST {
  constructor() {
    this.root = null;
  }

  preOrder(node) {
    if (node !== null) {
      console.log(node.show());
      this.preOrder(node.left);
      this.preOrder(node.right);
    }
  }
}

中序遍历时,依次执行以下操作:

  1. 遍历左子树
  2. 访问根节点
  3. 遍历右子树

输出结果为:3 -> 16 -> 23 -> 37 -> 45 -> 99 -> 100,代码实现:

class BST {
  constructor() {
    this.root = null;
  }

  preOrder(node) {
    if (node !== null) {
      this.preOrder(node.left);
      console.log(node.show());
      this.preOrder(node.right);
    }
  }
}

后序遍历时,移除执行以下操作:

  1. 遍历左子树
  2. 遍历右子树
  3. 访问根节点

输出结果为:3 -> 16 -> 100 -> 37 -> 99 -> 45 -> 23,代码实现:

class BST {
  constructor() {
    this.root = null;
  }

  preOrder(node) {
    if (node !== null) {
      this.preOrder(node.left);
      this.preOrder(node.right);
      console.log(node.show());
    }
  }
}

删除

在 BST 中删除节点非常复杂,其复杂程度取决于删除哪个节点。

按照节点位置分为三种情况:

第一种情况:若被删节点(下图的节点3)是叶子节点,则被删节点的左子树和右子树均为空树。如下图:

image-20210226112531469

删除节点 3 不会破坏整个树结构,只需要将节点 3 和父节点间的关系断开即可,伪代码:node16.left = null。

第二种情况:若被删节点(节点 99)只有左子树或右子树,此时只要让节点 99 的子树挂载到节点 45 即可。如下图:

image-20210226112754055

删除节点 99 不会破坏整个树结构,伪代码:node45.right = node100。

第三种情况:若被删节点(节点 45)的左子树和右子树均不为空,为保持其他元素之间的相对位置不变,可按中序遍历保持有序进行调整。如下图:

image-20210226113305413

这种情况下有两种做法:

做法一:令被删节点 45 的左子树(节点 37)成为被删节点 45 的右子树(节点 99)的左子树。如下图:

image-20210226114017355

伪代码:

node99.left = node33;
node23.right = node99;

做法二:这种做法的逻辑是先替换再删除,分两种实现方式:

  • 实现方式一:令被删节点 45 的右子树中的最小值(节点 99)替换被删节点,然后删除节点 99。如下图:

image-20210226121943239

  • 实现方式二:令被删节点 45 的左子树中的最大值(节点 37)替换被删节点,然后删除节点37。如下图:

image-20210226122256101

可以看到这两种实现方式得到的 BST 结构不一样,但是都符合 BST 的特性。

实现二叉查找树

下边是的二叉查找树的完整实现:

class Node {
  constructor(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }

  show() {
    return this.data;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const n = new Node(data, null, null);
    if (this.root === null) {
      this.root = n;
    } else {
      let current = this.root;
      let parent;
      while (true) {
        parent = current;
        if (data < current.data) {
          current = current.left;
          if (current === null) {
            parent.left = n;
            break;
          }
        } else {
          current = current.right;
          if (current === null) {
            parent.right = n;
            break;
          }
        }
      }
    }
  }

  preOrder(node) {
    if (node !== null) {
      console.log(node.show());
      this.preOrder(node.left);
      this.preOrder(node.right);
    }
  }

  inOrder(node) {
    if (node !== null) {
      this.inOrder(node.left);
      console.log(node.show());
      this.inOrder(node.right);
    }
  }

  postOrder(node) {
    if (node !== null) {
      this.postOrder(node.left);
      this.postOrder(node.right);
      console.log(node.show());
    }
  }

  findMin() {
    let current = this.root;
    while (!(current.left == null)) {
      current = current.left;
    }
    return current.data;
  }

  findMax() {
    let current = this.root;
    while (!(current.right == null)) {
      current = current.right;
    }
    return current.data;
  }
}

BST 的测试代码:

const nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(100);
nums.preOrder(nums.root);         // 输出:23 16 3 45 37 99 100
nums.inOrder(nums.root);             // 输出:3 16 23 37 45 99 100
nums.postOrder(nums.root);         // 输出:3 16 37 100 99 45 23
console.log(nums.findMin());     // 输出:3
console.log(nums.findMax());     // 输出:100

B+ 树

排序算法中的冒泡排序,适合用于教学,但实际场景中因为效率问题,通常会使用快速排序。

二叉树很像冒泡排序,教学意义大于实际用途。

B+ 树的定义:

B+ 树是一种树数据结构,通常用语数据库和操作系统的文件系统。B+ 树的特点是能用保持数据稳定有序,其插入与修改拥有稳定的对数时间复杂度。B+ 树元素自底向上插入,这与二叉树恰好相反。

几个算法题

算法题1

给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

来源:力扣(LeetCode)

算法题2

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

img

示例 1:

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

输入:digits = ""
输出:[]

示例 3:

输入:digits = "2"
输出:["a","b","c"]

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

我要发表看法

«-必填
«-必填,不公开