红黑树
https://blog.csdn.net/adaptiver/article/details/8679106
https://insidelinuxdev.net/article/a056q3.html
1、简介
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
2、关联数组
“关联数组”是一种具有特殊索引方式的数组。不仅可以通过整数来索引它，还可以使用字符串或者其他类型的值（除了NULL）来索引它。
关联数组和数组类似，由以名称作为键的字段和方法组成。 它包含标量数据，可用索引值来单独选择这些数据，和数组不同的是， 关联数组的索引值不是非负的整数而是任意的标量。这些标量称为Keys，可以在以后用于检索数组中的数值。 关联数组的元素没有特定的顺序，你可以把它们想象为一组卡片。每张卡片上半部分是索引而下半部分是数值。 JavaScript的对象本质就是一个关联数组。
std::map作为一个容器存在一个典型应用就是作为关联数组来作用。在诸如Java等等语言中，关联数组广泛存在。std::map是一个容器，在它的概念框架中存在两个词：键和值，std::map把一个键与一个值相对，它相当于一个字典，把一个索引和一人内容对应起来。一般情况下，std::map用一个平衡二叉树来实现的，所以它的大部分操作都可以log(n)的时间里完成。