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