温叶博客 - 树
type: channel
link: https://www.wenye123.com/tag/树/
items: Trie树/字典树
items: 平衡二叉树
items: 二叉排序树

Trie树/字典树
type: item
date: 2023-05-28T18:32:49+08:00
description: 介绍Tire树又称字典树/前缀树，具有如下特点根节点不包含字符 除根节点外每个节点只包含一个字符树的每一个路径都是一个字符串每个节点的子节点包含的字符都不相同用途利用字符串的公共前缀来降低查找的时间，常用于搜索系统文本词频统计实现type TrieMap = { [key: string]: any; } & { isEnd?: boolean }; class Trie { private map: TrieMap; constructor() { this.map = {}; } insert(word: string): void { let map = this.map; // 不断向下深入 for (let w of word) { if (map[w] === undefined) { map[w] = {}; } map = map[w]; } map.isEnd = true; } search(word: string): boolean { let map = this.map; for (let w of word) { if (map[w] === undefined) return false; map = map[w]; } return map.isEnd === true; } startsWith(prefix: string): boolean { let map = this.map; for (let w of prefix) { if (map[w] === undefined) return false; map = map[w]; } return true; } }

平衡二叉树
type: item
date: 2023-05-28T18:16:00+08:00
description: 介绍定义平衡二叉树又叫平衡二叉排序树，听名字知道和二叉排序树相关。实际上平衡二叉树就是每个节点最大高度差为1的二叉排序树。相比较二叉排序树，平衡二叉树查找，插入和删除的时间复杂度都维持在O(logn)。不了解二叉排序树的可以看看我的上一篇文章二叉排序树平衡因子节点左右子树的高度差就是平衡因子，值只能为0, -1和1，分别对应左右等高，右比左高，左比右高。叶子节点的平衡因子始终为0最小失衡树新插入的节点向上查找，第一个平衡因子绝对值超过1的节点为根的子树，比如上图中最小失衡树就是66。新增和删除节点都会导致树的失衡，失衡调整就是通过旋转最小失衡树来降低高度，旋转方向有左旋和右旋。失衡调整的四种情况LL插入描述: 根节点平衡因子为+2，左节点平衡因子为+1旋转方向: 右旋最终结果: 左节点上位具体操作:根节点的左节点替换根节点位置根节点的左节点的右子树变成根节点的左子树根节点本身变成左节点的右子树RR插入描述: 根节点平衡因子为-2，右节点平衡因子为-1旋转方向: 左旋最终结果: 右节点上位具体操作:根节点的右节点替换根节点位置根节点的右节点的左子树变成根节点的右子树根节点本身变成右节点的左子树LR插入描述: 根节点平衡因子为+2，左节点平衡因子为-1旋转方向: 左节点左旋再根节点右旋最终结果: 左节点的右节点上位具体操作:左节点左旋再根节点右旋RL插入描述: 根节点平衡因子为-2，右节点平衡因子为+1旋转方向: 右节点右旋再根节点左旋最终结果: 右节点的左节点上位具体操作:右节点右旋再根节点左旋实现因为采用typescript所以先定义好类型，可以看到相比较二叉排序树多了个深度属性，主要是方便计算平衡因子. export class AVLTreeNode<T = number> { val: T; left: AVLTree<T>; right: AVLTree<T>; depth: number; constructor(val: T, left?: AVLTree<T>, right?: AVLTree<T>) { this.val = val; this.left = left ? left : null; this.right = right ? right : null; this.depth = 1; } } export type AVLTree<T = number> = AVLTreeNode<T> | null;旋转操作旋转是保证平衡二叉树高度平衡的必要操作，以至于不会出现二叉排序树那种斜树的情况/** 获取树的深度 */ export function getAVLTreeDepth<T>(root: AVLTree<T>): number { if (root === null) return 0; return root.depth; } /** 更新树的深度 */ export function updateAVLTreeDepth<T>(root: AVLTree<T>) { if (root === null) throw new Error("非法节点"); root.depth = Math.max(getAVLTreeDepth(root.left), getAVLTreeDepth(root.right)) + 1; } /** 获取节点的平衡因子 */ export function getAVLTreeNodeBalance<T>(node: AVLTree<T>) { if (node === null) throw new Error("非法节点"); return getAVLTreeDepth(node.left) - getAVLTreeDepth(node.right); } /** 左旋 */ export function leftRotate<T>(root: AVLTree<T>) { if (root === null) return null; // 旋转调整 const newRoot = root.right!; const newRootLeft = newRoot.left; root.right = newRootLeft; // 根节点的右节点的左子树变成根节点的右子树 newRoot.left = root; // 根节点本身变成右节点的左子树 // 调整新老根节点的深度 newRootLeft深度不会改变无须调整 updateAVLTreeDepth(root); updateAVLTreeDepth(newRoot); // 返回新的根节点 return newRoot; } /** 右旋 */ export function rightRo…

二叉排序树
type: item
date: 2023-05-28T18:08:00+08:00
description: 介绍二叉排序树又称二叉搜索树，听名字都知道是方便排序和查找的树定义可以是一颗空树 或者是具有如下性质的二叉树若左子树不空 则左子树上所有节点的值都小于根节点的值若右子树不空 则右子树上所有节点的值都大于根节点的值它的左右子树也都是二叉排序树特点中序遍历是一个有序序列，比如上图的中序遍历结果是: [1, 3, 4, 6, 7, 8, 9, 10, 13, 14]查找复杂度取决于深度，好的话是二叉树的O(logn)，坏的话就是斜树的O(n)实现这里采用typescript实现，所以先定义好类型export class BSTreeNode<T = number> { val: T; left: BSTree<T>; right: BSTree<T>; constructor(val: T, left?: BSTree<T>, right?: BSTree<T>) { this.val = val; this.left = left ? left : null; this.right = right ? right : null; } } export type BSTree<T = number> = BSTreeNode<T> | null;新增如果新增节点的值比当前节点大，则插入到节点右边，小则插入到左边/** 新增节点: 作为叶子节点插入 */ export function insertBSTreeNode<T>(root: BSTree<T>, val: T): BSTree<T> { if (root === null) return new BSTreeNode(val); if (val < root.val) { if (root.left === null) { root.left = new BSTreeNode(val); } else { insertBSTreeNode(root.left, val); } } else { if (root.right === null) { root.right = new BSTreeNode(val); } else { insertBSTreeNode(root.right, val); } } return root; }通过数组构建二叉排序树其实就是遍历数组的值不断新增即可/** 构建二叉排序树 */ export function createBSTree<T>(arr: T[]): BSTree<T> { if (arr.length === 0 || arr[0] === null) return null; const root = new BSTreeNode(arr[0]); for (let i = 1; i < arr.length; i++) { insertBSTreeNode(root, arr[i]); } return root; }遍历二叉排序树这里通过中序遍历 直接获得一个有序序列/** 遍历二叉排序树: 中序遍历 */ export function traverseBSTree<T>(root: BSTree<T>): T[] { if (root === null) return []; const arr: T[] = []; const left = traverseBSTree(root.left); arr.push(...left, root.val); const right = traverseBSTree(root.right); return [...arr, ...right]; }查找节点其实就是通过判断大小来查找，如果比当前节点大就在右子树查找，否则左子树查找/** 查找节点 */ export function findBSTressNode<T>(root: BSTree<T>, val: T): BSTree<T> { if (root === null) return null; if (root.val === val) return root; if (val < root.val) return findBSTressNode(root.left, val); return findBSTressNode(root.right, val); }一些特性方法前驱后驱的意思是有序序列下的上一个节点和下一个节点，比如上图中8的前驱节点是7，后驱节点是9。其中获取前后驱节点在删除方法时候需要用到/** 获取树的最小节点 */ export function getMinBSTreeNode<T>(root: BSTree<T>): BSTree<T> { if (root === null)…