《学习JavaScript数据结构与算法》-- 7.树(笔记)

爱学习的程序媛

发布于 2022-04-07 16:18:18

3870

发布于 2022-04-07 16:18:18

文章被收录于专栏：学习/读书笔记

树是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点，每个节点都有一个父节点（除了根节点）以及0个或多个子节点。位于树顶部的节点叫作根节点，它没有父节点。

树中的每个元素都叫作节点（或键），节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点，没有子节点的节点称为外部节点或叶节点。

一个节点可以有祖先和后代。一个节点（除了根节点）的祖先包括父节点、祖父节点、曾祖父节点等，一个节点的后代包含子节点、孙子节点、曾孙节点等。子树由节点和它的后代构成。

节点的一个属性是深度，节点的深度取决于它的祖先节点的数量。树的高度取决于所有节点深度的最大值。一棵树也可以被分解成层级，根节点在第0层，它的子节点在第1层，以此类推。

7.1 二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点，一个是左侧子节点，另一个是右侧子节点。

二叉搜索树（BST），是二叉树的一种，只允许在左侧子节点存储比父节点小的值，在右侧子节点存储比父节点大的值。

我们通过两个指针（引用）来表示节点之间的关系，一个指向左侧子节点，另一个指向右侧子节点。

7.1.1 创建二叉搜索树

// 创建二叉搜索树类
class BinarySearchTree {
    constructor(compareFn = defaultCompare) {
        this.compareFn = compareFn;
        this.root = undefined;
    }
}
// 创建节点类
class Node {
    constructor(key) {
        this.key = key;//节点值
        this.left = undefined;//左侧子节点引用
        this.right = undefined;//右侧子节点引用
    }
    toString() {
        return `${this.key}`;
    }
}

7.1.2 向二叉搜索树中插入一个节点（键）

insert(key) {
    if (this.root == null) {
        this.root = new Node(key);
    } else {
        this.insertNode(this.root, key);
    }
}
insertNode(node, key) {
    if (this.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);
    }
}

通过二叉搜索树类BinarySearchTree生成实例二叉搜索树binarySearchTree后，向二叉搜索树binarySearchTree中依次添加节点（键）：11、7、15、5、3、9、8、10、13、12、14、20、18、25，二叉搜索树binarySearchTree的结构如图：

向二叉搜索树binarySearchTree中再插入一个节点（键）6，二叉搜索树binarySearchTree的结构如图：

7.2 树的遍历

遍历一颗树是指访问树的每个节点并对它们进行某种操作的过程。

7.2.1 中序遍历

中序遍历是一种以上行顺序访问BST所有节点的遍历方式，也就是从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。

inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
}
inOrderTraverseNode(node, callback) {
    if (node != null) {
        this.inOrderTraverseNode(node.left, callback);
        callback(node.key);
        this.inOrderTraverseNode(node.right, callback);
    }
}

7.2.2 先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。

preOrderTraverse(callback) {
    this.preOrderTraverseNode(this.root, callback);
}
preOrderTraverseNode(node, callback) {
    if (node != null) {
        callback(node.key);
        this.preOrderTraverseNode(node.left, callback);
        this.preOrderTraverseNode(node.right, callback);
    }
}

7.2.3 后序遍历

后序遍历是先访问节点的后代节点，再访问节点本身。后序遍历的一种应用是计算一个目录及子目录中所有文件所占空间的大小。

postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
}
postOrderTraverseNode(node, callback) {
    if (node != null) {
        this.postOrderTraverseNode(node.left, callback);
        this.postOrderTraverseNode(node.right, callback);
        callback(node.key);
    }
}

7.3 搜索树中的值

7.3.1 搜索树中的最小值

min() {
    return this.minNode(this.root);
}
minNode(node) {
    let current = node;
    while (current != null && current.left != null) {
        current = current.left;
    }
    return current;
}

7.3.2 搜索树中的最大值

max() {
    return this.maxNode(this.root);
}
maxNode(node) {
    let current = node;
    while (current != null && current.right != null) {
        current = current.right;
    }
    return current;
}

