什么是红黑树-面试中常问的数据结构

2024-08-24 07:04
文章标签 面试 数据结构 黑树 中常

本文主要是介绍什么是红黑树-面试中常问的数据结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

你有没有想过,为什么你的 Java HashMap 能够如此高效地处理数百万个键值对?或者你的 Linux 系统是如何在眨眼间就能管理成千上万的进程的?这些看似神奇的性能背后,隐藏着一个优雅而强大的数据结构 - 红黑树。
稿定智能设计202408232340.png

目录

    • 什么是红黑树?
    • 红黑树的特性
    • 为什么需要红黑树?
    • 红黑树的结构
    • 红黑树的操作
      • 插入操作
      • 删除操作
    • 红黑树的平衡性分析
    • 红黑树的应用场景
    • 红黑树 vs AVL树
    • 实现一个简单的红黑树
    • 红黑树的性能分析
    • 红黑树的局限性
    • 总结与展望

在这篇文章中,我们将揭开红黑树的神秘面纱,探索它如何在保持高效性的同时,优雅地平衡自己。无论你是刚入门的编程新手,还是经验丰富的大数据开发者,这篇文章都将带你进入一个充满平衡与效率的数据结构世界。

什么是红黑树?

红黑树(Red-Black Tree)是一种自平衡的二叉搜索树。它在1972年由Rudolf Bayer发明,当时被称为"对称二叉B树"。后来,在1978年由Leo J. Guibas和Robert Sedgewick改进,才正式命名为"红黑树"。
image.png

红黑树的每个节点都带有颜色属性,要么是红色,要么是黑色。通过巧妙地利用这些颜色,红黑树保证没有一条路径会比其他路径长出两倍,这个特性确保了树是大致平衡的。

想象一下,你正在搭建一座大厦。红黑树就像是这座大厦的结构工程师,它不断地调整建筑的各个部分,确保整体结构的稳定性和平衡性。即使你不断地往大厦里添加或移除房间(插入或删除节点),红黑树也能快速地重新平衡整个结构,使其保持高效运作。

红黑树的特性

红黑树的神奇之处在于它的五个基本特性:

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点总是黑色的。
  3. 每个叶节点(NIL节点,空节点)是黑色的。
  4. 如果一个节点是红色的,则它的两个子节点都是黑色的。
  5. 对于每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。
    image.png

这些特性看似简单,却能保证从根到叶子的最长路径不会超过最短路径的两倍。这是红黑树保持平衡的关键。

让我们用一个比喻来理解这些特性:想象红黑树是一个由红黑两色积木搭建的塔。特性1就像是规定了积木只有两种颜色。特性2告诉我们塔底必须是黑色的,为整个结构提供稳定性。特性3和4确保了红色积木不会相邻,防止"色彩失衡"。最后,特性5就像是确保了塔的每一侧都有相同数量的黑色积木,保持整体平衡。

为什么需要红黑树?

在计算机科学中,我们经常需要在大量数据中快速查找、插入和删除元素。普通的二叉搜索树可以做到这一点,但在最坏情况下(例如,当输入是已排序的数据时),它可能退化成一个链表,导致操作的时间复杂度从O(log n)变为O(n)。
image.png

这就像是你在图书馆里找书。如果书架组织得很好(平衡的树),你可以快速定位到你想要的书。但如果所有的书都排成一列(退化的树),你就必须从头开始一本本查找,这显然效率很低。

红黑树通过其特殊的结构和平衡操作,保证了树的高度始终保持在O(log n),从而确保了查找、插入和删除操作的时间复杂度都是O(log n)。这意味着,即使在最坏的情况下,红黑树也能保持高效的性能。

红黑树的结构

红黑树的每个节点通常包含五个属性:颜色、键值、左子节点、右子节点和父节点。在许多编程语言中,我们可以这样定义一个红黑树节点:

