DAY2 红黑树+最大堆

红黑树定义和性质

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

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

最大堆ADT

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

  • 最大堆的数据结构：层级保存的数组
  • 最大堆插入元素：结点上浮（直接加入尾部，依次比较新增结点和父节点，进行上浮操作）
  • 最大堆删除元素：结点下沉（删除结点与末尾结点交换，该结点依次比较大小，进行下沉操作）
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容