前言
红黑树Java实现
正文
一. 概述
红黑树是一颗平衡二叉树, 是为了避免二叉查找树在极端情况下形成单链表而表现出线性级别的时间复杂度; 红黑树的前身是2-3查找树, 为了便于理解红黑树的各种旋转操作, 需要先了解一下2-3查找树
平衡二叉树始终要保证的是所有空链接(指向一棵空树的链接)到根节点的距离相等
二. 2-3查找树
2.1 基本概念
为了保证树的平衡性, 2-3查找树允许树中的一个节点保存多个键; 如下图
2-结点: 含有一个键(及其对应的值)和两条链接, 左链接指向的2-3树中的键都小于该结点, 右链接指向的2-3树中的键都大于该结点 3-结点: 含有两个键(及其对应的值)和三条链接, 左链接指向的2-3树中的键都小于该结点, 右链接指向的2-3树中的键都大于该结点, 中链接指向的2-3树中的键介于该结点之间
一棵完美平衡的2-3查找树中的所有空链接到根结点的距离都是相同的
2.2 2-3树的插入
2.2.1 向2-结点中插入新键
这种情况比较简单, 直接将2-结点替换为3-结点即可