public class RedBlackNode<T extends Comparable<T>> {public static final boolean RED = true;public static final boolean BLACK = false;public T key;public RedBlackNode<T> left;public RedBlackNode<T> right;public RedBlackNode<T> parent;public boolean color;public RedBlackNode(T key) {this.key = key;this.color = RED; // 新插入的节点默认为红色this.left = null;this.right = null;this.parent = null;}
}

这个结构看起来很简单,但它蕴含了红黑树强大功能的基础。每个节点都知道自己的颜色,保存了一个键值,并且与其父节点和子节点相连。这种结构允许我们在树中快速移动,执行各种操作。

想象一下,每个节点就像是一个带有颜色标记的盒子,里面装着一个值。这些盒子通过绳子(指针)连接在一起,形成一个复杂的网络。通过遵循这些连接,我们可以在整个结构中导航,找到我们需要的信息。

红黑树的操作

红黑树最基本的操作是插入和删除。这些操作的复杂之处在于,它们不仅要保持二叉搜索树的性质,还要维护红黑树的五个基本特性。让我们深入了解这两个关键操作。

插入操作

image.png

插入操作的基本步骤如下:

  1. 像在普通的二叉搜索树中一样插入节点。
  2. 将新节点着色为红色。
  3. 通过重新着色和旋转来修复红黑树的性质。

让我们通过一个具体的例子来说明这个过程。假设我们要构建一个存储整数的红黑树,并依次插入以下值:10, 20, 30, 15, 25。

初始状态:空树

插入10:

   10(B)

10作为根节点,必须是黑色的。

插入20:

   10(B)\20(R)

20作为新插入的节点,initially被着色为红色。

插入30:

     20(B)/   \10(R)  30(R)

插入30后,我们需要重新着色来保持红黑树的性质。20变为黑色,10和30变为红色。

插入15:

     20(B)/   \10(B)  30(B)\15(R)

15作为10的右子节点被插入,颜色为红色。不需要further调整。

插入25:

     20(B)/   \10(B)  30(B)\    /15(R) 25(R)

25作为30的左子节点被插入,颜色为红色。同样不需要further调整。

这个例子展示了红黑树如何通过插入操作逐步构建起来。在每一步插入后,我们都需要检查并可能调整树的结构,以维护红黑树的性质。

删除操作

删除操作更为复杂,因为它可能会破坏树的平衡性和颜色规则。基本步骤如下:

  1. 像在普通的二叉搜索树中一样删除节点。
  2. 如果删除的节点是黑色的,且不是叶子节点,我们需要通过一系列的重新着色和旋转来恢复红黑树的性质。

让我们以前面构建的红黑树为例,尝试删除节点15:

初始状态:

     20(B)/   \10(B)  30(B)\    /15(R) 25(R)

删除15:

     20(B)/   \10(B)  30(B)/25(R)

在这个例子中,删除15后不需要进一步的调整,因为被删除的是一个红色节点,不会影响黑色节点的平衡。

但是,如果我们尝试删除一个黑色节点,情况就会变得复杂得多。例如,如果我们要删除10:

     20(B)/   \10(B)  30(B)/25(R)

删除10后:

     20(B)\30(B)/25(R)

这种情况下,我们需要进行一系列的重新着色和旋转操作来恢复红黑树的性质。具体的操作取决于被删除节点的兄弟节点的颜色和它的子节点的颜色。

这些复杂的操作确保了无论我们如何插入或删除节点,红黑树都能保持其平衡性和高效性。这就是为什么红黑树在需要频繁插入和删除操作的场景中表现出色的原因。

红黑树的平衡性分析

红黑树的核心优势在于其良好的平衡性。但是,什么是"平衡"?为什么平衡如此重要?让我们深入探讨这个问题。

在树结构中,平衡指的是树的所有叶节点到根节点的路径长度相近。一棵完全平衡的树,其所有叶节点到根节点的路径长度都相同。然而,维护一棵完全平衡的树(如AVL树)在插入和删除操作时代价很高。

红黑树采取了一种折中的方案:它不追求绝对的平衡,而是保证最长路径不超过最短路径的两倍。这种"近似平衡"足以保证O(log n)的操作时间复杂度,同时又能保持插入和删除操作的高效性。

让我们通过一个例子来理解这一点。考虑以下红黑树:

