C++STL集合.pptx

C++ 集合的特点，原理，使用 STL set集合容器实现了红黑树（Red-Black Tree）的平衡二叉检索树 的数据结构，在插入元素时，它会自动调整二叉树的排列，把该 元素放到适当位置，以确保每个子树根节点键值大于左子树所有 节点键值，而小于右子树所有节点键值。另外，还得确保根节点 左子树高度与右子树高度相等，这样，二叉树的高度最小，从而 检索速度最快。要注意的是，它不会重复插入相同键值的元素， 而采取忽略处理。如图是一个典型的红黑树。 平衡二叉检索树的检索使用中序遍历算法，中序遍历算法可将键 值由小到大遍历出来，所以，可以理解为平衡二叉检索树在插入 元素时，就会自动将元素按键值由小到大的顺序排列。