DAY2 红黑树+最大堆

2020-04-19  本文已影响0人  神游物外的轮子

红黑树定义和性质

性质1:每个节点要么是黑色,要么是红色。
性质2:根节点是黑色。
性质3:每个叶子节点(NIL)是黑色。
性质4:每个红色结点的两个子结点一定都是黑色。
性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

简单来说:非红即黑;两头黑;红下黑;各路径黑节点同数量
红黑树的查找、插入、删除的时间复杂度最坏为O(\log{n})
暂时不深究,实用主义。

最大堆ADT

父节点值大于子节点,且是完全二叉树

上一篇下一篇

猜你喜欢

热点阅读