您的位置: 首页 > 文章 > 关联式容器

关联式容器

分类: 文章 • 2025-02-06 20:13:28

平衡二叉搜索树：根据平衡条件的不同有AVL树，红黑树等。

当在AVL树中插入一个新节点时，导致某个节点的高度差变为了2，则此时需要调整。假设平衡被破坏的最深节点为X,则平衡被破坏的情况有如下四种（插入点不可能直接在左右节点上，否则该树平衡早就被破坏了）：

关联式容器

k1,k2,k3是以节点X为标准得出的。