红黑树定义和性质
性质1:每个节点要么是黑色,要么是红色。
性质2:根节点是黑色。
性质3:每个叶子节点(NIL)是黑色。
性质4:每个红色结点的两个子结点一定都是黑色。
性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。
简单来说:非红即黑;两头黑;红下黑;各路径黑节点同数量
红黑树的查找、插入、删除的时间复杂度最坏为
暂时不深究,实用主义。
最大堆ADT
父节点值大于子节点,且是完全二叉树
- 最大堆的数据结构:层级保存的数组
- 最大堆插入元素:结点上浮(直接加入尾部,依次比较新增结点和父节点,进行上浮操作)
- 最大堆删除元素:结点下沉(删除结点与末尾结点交换,该结点依次比较大小,进行下沉操作)