在学习红黑树之前，我们首先需要知道它到底解决了什么问题。4/ \2 6/ \ / \1 3 5 7log₂NO(logN)但是普通二叉搜索树并不会主动维护自己的结构。12345O(N)O(N)所以我们需要一种能够自动控制高度的二叉搜索树。AVL 树是一种解决方法，而红黑树则是另一种非常经典的解决方案。红黑树并不像 AVL 树那样严格要求左右子树高度差不超过 1，而是通过一些颜色规则间接约束树的高度

红黑树为什么能够保持近似平衡？插入以后为什么需要变色和旋转？这一篇正式进入代码实现。1. 红黑树结点2. 左旋与右旋3. BST 插入4. 红黑树插入修复5. Find 查找6. 红黑树合法性验证红黑树的代码虽然看起来比较长，但真正复杂的部分其实只有插入修复。第一阶段：BST 插入第二阶段：新结点染红第三阶段：如果父结点为红，修复红红冲突→ 变色→ 向上继续→ 判断 LL / RR / LR /

左子树中的关键字小于根右子树中的关键字大于根左右子树仍然是二叉搜索树借助这个规则，我们可以根据关键字大小决定向左还是向右查找。但是，普通二叉搜索树有一个明显的问题：它只规定了关键字之间的大小关系，却没有限制树的形状。查找7O(log N)O(N)AVL 树就是为了解决这个问题而出现的。普通二叉搜索树↓树高决定操作效率↓限制左右子树高度差↓引入平衡因子↓按照 BST 规则插入↓沿祖先路径更新平衡因子

按照 BST 规则插入↓沿祖先路径更新平衡因子↓平衡因子为 0：停止平衡因子为 ±1：继续平衡因子为 ±2：旋转真正实现 AVL 树时，难点主要集中在旋转。二叉搜索树的大小关系左孩子指针右孩子指针父指针整棵树的根指针局部子树与上一层的连接结点的平衡因子右单旋左单旋左右双旋右左双旋最后给出一套可以直接在 Linux 环境中编译运行的完整 C++ 实现。假设失衡结点为parent说明 parent 左

在学习普通二叉树时，我们主要关注的是树的结构，以及前序、中序、后序、层序等遍历方式。但普通二叉树有一个问题：结点之间没有统一的大小关系。假设现在要在一棵普通二叉树中查找数字13，除了把整棵树遍历一遍，我们通常没有更好的办法。因为站在某个结点上时，并不知道目标应该在左子树还是右子树。较小的数据放在左边较大的数据放在右边正是这条看起来很简单的规则，让树具备了定向查找、插入和删除的能力。这时树的方向会与

int main()students.insert({1003, "张三"});students.insert({1001, "李四"});students.insert({1002, "王五"});return 0;

虽然ptr的类型是Base*编译器如何知道指针实际指向哪种对象？静态绑定和动态绑定有什么区别？什么是虚函数表和虚函数表指针？派生类重写虚函数后，虚表发生了什么变化？为什么含有虚函数的对象可能会变大？为什么构造和析构期间不会调用更派生类版本？如何保存一组不同类型的多态对象？应该在什么时候使用？虚函数会带来多大性能开销？本文主要从底层原理和实际工程使用两个角度，继续讲解 C++ 多态。对象保存虚表指针

继承解决了类之间的代码复用问题，但仅仅有继承，还不能让程序根据对象的实际类型自动执行不同的行为。普通人：全价买票学生：优惠买票军人：优先买票如果程序通过大量if-elsecout << "全价买票" << endl;cout << "优惠买票" << endl;cout << "优先买票" << endl;多态提供了一种更自然的方式：调用者只面向统一的基类接口，具体执行哪个版本，由对象的实际类型决

继承是 C++ 面向对象部分非常重要的一块内容。在学习继承之前，我们已经接触过函数复用、模板复用和 STL。它们解决的都是“相同代码不要重复写”的问题，而继承解决的是类层面的复用。例如，学生和老师都具有姓名、年龄、电话和地址，也都需要进行身份认证。如果分别在Student和Teacher中定义这些成员，不但代码重复，后续修改起来也比较麻烦。继承允许我们把公共部分抽取到一个基类中，再让不同的派生类在

谁在访问文件？他可以对文件做什么？Linux 是一个多用户系统。普通用户的程序Web 服务数据库服务定时任务系统管理工具如果它们都可以不受限制地读取、修改和删除所有文件，系统几乎无法正常管理。文件类型文件拥有者文件所属组拥有者权限所属组权限其他用户权限怎样阅读ls -lLinux 常见文件类型rwx的含义文件权限与目录权限的区别字符权限和八进制权限chmod修改权限chown修改拥有者chgrp修