二叉树06.从2-3-4树到红黑树
作者:刘涛 2022-02-18 V1.0.0 1. 前言 红黑树是一种自平衡二叉查找树(Self-balancing binary search tree)。 如前文所述,根据红黑树的定义去理解其设计思想是非常困难的,但借助 B 树我们却可以更好地理解它,因为红黑树本就是由4阶B树推导而来。 全文较长,但为了完整的阅读体验,所以没有拆分为多篇文章,读者可以自行挑选阅读感兴趣的章节。 代码仓库:https://github.com/patricklaux/perfect-code 系列文章 (1) 深度优先遍历之递归和非递归遍历 (2) 深度优先遍历之 Morris 遍历 (3) 一种无需队列的层序遍历算法 IDDFS (4) 深度分析AVL树的实现与优化 (5) B树详解与实现 (6) 从2-3-4树到红黑树【本文】 2. 由来 (1) 1972 年,Rudolf Bayer 提出了 “symmetric binary B-tree”,这是B 树的 4 阶情形,也就是 2-3-4树(或称为 2-4 树)[1]。 (2) 1978 年,Leonidas J. Guibas 和 Robe...