瑞典保险公司Folksa数据泄露

节点介绍

2-3-4树到红黑树的转化

红黑树是对概念模型2-3-4树的一种实现，由于直接进行不同节点间的转化会造成较大的开销，所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3-4树中不同的节点。

2-3-4树中的2节点对应着红黑树中的黑色节点，而2-3-4树中的非2节点是以红节点+黑节点的方式存在，红节点的意义是与黑色父节点结合，表达着2-3-4树中的3，4节点。

(此处理解成红节点也好，红色链接也好，看个人喜好。很多书中会说是由黑色节点指出的红色链接，链接指向的节点颜色为红。)

我们先看2-3-4树到红黑树的节点转换。2节点直接转化为黑色节点;3节点这里可以有两种表现形式，左倾红节点或者右倾红节点。而4节点被强制要求转化为一个黑父带着左右两个红色儿子。
 

其实当面试官提出这个问题的时候，不参照答案，他大概率也无法清晰的给出具体的定义和操作。但是他希望从这个问题出发，看到你对于一个数据结构的理解，考察你知识面的广度和深度。能否给出完整的定义，能否介绍自己对红黑树的认识，能否通过旋转，染色等操作在给定的场景下对一颗红黑树进行调整使其符合定义......这些才是面试官希望从你的答案中得到的信息，问了一圈身边大厂的面试官朋友，跟我这个说法出入不大。

读完这篇文章，你将能够从红黑树的概念模型2-3-4树出发，理解红黑树五大定义背后的逻辑。你也可以深刻认识到红黑节点颜色背后的意义，对于插入删除引发的动态变化有一定的认识，而不再是去硬性的记忆某个场景下的调平操作(诸如：删除某节点，当该节点的叔父节点为红，而叔父节点的左右子节点都为黑的情况下，我们应该......)。你能够掌握节点旋转的具体操作，理解染色的目的。

最后，如果你足够认真，配图中有清晰的插入删除全部步骤，你能够真正的将红黑树变成自己的知识。

先谈平衡树

做开发的朋友一定知道接口这个东西：定义接口，给出实现。一个接口可以有多种不同的实现，但是这些实现都会满足接口中的声明。

例如，我们定义手机是一个可用作通讯的工具，作为它的实现，三星，苹果，华为推出了各式各样的产品。

红黑树的本质其实也是对概念模型：2-3-4树的一种实现，因此我们先来关注2-3-4树。

2-3-4树是阶数为4的B树，B树，全名BalanceTree，平衡树。这种结构主要用来做查找。

关于B树(平衡多路查找树)的定义，网上已经有很多介绍，在此不多赘述。它最重要的特性在于平衡，这使得我们能够在最坏情况下也保持O(LogN)的时间复杂度实现查找(一个不具备平衡性的查找树可能退化成单链表，时间复杂度会到O(N))。

在此需要提醒大家一下，平衡的定义是说从空链接到根节点距离相等，此处一定要用心理解。(也就是说非叶子节点是不会存在空链接的)

由于2-3-4树是一颗阶数为4的B树，所以它会存在以下节点：

• 2节点
• 3节点
• 4节点

2节点中存放着一个key[X]，两个指针，分别指向小于X的子节点和大于X的子节点;3节点中存放在两个key[X,Y],三个指针，分别指向小于X的子节点，介于X~Y之间的子节点和大于Y的子节点;4节点可依此类推。

（编辑：鹰潭站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!