红黑树学习笔记之红黑树的动机
一. 初认红黑树
节点具有颜色，红色或者黑色。
二. 持久性
无论是线性结构：向量，列表，栈，队列
半线性结构：树
非线性结构：图
每当经过一次动态的操作，使得其中的逻辑结构发生变化之后，它都会随即完全的转入新的状态，同时将此前的状态完全的遗忘掉。这类结构因此称作ephemeral data structure。而Persistent structure支持对历史版本的访问。
蛮力实现：每个版本独立保存；各版本入口自成一个搜索结构。
三. 关联性
大量共享，少量更新：每个版本的新增复杂度，仅为O(logn)
每一条红线都对应于一个共享。节点1既出现在前一个版本中，同时也出现在后一个版本中。
蓝色虚线指示相邻版本之间的更新量，也是不得不花费空间来进行存储的量。
4.重构
就树形结构的拓扑而言，相邻版本之间的差异不能超过O(1)。所谓的拓扑结构差异，来自调整过程中的旋转操作。从前一版本转入后一版本的过程中，所执行的旋转操作不得超过常数次。AVL的insert满足，而delete却不满足。
红黑树任何一次动态操作，引发的结构变化量都不导致超过O（1）。