美文网首页
DAY2 红黑树+最大堆

DAY2 红黑树+最大堆

作者: 神游物外的轮子 | 来源:发表于2020-04-19 17:13 被阅读0次

红黑树定义和性质

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

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

最大堆ADT

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

  • 最大堆的数据结构:层级保存的数组
  • 最大堆插入元素:结点上浮(直接加入尾部,依次比较新增结点和父节点,进行上浮操作)
  • 最大堆删除元素:结点下沉(删除结点与末尾结点交换,该结点依次比较大小,进行下沉操作)

相关文章

  • DAY2 红黑树+最大堆

    红黑树定义和性质 性质1:每个节点要么是黑色,要么是红色。性质2:根节点是黑色。性质3:每个叶子节点(NIL)是黑...

  • 数据结构—树—红黑树

    红黑树概述 红黑树的插入 红黑树的删除

  • TreeMap

    需要先了解红黑树,这是之前分析红黑树的文章。之前在分析红黑树时,我认为红黑树=二叉查找树+红黑平衡,关于二叉查找树...

  • 数据结构与算法-AVL 红黑树

    AVL树AVL树 算法红黑树红黑树 B站

  • [转载]红黑树

    https://zhuanlan.zhihu.com/p/24367771红黑树简介红黑树插入红黑树删除

  • 拿下红黑树

    红黑树 红黑树、2-3树的简单定义: 实现红黑树的基本结构以及添加操作(维护定义,左旋、右旋、颜色反转) 红黑树与...

  • 红黑树

    啥是红黑树,红黑树 = 二叉树

  • 彻底理解红黑树(二)之 插入

    彻底理解红黑树(一)之 二叉搜索树彻底理解红黑树(二)之 插入彻底理解红黑树(三)之 删除 前言 红黑树的插入情况...

  • 彻底理解红黑树(三)之 删除

    彻底理解红黑树(一)之 二叉搜索树彻底理解红黑树(二)之 插入彻底理解红黑树(三)之 删除 前言 红黑树的删除情况...

  • Golang红黑树

    红黑树 红黑树是每个节点都带有颜色属性(红色或黑色)的二叉查找树。红黑树也属于自平衡二叉查找树。 红黑树具有如下性...

网友评论

      本文标题:DAY2 红黑树+最大堆

      本文链接:https://www.haomeiwen.com/subject/rehsbhtx.html