本章主要介绍符号表，以及三种经典数据结构来实现符号表：
- 二叉查找树
- 红黑树
- 散列表
符号表
符号表是一种抽象的数据结构，定义如下：
INFO
符号表是一种存储键值对的数据结构，支持两种操作：插入（put），即将一组新的键值对存入表中；查找（get），即根据给定的键得到相应的值。
符号表的简单API定义如下： 
有序符号表
保持符号表的键的有序性可以实现更多使用的操作。例如，假设键是时间，你可能会对最早的或是最晚的键或是给定时间段内的所有键等感兴趣。 
平衡查找树
《算法4》介绍了2-3树和红黑树，其实还有平衡二叉树AVL，和2-3树一样，也是通过调平操作来维持树的平衡，只是AVL只有2-节点。
2-3 查找树
二叉树在最坏情况下的性能仍然很糟糕（元素按顺序插入），2-3查找树能保证任何情况下运行时间都是对数级别的。
标准二叉查找树中的结点称为2-结点（含有一个键和两条链接） 2-3 查找树可以由2-节点或3-节点组成**。**
3- 节点含有两个键和三条链接，左链接指向的子树中的键都小于该节点，中链接指向的2-3树中的键都位于该结点的两个键之间；右链接指向的2-3树中的键都大于该结点。
2-3查找树实现的关键在于插入操作，将插入操作看成两步：第一步是查找操作，未命中的查找结束与某个节点；第二步是向这个节点做插入操作。插入操作根据不同的情况可以分为：
- 向2-节点中插入新键
- 向一个3-节点中插入新键，根据父节点的不同可以分为：
- 向一个没有父节点的3-节点的树种插入新键
- 向一个父节点为2-节点的树中插入新键
- 向一个父节点为3-节点的树中插入新键
插入操作需要保证插入新节点的同时，不破坏二叉查找树的结构和性质。
当未命中的节点结束于2-节点时候，这时我们把它变为3-节点即可： 
当未命中的节点结束与一个3-节点时，一个基本思想是先把它变为4-节点，再进行类似向上冒泡的过程，把4-节点分解为两个2-节点，将中键移动至父节点。
INFO
👉 观察上述几种插入操作，我们可以发现标准二叉查找树的插入操作是由上向下生长的，而2-3树的生长是**”从下向上“**的。
理解为从下向上分裂的过程。由4-节点向上生长。
INFO
**命题F。**在一棵大小为N的2-3树中，查找和插入操作访问的结点必然不超过lgN个。 **证明。**一棵含有N个结点的2-3树的高度在[log3N]=[（lgN）/（lg3）]（如果树中全是3-结点）和[lgN]（如果树中全是2-结点）之间
红黑二叉查找树
注：算法4中的红黑二叉查找树基于2-3树的一种特殊实现：左倾红黑树。这种限定能够很大的减少红黑树调整过程中的复杂性。
为什么要引入红黑树呢？因为直接实现2-3树所需要考虑的边缘CASE较多，而红黑树是一种更高层次的抽象，将2-3树抽象为标准2-查找树，从而可以结合2-查找二叉树中高效的查找算法和2-3树中高效的平衡插入算法。
红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。 红黑树中的链接分为两种类型：**红链接**和**黑链接**。其中**黑链接**就是2-3树中的普通链接。**红链接**将两个2-结点连接起来构成一个3-结点，
确切地说，红黑树将3-结点表示为由一条左斜的红色链接（两个2-结点其中之一是另一个的左子结点）相连的两个2-结点。
红黑树的定义： ❏红链接均为左链接； ❏没有任何一个结点同时和两条红链接相连； ❏该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
红黑树的实现需要维持以上的性质，通过左旋、右旋、颜色翻转这三种简单的操作，来保证插入操作后红黑树的性质和结构不变，保持和2-3树的一一对应关系。
旋转操作是二叉树调平的精髓。通过旋转，可以重新调整树的节点，来保持或恢复红黑树的性质。（想象旋转操作就像是调平天平的两端。
INFO
🤔 左旋、右旋、颜色翻转这三种操作分别对应2-3树的插入操作中那些步骤呢？
左旋右旋颜色翻转：对应与2-3树插入操作中临时4-节点的“分裂”操作：把4-节点分解为两个2-节点，将中键移动至父节点。
❓遗留问题：关于deletemin()和delete()方法还没有理解。
总结：
- 所谓平衡查找树，是为了解决二叉查找树在最坏情况下的性能问题（可能成为链表结构），通过一系列的调平操作来维护树的高度。
- 2-3树可以存储更多的节点，减少树的高度。但维护不同的节点也会带来更大的复杂度
- 红黑树是一种对2-3树的更高层次的抽象，同时保持二叉树的结构和API的易用性。