集合

hashMap数据结构之红黑树

❒ 红黑树的特质

✔ 性质1: 节点要么是红色,要么是黑色
✔ 性质2: 根节点是黑色
✔ 性质3: 叶子节点都是黑色的空节点
✔ 性质4: 红黑树中红色节点的子节点都是黑色
✔ 性质5: 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质。

❒ 什么是红黑树
✔ 红黑树(Red Black Tree):也是一种自平衡的二叉搜索树(BST)
✔ 所有的红黑规则都是希望红黑树能够保证平衡
✔ 红黑树的时间复杂度:查找、添加、删除都是O(logn)