数据结构-树
date
May 15, 2023
tags
技术&产品
type
Post
status
Published
Last edited time
May 18, 2023 05:54 AM
什么是二叉查找树（Binary Search Tree）
二叉查找树是一种有序的二叉树，每个节点最多只有两个子节点。对于每个节点，其左子树上所有节点的值均小于该节点的值，其右子树上所有节点的值均大于该节点的值。它具有以下特点：
- 左子树上所有节点的值均小于根节点的值；
- 右子树上所有节点的值均大于根节点的值；
- 左右子树也分别为二叉查找树。
二叉查找树支持插入、删除、查找等操作，时间复杂度为 O(log n)。它被广泛应用于数据库、编译器等领域。
二叉查找树的时间复杂度取决于树的高度，如果二叉查找树退化为一条链，时间复杂度就会退化为 O(n)。为了解决这个问题，出现了平衡二叉查找树，如 AVL 树和红黑树等。这些数据结构保证了树的高度不会太高，从而保证了操作的时间复杂度。
二叉查找树相关算法题目
什么是红黑树（Red-Black Tree）
红黑树是一种自平衡的二叉查找树，它保证了树的高度不会太高，从而保证了插入、删除、查找等操作的时间复杂度都为 O(log n)。红黑树与 AVL 树类似，但它对于插入和删除操作的旋转次数要少于 AVL 树，因此在插入和删除操作较多的情况下，红黑树的性能更优。红黑树的节点具有以下特点：
- 每个节点要么是红色，要么是黑色；
- 根节点是黑色的；
- 每个叶子节点都是黑色的空节点（NIL节点）；
- 不能有相邻的两个红色节点；
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树相关算法题目
什么是堆（Heap）
堆是一种完全二叉树，它分为大根堆和小根堆。在大根堆中，每个节点的值都大于等于其子节点的值；在小根堆中，每个节点的值都小于等于其子节点的值。堆通常用来实现优先队列和排序算法。堆的插入和删除操作的时间复杂度为 O(log n)，堆化的时间复杂度为 O(n)。
堆的应用
堆通常用来实现优先队列和排序算法。优先队列是一种特殊的队列，每个元素都有一个优先级。堆可以用来实现优先队列，时间复杂度为 O(log n)。排序算法中，堆排序的时间复杂度为 O(n log n)。