       30(B)/     \20(B)    40(B)/  \     /  \
10(B) 25(R) 35(R) 50(B)

在这棵树中:

  • 最短路径(从根到任何空叶节点)包含2个黑节点(30, 20/40)
  • 最长路径包含3个节点(30, 20, 25或30, 40, 35),其中2个是黑节点

我们可以看到,最长路径(3)确实不超过最短路径(2)的两倍。这就是红黑树平衡性的体现。

为什么这种平衡性如此重要?想象一下,如果树变得不平衡,某些路径可能会变得非常长。在最坏的情况下,树可能退化成一个链表。这将导致搜索、插入和删除操作的时间复杂度从O(log n)退化到O(n),这在处理大量数据时是不可接受的。

红黑树通过其特殊的结构和平衡规则,保证了这种情况永远不会发生。即使在最坏的情况下,红黑树的高度也不会超过2log(n+1),其中n是树中节点的数量。这意味着,无论你如何插入或删除节点,所有操作的时间复杂度都保持在O(log n)。

这种平衡性是通过红黑树的五个平衡性是通过红黑树的五个基本性质来保证的。让我们再次回顾这些性质,并深入理解它们如何共同作用来维护树的平衡:

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点总是黑色的。
  3. 每个叶节点(NIL节点,空节点)是黑色的。
  4. 如果一个节点是红色的,则它的两个子节点都是黑色的。
  5. 对于每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。

这些性质看似简单,但它们的组合效果是强大的:

  • 性质4确保了红色节点不会连续出现。这就限制了树的"倾斜"程度。
  • 性质5是关键。它确保了从根到任何叶子的路径上黑色节点的数量相同。这直接限制了树的高度。

因为最长路径(红黑相间)的长度不会超过最短路径(全黑)长度的两倍,所以树总是大致平衡的。

红黑树的应用场景

image.png

理解了红黑树的结构和特性后,让我们来看看它在实际中的应用。红黑树的平衡性和效率使它在很多场景下成为理想的选择:

  1. Java中的TreeMap和TreeSet:
    Java的Collections框架中,TreeMap和TreeSet的内部实现就是红黑树。这保证了这些集合类的containsKey(), get(), put(), remove()等操作的时间复杂度为O(log n)。

    TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "One");
map.put(2, "Two");
map.put(3, "Three");System.out.println(map.get(2)); // 输出: Two

  2. Linux内核中的完全公平调度器(CFS):
    Linux的CFS使用红黑树来有效地管理进程的调度。每个可运行的进程都作为一个节点插入到树中,键值是进程的虚拟运行时间。这样,CFS可以快速找到下一个要运行的进程(树的最左节点)。

  3. 数据库索引:
    很多数据库系统使用B树或B+树作为索引结构,这些树和红黑树有着密切的关系。红黑树可以看作是2-3-4树的一种等价表示。

  4. C++ STL中的set和map:
    在许多C++标准库的实现中,set和map类型是用红黑树实现的。这保证了元素始终有序,并且插入、删除和查找操作的时间复杂度都是O(log n)。

    #include <set>
#include <iostream>int main() {std::set<int> s;s.insert(1);s.insert(2);s.insert(3);if (s.find(2) != s.end()) {std::cout << "Found 2" << std::endl;}return 0;
}

  5. 网络应用中的IP路由表:
    在网络路由中,需要快速查找最长前缀匹配。红黑树可以有效地支持这种操作。

  6. 文件系统:
    某些文件系统使用红黑树来管理文件和目录结构,以支持快速的查找和修改操作。

这些应用场景展示了红黑树在实际系统中的重要性。它不仅是一个理论上有趣的数据结构,更是解决实际问题的有力工具。

红黑树 vs AVL树

image.png