7.3.3 搜索树中特定的值

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);
    }
    if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
        return this.searchNode(node.right, key);
    }
    return true;
}

7.4 移除一个节点

7.4.1 移除一个叶节点

7.4.2 移除有一个左侧或右侧节点的节点

7.4.3 移除有两个子节点的节点

remove(key) {
    this.root = this.removeNode(this.root, key);
}
removeNode(node, key) {
    if (node == null) {
        return undefined;
    }
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
        node.left = this.removeNode(node.left, key);
        return node;
    }
    if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
        node.right = this.removeNode(node.right, key);
        return node;
    }
    // 移除一个叶节点
    if (node.left == null && node.right == null) {
        node = undefined;
        return node;
    }
    // 移除有一个左侧或右侧节点的节点
    if (node.left == null) {
        node = node.right;
        return node;
    }
    if (node.right == null) {
        node = node.left;
        return node;
    }
    // 移除有两个子节点的节点
    const aux = this.minNode(node.right);
    node.key = aux.key;
    node.right = this.removeNode(node.right, aux.key);
    return node;
}

7.5 自平衡树

BST存在一个问题：取决于添加的节点树，树的一条边可能会非常深。也就是说，树的一条分支会有很多层，而其他的分支却只有几层。

这会在需要在某条边上添加、移除和搜索某个节点时引起一些性能问题。为了解决这个问题，可以使用自平衡二叉搜索树（Adelson-Velskii-Landi，AVL树）。添加或移除节点时，AVL树会尝试保持自平衡，任意一个节点的左子树和右子树高度最多相差1。

在AVL树中插入或移除节点和BST完全相同，只是AVL需要检验树的平衡因子，如果需要，会将其逻辑应用于树的自平衡。

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

7.5.1 创建自平衡树

// 声明一些用来作为计数器的常量
const BalanceFactor = {
    UNBALANCED_RIGHT: 1,
    SLIGHTLY_UNBALANCED_RIGHT: 2,
    BALANCED: 3,
    SLIGHTLY_UNBALANCED_LEFT: 4,
    UNBALANCED_LEFT: 5
};
// AVLTree类 继承 BinarySearchTree类
class AVLTree extends BinarySearchTree {
    constructor(compareFn = defaultCompare) {
        super(compareFn);
        this.compareFn = compareFn;
        this.root = null;
    }
}

7.5.2 计算一个节点高度

getNodeHeight(node) {
    if (node == null) {
        return -1;
    }
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
}

7.5.3 计算一个节点的平衡因子

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;
    }
}

7.5.4 平衡操作--AVL旋转

向AVL树插入节点时，可以执行单旋转或双旋转两种平衡操作，分别对应四种场景。

a. 左-左(LL)：向右的单旋转

这种情况出现于节点的左侧子节点的高度大于右侧子节点的高度，并且左侧子节点也是平衡或左侧较重的。

rotationLL(node) {
    const tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
}

b. 右-右(RR)：向左的单旋转

这种情况出现于节点的右侧子节点的高度大于左侧子节点的高度，并且右侧子节点也是平衡或右侧较重的。

rotationRR(node) {
    const tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    return tmp;
 }

c. 左-右(LR)：向右的双旋转

这种情况出现于左侧子节点的高度大于右侧子节点的高度，并且左侧子节点右侧较重。

rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
}

d. 右-左(RL)：向左的双旋转

这种情况出现于右侧子节点的高度大于左侧子节点的高度，并且右侧子节点左侧较重。

rotationRL(node) {
    node.right = this.rotationLL(node.right);
    return this.rotationRR(node);
}

7.5.5 向AVL树插入节点

insert(key) {
    this.root = this.insertNode(this.root, key);
}
insertNode(node, key) {
    if (node == null) {
        return new Node(key);
    }
    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;
}

7.5.6 从AVL树中移除节点

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

详细代码：

https://github.com/chenxiaohuan117/learning-javasrcipt-note/tree/main/%E3%80%8A%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E3%80%8B(%E7%AC%AC3%E7%89%88)

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-11，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法