红黑树与平衡二叉树

平衡二叉树: 维持左右子树平衡
平衡因子(左右子树高度差)绝对值小于1,若超过就会进行左/右旋来保持平衡,比较耗时,因此在频繁插入删除的场景不适用,适用于查询多的场景

红黑树: 维持左右子树大致平衡

  1. 根节点是黑的;
  2. 每个节点非红即黑
  3. 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的;
  4. 如图所示，如果一个节点是红的，那么它的两儿子都是黑的;
  5. 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;

文献:
https://blog.csdn.net/u010899985/article/details/80981053

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容