在讨论自平衡二叉搜索树时,我们不能不提到AVL树。AVL树是另一种自平衡二叉搜索树,它和红黑树有许多相似之处,但也有一些关键的区别。让我们来比较这两种树结构:

  1. 平衡条件:

    • AVL树:任何节点的两个子树的高度最多差1。这是一个很严格的平衡条件。
    • 红黑树:从根到叶子的最长路径不超过最短路径的两倍。这个条件相对宽松。

  2. 树高:

    • AVL树:严格平衡,树高约为1.44log n。
    • 红黑树:近似平衡,树高不超过2log(n+1)。

  3. 旋转操作:

    • AVL树:插入可能需要多次旋转,删除最多需要O(log n)次旋转。
    • 红黑树:插入最多需要2次旋转,删除最多需要3次旋转。

  4. 适用场景:

    • AVL树:适合查找密集型任务,因为它的严格平衡导致更快的查找速度。
    • 红黑树:适合写入密集型任务,因为它的插入和删除操作通常需要更少的旋转。

让我们通过一个具体的例子来比较这两种树结构。假设我们要依次插入以下数字:10, 20, 30, 40, 50。

AVL树的结果:

    30/  \20    40
/        \
10        50

红黑树的结果(B代表黑色,R代表红色):

      30(B)/     \20(B)    40(B)/          \
10(R)        50(R)

我们可以看到,AVL树在插入过程中进行了多次旋转,最终形成了一个更为平衡的结构。而红黑树虽然不如AVL树平衡,但仍然保持了良好的平衡性,同时可能进行了更少的旋转操作。

在实际应用中,如果你的场景以查询操作为主,而插入和删除操作相对较少,那么AVL树可能是更好的选择。但如果你的应用需要频繁的插入和删除操作,那么红黑树可能更为合适。这就是为什么在很多标准库的实现中(如C++ STL),选择使用红黑树而不是AVL树的原因。

实现一个简单的红黑树

image.png

理解了红黑树的原理后,让我们尝试实现一个简单的红黑树。我们将使用Java来实现,但这些概念可以轻易地转换到其他编程语言。

首先,我们定义节点结构:

public class RedBlackNode<T extends Comparable<T>> {T data;RedBlackNode<T> parent;RedBlackNode<T> left;RedBlackNode<T> right;boolean color; // true for red, false for blackpublic RedBlackNode(T data) {this.data = data;this.color = true; // new nodes are always redthis.left = null;this.right = null;this.parent = null;}
}

然后,我们定义红黑树类:

public class RedBlackTree<T extends Comparable<T>> {private RedBlackNode<T> root;private RedBlackNode<T> NIL;public RedBlackTree() {NIL = new RedBlackNode<>(null);NIL.color = false; // NIL nodes are always blackroot = NIL;}// 插入操作public void insert(T data) {RedBlackNode<T> node = new RedBlackNode<>(data);RedBlackNode<T> y = NIL;RedBlackNode<T> x = this.root;while (x != NIL) {y = x;if (node.data.compareTo(x.data) < 0) {x = x.left;} else {x = x.right;}}node.parent = y;if (y == NIL) {root = node;} else if (node.data.compareTo(y.data) < 0) {y.left = node;} else {y.right = node;}node.left = NIL;node.right = NIL;node.color = true; // redinsertFixup(node);}// 插入后的修复操作private void insertFixup(RedBlackNode<T> k) {RedBlackNode<T> u;while (k.parent.color == true) {if (k.parent == k.parent.parent.right) {u = k.parent.parent.left;if (u.color == true) {u.color = false;k.parent.color = false;k.parent.parent.color = true;k = k.parent.parent;} else {if (k == k.parent.left) {k = k.parent;rightRotate(k);}k.parent.color = false;k.parent.parent.color = true;leftRotate(k.parent.parent);}} else {u = k.parent.parent.right;if (u.color == true) {u.color = false;k.parent.color = false;k.parent.parent.color = true;k = k.parent.parent;} else {if (k == k.parent.right) {k = k.parent;leftRotate(k);}k.parent.color = false;k.parent.parent.color = true;rightRotate(k.parent.parent);}}if (k == root) {break;}}root.color = false;}// 左旋操作private void leftRotate(RedBlackNode<T> x) {RedBlackNode<T> y = x.right;x.right = y.left;if (y.left != NIL) {y.left.parent = x;}y.parent = x.parent;if (x.parent == NIL) {this.root = y;} else if (x == x.parent.left) {x.parent.left = y;} else {x.parent.right = y;}y.left = x;x.parent = y;}// 右旋操作private void rightRotate(RedBlackNode<T> y) {RedBlackNode<T> x = y.left;y.left = x.right;if (x.right != NIL) {x.right.parent = y;}x.parent = y.parent;if (y.parent == NIL) {this.root = x;} else if (y == y.parent.right) {y.parent.right = x;} else {y.parent.left = x;}x.right = y;y.parent = x;}
}

这个实现包含了红黑树的基本结构和插入操作。插入操作首先像普通二叉搜索树一样插入节点,然后通过insertFixup方法来修复可能被破坏的红黑树性质。

让我们来看一个使用这个红黑树的例子:

public class Main {public static void main(String[] args) {RedBlackTree<Integer> rbt = new RedBlackTree<>();rbt.insert(10);rbt.insert(20);rbt.insert(30);rbt.insert(15);rbt.insert(25);// 这里我们可以添加一些打印或遍历操作来查看树的结构}
}

这个简单的实现展示了红黑树的核心概念,包括节点的颜色属性、插入操作、以及用于维护树平衡的旋转操作。然而,这只是一个基础实现,一个完整的红黑树还需要包括删除操作、查找操作,以及各种遍历方法。

红黑树的性能分析

image.png

红黑树的性能是它成为许多系统选择的关键原因。让我们深入分析一下红黑树各种操作的时间复杂度:

  1. 搜索😮(log n)
    在最坏情况下,搜索操作需要遍历从根到叶的最长路径。由于红黑树的高度被限制在O(log n),所以搜索操作的时间复杂度是O(log n)。

  2. 插入😮(log n)
    插入操作包括两个步骤:

    • 找到插入位置:这需要O(log n)时间。
    • 调整树以维持红黑性质:这需要最多3次旋转操作,每次旋转是O(1)的。
      因此,总的时间复杂度仍然是O(log n)。

  3. 删除😮(log n)
    删除操作稍微复杂一些,但其时间复杂度仍然是O(log n):

    • 找到要删除的节点:O(log n)
    • 删除节点并调整树:最多需要O(log n)次颜色调整和3次旋转。

  4. 空间复杂度😮(n)
    红黑树需要为每个元素存储颜色信息,但这只增加了一个常数因子,不影响渐进空间复杂度。

让我们通过一个具体的例子来理让我们通过一个具体的例子来理解红黑树的性能优势。假设我们有一个包含100万个元素的红黑树：

  • 搜索操作：在最坏情况下，我们需要遍历树的高度。log_2(1,000,000) ≈ 20，所以我们最多需要比较20次就能找到任何元素。
  • 插入操作：同样，我们需要大约20次比较来找到正确的插入位置，然后最多3次旋转来维持树的平衡。
  • 删除操作：我们需要约20次比较来找到要删除的节点，然后最多3次旋转和O(log n)次颜色调整来维持树的平衡。

相比之下，如果我们使用一个普通的二叉搜索树，在最坏情况下（树退化为链表），这些操作可能需要100万次比较！

这就是为什么红黑树在处理大量数据时如此高效。即使在最坏的情况下，它也能保证对数时间的性能，这使得它非常适合需要频繁插入、删除和搜索操作的应用场景。

红黑树的局限性

image.png

尽管红黑树在许多场景下表现出色，但它也有一些局限性：

  1. 实现复杂性：红黑树的实现比简单的二叉搜索树要复杂得多。插入和删除操作需要考虑多种情况，并进行适当的旋转和重新着色。

  2. 额外的存储开销：每个节点需要存储颜色信息，这增加了内存使用。

  3. 不适合小数据集：对于小型数据集，红黑树的优势不明显，简单的数据结构（如数组或链表）可能更合适。

  4. 不保证绝对平衡：虽然红黑树保证了近似平衡，但它不如AVL树平衡。在某些特定的只读场景中，AVL树可能表现更好。

