在讲容器之前先讲一下集合和Java的集合类
集合：一个或多个确定元素构成的整体（确定性、互异性、无序性）
Java集合类：集合类里的元素都是对象的引用
那么问题来了：
Q1:什么是对象的引用？
new Demo()产生新对象，存储在堆内存中，demo是对象引用。存储在栈内存中，存储的内容就是new Demo()对象的堆的内存地址
Q2:我们存储的是基本数据类型，为什么在集合类里会变成对象？
系统自动包装
那么集合类存储的都是对象的引用，存的都是对象对应的内存地址。所以依旧遵循集合的互异性
插一个题外话：
Q：为什么equals和==有时候得到的效果是不同的？
A：==在比较时会先查看两边的数据，如果都是int这种基本数据类型，就会生成一个if_icmpne指令，用于比较整型数值是否相等。如果两边是对象的话，就会生成一个if_acmpne，用于比较它们指向的地址是否相等。
因为第一个都是指向堆中的“abc”这个字符串，地址是一样的，所以==返回true
Q：数组内的值改变了，它的地址会改变吗？
A：不会改变，因为数组一开始的内存就已经被分配好了，值改变了也不会改变相应的地址
c++的STL容器有哪些？
vector（封装数组）/list（封装链表）/deque map/set（两者都封装了二叉树）
vector：表示一段连续的内存地址，相当于数据结构的线性表的顺式表现
list：STL实现的双向链表，允许快速插入和删除，查找较慢
相当于数据结构的线性表的链式表现，含有两个指针（一个指示直接后继、一个指示直接前驱）
deque：允许首部插入，其他的都和vector一样
map：存在key/value
引用自STL
set与map，相似，但是set键和值相等
那么，再来思考一个问题，迭代器是什么？
迭代器提供了对集合（容器）元素的操作能力，比如访问和遍历。迭代器模仿了C++的指针，可以有++运算，*，以及->运算符来访问容器里的元素。
Q：为什么我们要用迭代器？
A：编程中我们往往碰到各种各样的容器，不一样的容器它们的底层代码实现是不同的，那就意味着，遍历它们需要不同的方式。这样一来非常不利于代码重用，所以迭代器就出现了，我们将遍历容器的操作都封装在迭代器里，那么我们就不需要考虑这个容器需要用哪一种遍历方式
Q：那么现在思考一下，什么是迭代器模式呢？
A：我们访问我们需要访问的元素而不会暴露我们的底层实现
就像听歌一样，我们按下下一首，就跳转到下一首歌曲了。而这个界面就相当于我们的迭代器，里面的歌曲的遍历方式都被封装好了，我们只需要按按钮，就会自动访问到我们想要听的那首歌。
迭代器在C++里的使用
由上面的map容器，我们来思考一下什么是红黑树？
在理解红黑树之前，先要思考两个概念：什么是二叉排序树（BST），什么是平衡二叉树（AVL）
什么是二叉排序树：
1.若左子树不为空，那么左子树上的所有点都小于根节点
2.若右子树不为空，那么右子树上的所有点都大于根节点
3.左右子树也分别为二叉排序树
4.每个节点都是互不相同的
二叉排序树的算法是怎么实现的？
1.查找
2.插入
3.删除
如果要删除的节点只有右子树/左子树，只需要让它们的父节点指向它们的右子树/左子树
如果要删除的节点左右子树都有，那么此时需要找到要删除的节点的右子树的最左节点，将它与要删除的节点的值替换，然后删除
什么是平衡二叉树？
在二叉搜索树的基础上增加平衡条件：每个节点左右子树的高度差的绝对值小于等于1。
平衡二叉树是基于二分法策略来提高检索速度
为什么有平衡二叉树的概念？
当我们将1-9按照正序或者逆序一个个插入树结构中，我们就会发现树的结构已经变成了单向右子树/左子树，若继续往下插入数字，那么子树也越来越长。这样树和单链表就没什么不同，此时的复杂度变为O(n)。那么为了避免出现这样的情况，我们引入了平衡二叉树。
平衡二叉树有很多种实现方法，这里我们只考虑AVL和红黑树
AVL：（以下代码实现参考博客）
平衡二叉树的查询性能与什么有关？
树的高度
什么是红黑树？
红黑树是近似平衡的二叉查找树，它含有以下特性：
1.每个节点要么是红色，要么是黑色。
2.根节点必须是黑色
3.红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
4.对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。
5.每个叶子节点都为黑色
如何理解左旋？
X的右子树逆时针旋转，使得X变为Y的左子树。即被旋转的节点将变为左节点
如何理解右旋？
X的左子树向顺时针方向旋转，X的左子树变为X的父节点。即被旋转的节点将变为右节点
如何理解红黑树的插入？
1.进行查找，查找到合适位置，创建新节点插入
2.因为插入可能会使当前树不满足红黑树的特点，于是需要对红黑树进行调整
3.调整的方法有：改变某些节点的颜色、对某些节点进行旋转
侵删
在了解红黑树的删除之前，我们需要清楚一个概念：
如何查找节点的直接后继？
1.节点右孩子不为空，则右子树的最小的元素为直接后继
2.节点右孩子为空，则直接后继为第一个向左走的祖先
侵删
如何理解红黑树的插入？
1.进行查找，查找到合适位置，删除对应节点
2.删除节点对应两种情况，
a.删除点左右子树都为空（解决：直接删除）或只有一棵子树为非空（解决：让该子树替代删除的节点）
b.删除点左右子树都不为空（解决：删除节点的直接后继代替节点）
3.因为删除可能会使当前树不满足红黑树的特点，于是需要对红黑树进行调整
4.调整的方法有：改变某些节点的颜色、对某些节点进行旋转
网友评论