数据结构-树

slug
data-struct-tree
date
May 15, 2023
tags
技术&产品
summary
type
Post
status
Published
Last edited time
May 18, 2023 05:54 AM

什么是二叉查找树(Binary Search Tree)

二叉查找树是一种有序的二叉树,每个节点最多只有两个子节点。对于每个节点,其左子树上所有节点的值均小于该节点的值,其右子树上所有节点的值均大于该节点的值。它具有以下特点:
  1. 左子树上所有节点的值均小于根节点的值;
  1. 右子树上所有节点的值均大于根节点的值;
  1. 左右子树也分别为二叉查找树。
二叉查找树支持插入、删除、查找等操作,时间复杂度为 O(log n)。它被广泛应用于数据库、编译器等领域。
二叉查找树的时间复杂度取决于树的高度,如果二叉查找树退化为一条链,时间复杂度就会退化为 O(n)。为了解决这个问题,出现了平衡二叉查找树,如 AVL 树和红黑树等。这些数据结构保证了树的高度不会太高,从而保证了操作的时间复杂度。

二叉查找树相关算法题目

  1. LeetCode 98. 验证二叉搜索树
  1. LeetCode 450. 删除二叉搜索树中的节点
  1. LeetCode 230. 二叉搜索树中第K小的元素
  1. LeetCode 235. 二叉搜索树的最近公共祖先
  1. LeetCode 108. 将有序数组转换为二叉搜索树
  1. LeetCode 109. 有序链表转换二叉搜索树
  1. LeetCode 538. 把二叉搜索树转换为累加树
  1. LeetCode 98. 验证二叉搜索树
 

什么是红黑树(Red-Black Tree)

红黑树是一种自平衡的二叉查找树,它保证了树的高度不会太高,从而保证了插入、删除、查找等操作的时间复杂度都为 O(log n)。红黑树与 AVL 树类似,但它对于插入和删除操作的旋转次数要少于 AVL 树,因此在插入和删除操作较多的情况下,红黑树的性能更优。红黑树的节点具有以下特点:
  1. 每个节点要么是红色,要么是黑色;
  1. 根节点是黑色的;
  1. 每个叶子节点都是黑色的空节点(NIL节点);
  1. 不能有相邻的两个红色节点;
  1. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
notion image

红黑树相关算法题目

  1. LeetCode 337. 打家劫舍 III
  1. LeetCode 98. 验证二叉搜索树
  1. LeetCode 235. 二叉搜索树的最近公共祖先
  1. LeetCode 450. 删除二叉搜索树中的节点
 

什么是堆(Heap)

堆是一种完全二叉树,它分为大根堆和小根堆。在大根堆中,每个节点的值都大于等于其子节点的值;在小根堆中,每个节点的值都小于等于其子节点的值。堆通常用来实现优先队列和排序算法。堆的插入和删除操作的时间复杂度为 O(log n),堆化的时间复杂度为 O(n)。

堆的应用

堆通常用来实现优先队列和排序算法。优先队列是一种特殊的队列,每个元素都有一个优先级。堆可以用来实现优先队列,时间复杂度为 O(log n)。排序算法中,堆排序的时间复杂度为 O(n log n)。

堆相关算法题目

  1. LeetCode 23. 合并K个升序链表
  1. LeetCode 295. 数据流的中位数
  1. LeetCode 378. 有序矩阵中第K小的元素
  1. LeetCode 347. 前 K 个高频元素
 

堆相关算法题目

  1. LeetCode 703. 数据流中的第K大元素
  1. LeetCode 215. 数组中的第K个最大元素
  1. LeetCode 347. 前 K 个高频元素
  1. LeetCode 295. 数据流的中位数
 

© JimYan 2023 - 2024