  5. 范围查询效率不如B树：对于需要频繁进行范围查询的场景（如数据库索引），B树或B+树可能是更好的选择。

总结与展望

红黑树是一种优雅而强大的数据结构，它巧妙地平衡了效率和复杂性。通过保持近似平衡，红黑树在保证最坏情况性能的同时，也提供了相对简单的插入和删除操作。

我们已经深入探讨了红黑树的以下方面：

  • 基本结构和性质
  • 插入和删除操作的原理
  • 平衡性分析
  • 与AVL树的比较
  • 实际应用场景
  • 简单的实现示例
  • 性能分析
  • 局限性

理解红黑树不仅能帮助我们更好地使用依赖于它的数据结构和系统，还能启发我们思考如何在其他场景中平衡不同的需求。

展望未来，随着数据规模的不断增长和新的应用场景的出现，我们可能会看到红黑树的新变种或改进。例如：

  1. 并发红黑树：为了更好地适应多核处理器，研究人员正在探索能够支持并发操作的红黑树变体。

  2. 缓存友好的红黑树：随着内存访问成为瓶颈，有人提出了更加缓存友好的红黑树实现，试图减少内存访问次数。

  3. 自适应红黑树：根据实际使用情况动态调整平衡策略的红黑树，可能在某些场景下表现更好。

  4. 持久化红黑树：为了支持快速的故障恢复，研究人员正在探索能够高效持久化到非易失性内存的红黑树结构。

无论未来如何发展，红黑树作为一个经典的数据结构，其核心思想 —— 在多个相互矛盾的目标之间寻求平衡 —— 将继续启发我们设计新的算法和数据结构。

作为一名大数据开发者，深入理解红黑树这样的基础数据结构将使你在设计和优化大规模数据处理系统时具有独特的洞察力。无论是选择适当的数据结构，还是调优现有系统的性能，这些知识都将是你的宝贵资产。

最后，我想鼓励所有读者：不要止步于此。尝试实现你自己的红黑树，在实际项目中使用它，或者深入研究它的变体。只有通过实践，我们才能真正掌握这个优雅而强大的数据结构。

记住，在计算机科学中，平衡往往是智慧的体现。红黑树正是这种智慧的完美诠释。

这篇关于什么是红黑树-面试中常问的数据结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1101783。

相关文章

字节面试 | 如何测试RocketMQ、RocketMQ？

字节面试 | 如何测试RocketMQ、RocketMQ？

字节面试：RocketMQ是怎么测试的呢？ 答： 首先保证消息的消费正确、设计逆向用例，在验证消息内容为空等情况时的消费正确性； 推送大批量MQ，通过Admin控制台查看MQ消费的情况，是否出现消费假死、TPS是否正常等等问题。（上述都是临场发挥，但是RocketMQ真正的测试点，还真的需要探讨） 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说，就是一个分
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
java面试常见问题之Hibernate总结

java面试常见问题之Hibernate总结

1  Hibernate的检索方式 Ø  导航对象图检索（根据已经加载的对象，导航到其他对象。） Ø  OID检索（按照对象的OID来检索对象。） Ø  HQL检索（使用面向对象的HQL查询语言。） Ø  QBC检索（使用QBC(Qurey By Criteria)API来检索对象。 QBC/QBE离线/在线） Ø  本地SQL检索（使用本地数据库的SQL查询语句。） 包括Hibern
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
贝壳面试：什么是回表？什么是索引下推？

贝壳面试：什么是回表？什么是索引下推？

尼恩说在前面 在40岁老架构师 尼恩的读者交流群(50+)中，最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格，遇到很多很重要的面试题： 1.谈谈你对MySQL 索引下推 的认识？ 2.在MySQL中，索引下推 是如何实现的？请简述其工作原理。 3、说说什么是 回表，什么是 索引下推 ？ 最近有小伙伴在面试 贝壳、soul，又遇到了相关的
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...
Python 内置的一些数据结构

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据，每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明： 1. 列表 (List) 列表是一种可变的有序集合，可以存放任意类型的数据。列表中的元素可以通过索
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2