Ch5 关联式容器

关联式容器，每个元素都有一个键值（key）和一个实值（value）。

当元素被插入到关联式容器中时，容器内部结构便依照其键值大小，以某种特定规则将这个元素放置于适当位置。关联式容器没有所谓头尾，所以也不会有所谓push_back()、push_front()等操作。

关联式容器的内部结构是一个balanced binary tree（平衡二叉树），以便获得良好的搜寻效率。balanced binary tree有许多类型，包括AVL-tree，RB-tree，AA-tree，其中最被广泛运用于STL的是RB-tree（红黑树）。

5.1 树的导览

5.1.1 二叉搜索树（binary search tree）

5.1.2 平衡二叉搜索树（balanced binary search tree）

二叉搜索树可能失去平衡，导致效率过低，AVL-tree、RB-tree、AA-tree均可实现出平衡二叉搜索树，他们插入和删除节点的平均时间较长，但总保持某种程度的平衡，所以元素的访问（搜寻）时间平均而言也就较少。

5.1.3 AVL tree（Adelson-Velskii-Landis tree）

AVL tree要求任何节点的左右子树高度相差最多1。

只要调整“插入点至根节点”路径上，平衡状态被破坏之各节点中最深的哪一个，便可使整棵树重新获得平衡。

假设该最深节点为X，由于节点最多拥有两个子节点，而所谓“平衡被破坏”意味着X的左右两棵子树的高度相差2，因此可以分为以下四种情况：

1. 插入点位于X的左子节点的左子树——左左；（外侧插入，采用单旋转调整）
2. 插入点位于X的左子节点的右子树——左右；（内侧插入，采用双旋转调整）
3. 插入点位于X的右子节点的左子树——右左；（内侧插入，采用双旋转调整）
4. 插入点位于X的右子节点的右子树——右右；（外侧插入，采用单旋转调整）

5.1.4 单旋转（Single Rotation）

5.1.5 双旋转（Double Rotation）

5.2 RB-tree（红黑树）

Ch5 关联式容器

原文：http://www.cnblogs.com/atmacmer/p/6362436.html