介绍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; } }
介绍定义平衡二叉树又叫平衡二叉排序树，听名字知道和二叉排序树相关。实际上平衡二叉树就是每个节点最大高度差为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 rightRotate<T>(root: AVLTree<T>) { if (root === null) return null; // 旋转调整 const newRoot = root.left!; const newRootRight = newRoot.right; root.left = newRootRight; // 根节点的左节点的右子树变成根节点的左子树 newRoot.right = root; // 根节点本身变成左节点的右子树 // 调整新老根节点的深度 newRootLeft深度不会改变无须调整 updateAVLTreeDepth(root); updateAVLTreeDepth(newRoot); // 返回新的根节点 return newRoot; } /** 保持树平衡 */ export function keepAVLTreeBalance<T>(root: AVLTree<T>) { if (root === null) return null; // 旋转操作 const balance = getAVLTreeNodeBalance(root); if (balance < -1) { if (getAVLTreeNodeBalance(root.right) > 0) { root.right = rightRotate(root.right); // 节点右节点平衡因子大于0则右旋 } return leftRotate(root); // 平衡因子小于-1则左旋 } if (balance > 1) { if (getAVLTreeNodeBalance(root.left) < 0) { root.left = leftRotate(root.left); // 节点左节点平衡因子小于0则左旋 } return rightRotate(root); // 平衡因子大于1则右旋 } return root; }新增操作和二叉排序树几乎一样，唯一区别就是每次新增完节点需要更新下父节点深度，然后对父节点进行一次旋转操作/** 新增节点 */ export function insertAVLTreeNode<T>(root: AVLTree<T>, val: T): AVLTree<T> { if (root === null) return new AVLTreeNode(val); if (val < root.val) { root.left = insertAVLTreeNode(root.left, val); } else { root.right = insertAVLTreeNode(root.right, val); } // 修改节点的深度 updateAVLTreeDepth(root); // 返回平衡后的结果 return keepAVLTreeBalance(root); }构建平衡二叉树和二叉排序树一样，只不过因为根节点会变，所以需要不断赋新值export function createAVLTree<T>(arr: T[]): AVLTree<T> { if (arr.length === 0 || arr[0] === null) return null; let root: AVLTree<T> = new AVLTreeNode(arr[0]); for (let i = 1; i < arr.length; i++) { root = insertAVLTreeNode(root, arr[i]); // 根节点需要重新赋值 } return root; }遍历平衡二叉树和二叉排序树一样，就是中序遍历获取有序序列/** 遍历平衡二叉树: 中序遍历 */ export function traverseAVLTree<T>(root: AVLTree<T>): T[] { if (root === null) return []; const arr: T[] = []; const left = traverseAVLTree(root.left); arr.push(...left, root.val); const right = traverseAVLTree(root.right); return [...arr, ...right]; }查找节点同二叉排序树，通过比较大小查找/** 查找节点 */ export function findAVLTressNode<T>(root: AVLTree<T>, val: T): AVLTree<T> { if (root === null) return null; if (root.val === val) return root; if (val < root.val) return findAVLTressNode(root.left, val); return findAVLTressNode(root.right, val); }删除节点也是同二叉排序树一样，只不过删除后的父节点多了更新深度和旋转的操作/** 获取树的最小节点 */ export function getMinAVLTreeNode<T>(root: AVLTree<T>): AVLTree<T> { if (root === null) return null; if (root.left === null) return root; return getMinAVLTreeNode(root.left); } /** 获取树的最大节点 */ export function getMaxAVLTreeNode<T>(root: AVLTree<T>): AVLTree<T> { if (root === null) return null; if (root.right === null) return root; return getMaxAVLTreeNode(root.right); } /** 获取前驱节点: 左子节点树的最大值 */ export function getPrevAVLTreeNode<T>(root: AVLTree<T>): AVLTree<T> { if (root === null) return null; if (root.left === null) return null; return getMaxAVLTreeNode(root.left); } /** 获取后驱节点: 右子节点树的最小值 */ export function getNextAVLTressNode<T>(root: AVLTree<T>): AVLTree<T> { if (root === null) return null; if (root.right === null) return null; return getMinAVLTreeNode(root.right); } /** 删除节点 1. 叶子节点: 直接删除 2. 节点只有左子树或者右子树: 节点删除 将节点的左子树或者右子树移到删除节点的位置上 3. 节点既有左子树也有右子树: 找到节点的前驱/后继节点替换该节点 并删除前驱/后继节点(递归删除) 删除完调整树的平衡 */ export function removeAVLTreeNode<T>(root: AVLTree<T>, val: T): AVLTree<T> { if (root === null) return null; if (root.val === val) { if (root.left === null && root.right === null) { // 叶子节点 return null; } else if (root.left === null) { // 只存在右子树 return root.right; } else if (root.right === null) { // 只存在左子树 return root.left; } else { // 既存在左子树也存在右子树 这里采用寻找后继节点替换的方式 const nextNode = getNextAVLTressNode(root)!; root.val = nextNode.val; // 将后继节点的值赋值给当前节点 root.right = removeAVLTreeNode(root.right, nextNode.val); // 递归删除后继节点 } } else if (root.val > val) { root.left = removeAVLTreeNode(root.left, val); } else { root.right = removeAVLTreeNode(root.right, val); } // 修改节点的深度 updateAVLTreeDepth(root); // 返回平衡后的结果 return keepAVLTreeBalance(root); }总结其实相比较二叉排序树，平衡二叉树就是通过旋转操作让树的深度不会无限递增，将查找复杂度降低到了O(logn)级别。除了新增和删除需要旋转下树外，其他并没有什么区别。
介绍二叉排序树又称二叉搜索树，听名字都知道是方便排序和查找的树定义可以是一颗空树 或者是具有如下性质的二叉树若左子树不空 则左子树上所有节点的值都小于根节点的值若右子树不空 则右子树上所有节点的值都大于根节点的值它的左右子树也都是二叉排序树特点中序遍历是一个有序序列，比如上图的中序遍历结果是: [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) return null; if (root.left === null) return root; return getMinBSTreeNode(root.left); } /** 获取树的最大节点 */ export function getMaxBSTreeNode<T>(root: BSTree<T>): BSTree<T> { if (root === null) return null; if (root.right === null) return root; return getMaxBSTreeNode(root.right); } /** 获取前驱节点: 左子节点树的最大值 */ export function getPrevBSTreeNode<T>(root: BSTree<T>): BSTree<T> { if (root === null) return null; if (root.left === null) return null; return getMaxBSTreeNode(root.left); } /** 获取后驱节点: 右子节点树的最小值 */ export function getNextBSTressNode<T>(root: BSTree<T>): BSTree<T> { if (root === null) return null; if (root.right === null) return null; return getMinBSTreeNode(root.right); }删除节点这个方法也是所有方法中最复杂的，待删除节点可细分为以下情况叶子节点: 直接删除节点只有左子树或者右子树: 节点删除 将节点的左子树或者右子树移到删除节点的位置上节点既有左子树也有右子树: 找到节点的前驱/后继节点替换该节点 并删除前驱/后继节点(递归删除)/** 删除节点 **/ export function removeBSTreeNode<T>(root: BSTree<T>, val: T): BSTree<T> { if (root === null) return null; if (root.val === val) { if (root.left === null && root.right === null) { // 叶子节点 return null; } else if (root.left === null) { // 只存在右子树 return root.right; } else if (root.right === null) { // 只存在左子树 return root.left; } else { // 既存在左子树也存在右子树 这里采用寻找后继节点替换的方式 const nextNode = getNextBSTressNode(root)!; root.val = nextNode.val; // 将后继节点的值赋值给当前节点 root.right = removeBSTreeNode(root.right, nextNode.val); // 递归删除后继节点 } } else if (root.val > val) { root.left = removeBSTreeNode(root.left, val); } else { root.right = removeBSTreeNode(root.right, val); } return root; }总结二叉排序树是一个专门为查找而诞生的树，如果构建得当是可以将查找的效率降低到O(logn)的情况，但是如果构建成斜树的情况，其实和链表就是一样的了，查找复杂度变成O(n)。