今天先看一下2-3-4 Tree的定义和规则:
顾名思义,每个节点可以有2个,3个,最多4个子节点,而key的个数则为1个,2个,最多3个。那么2-3-4树如何实现的自平衡呢?以插入为例,插入的规则如下:
1. key只插入到叶节点中;
2. 当叶节点的key已满而无法插入的时候,需要对节点进行拆分。将中间节点移到父节点中,从而使当前节点可以容纳新的key。
这时有可能出现这种情况,当将中间节点移到父节点时,父节点的key已满,则父节点也需要进行拆分。这样导致情况变得复杂。所以在2-3-4的实现中,会在插入的过程中,对经过的节点进行检查,将这种情况“扼杀”于摇篮之中。即从根节点开始,由上而下,遇到一个已满的节点就对其进行拆分。这样,当到达叶节点的时候,该节点可以直接插入新的key。
因此拆分节点的时候,一般有下面两种情况:
上面就是插入key的基本规则。2-3-4树就是通过这两条规则,从而实现了自平衡。那么究竟为什么这两条规则可以实现自平衡呢?我来谈谈我的理解。
首先,回忆一下普通二叉树什么时候会失衡。在key已经是有序的情况下,由于key的有序,导致新加入的key不断的加入到节点的某一个方向,从而导致了失衡。而2-3-4树则不会出现这种情况。当key有序的加入时,当一个固定方向的叶节点的key已满时,这时拆分发生了。叶节点需要把中间的key提交到父节点处。这时就显出2-3-4数的好处了。一共3个key,中间的key可以看作中值。这时把中值向父节点提交后。由于中值的key加到了父节点,那么后序的key会逐渐向另一方向转移,而不会在一个固定的方向持续添加。即使所有的key是有序的,从而导致最早提交的中间的key并不是中值。但是随着子节点的不断拆分,不断的提交中间的key。这个中间的key就逐渐接近中值。那么当父节点的key为中值的时候,后续的key就会平均的添加到其各个方向的子节点上,从而实现了自平衡。
至于为什么插入key的时候,只能插入到叶节点上。我的理解是在这个条件下,按照上面的规则可以很容易的实现自平衡。而如果新的key可以插入到父节点上,这时为实现自平衡,无疑增加了难度。
下面看看我实现的2-3-4 Tree的代码。由于只是为了便于自己对2-3-4 Tree的理解,所以只实现了插入部分的代码(理解了插入,删除也就好理解了),且没有考虑申请内存失败的情况。另外,好几年没有写过C++代码了,代码可能写的有些难看,望大家见谅和指正。
2-3-4 Tree的结构声明,目前实现了insert操作。这里实现的insert是支持插入重复的key值。这个结构是对外的接口,所以声明尽量简单,不暴露内部结构和逻辑。
#ifndef TWO_THREE_FOUR_THREE_H_
#define TWO_THREE_FOUR_THREE_H_
#include <cstddef>
class TwoThreeFourNode;
class TwoThreeFourTree {
public:
TwoThreeFourTree();
~TwoThreeFourTree();
void insert(int key);
private:
TwoThreeFourNode *root;
};
#endif
2-3-4 Tree的实现代码。其中的逻辑都是委托TwoThreeFourNode实现的。
#include <cstddef>
#include "two_three_four_tree.h"
#include "two_three_four_node.h"
TwoThreeFourTree::TwoThreeFourTree()
{
root = NULL;
}
TwoThreeFourTree::~TwoThreeFourTree()
{
if (root) delete root;
}
void TwoThreeFourTree::insert(int key)
{
if (!root) {
root = new TwoThreeFourNode();
}
return root->insert(key);
}
TwoThreeFourNode的声明,其为2-3-4 Tree的内部类,所以在声明中可以暴露一些内部数据和逻辑。
#ifndef TWO_THREE_FOUR_NODE_H_
#define TWO_THREE_FOUR_NODE_H_
#include <cstddef>
#include <cstring>
class TwoThreeFourNode {
public:
TwoThreeFourNode():key_cnt(0), parent(NULL) {
memset(child, NULL, sizeof(child));
};
~TwoThreeFourNode() {
for (int i = 0; i < MAX_CHILD_CNT; ++i) {
delete child[i];
}
};
void insert(int key);
private:
enum {
MAX_DATA_CNT = 3,
MAX_CHILD_CNT,
};
bool need_split(void) const { return key_cnt == MAX_DATA_CNT;};
void split_node(void);
bool is_root_node(void) const { return parent == NULL;};
bool is_leaf_node(void) const {
for (int i = 0; i < MAX_CHILD_CNT; ++i) {
if (child[i]) {
return false;
}
}
return true;
}
int get_child_node_index(const TwoThreeFourNode *child_node);
void add_key(int new_key);
void add_child(TwoThreeFourNode *child_node, int index);
void add_key_to_child(int new_key);
int key[MAX_DATA_CNT];
int key_cnt;
TwoThreeFourNode *child[MAX_CHILD_CNT];
TwoThreeFourNode *parent;
};
#endif
TwoThreeFourNode类的实现代码
#include <cassert>
#include "two_three_four_node.h"
void TwoThreeFourNode::insert(int new_key)
{
/* check itself */
if(need_split()) {
split_node();
/* Because split this node, so need recheck the parent node */
if (parent) {
parent->insert(new_key);
return;
}
}
if (is_leaf_node()) {
add_key(new_key);
}
else {
add_key_to_child(new_key);
}
return;
}
void TwoThreeFourNode::add_key(int new_key)
{
int index = 0;
while (index < key_cnt && new_key >= key[index]) {
++index;
}
if (index < key_cnt) {
memmove(key+index+1, key+index, (key_cnt-index)*sizeof(int));
}
key[index] = new_key;
++key_cnt;
}
void TwoThreeFourNode::add_child(TwoThreeFourNode * child_node, int index)
{
child[index] = child_node;
if (child_node) {
child_node->parent = this;
}
}
void TwoThreeFourNode::add_key_to_child(int new_key)
{
for (int i = 0; i < key_cnt; ++i) {
if (new_key <= key[i]) {
if (NULL == child[i]) {
TwoThreeFourNode *new_child = new TwoThreeFourNode();
new_child->add_key(new_key);
add_child(new_child, i);
return;
}
else {
child[i]->insert(new_key);
return;
}
}
}
//这块代码有些冗余,应该可以和上面的代码合并。单独去判断最右侧的子节点,显得有些奇怪。
//不过由于这只是一个练手代码,我也就接受了。
/* check the rightmost child */
if (NULL == child[key_cnt]) {
TwoThreeFourNode *new_child = new TwoThreeFourNode();
new_child->add_key(new_key);
add_child(new_child, key_cnt);
}
else {
child[key_cnt]->insert(new_key);
}
}
int TwoThreeFourNode::get_child_node_index(const TwoThreeFourNode * child_node)
{
for (int i = 0; i < key_cnt+1; ++i) {
if (child_node == child[i]) {
return i;
}
}
return -1;
}
/*
拆分节点的时候。根节点的拆分方法和普通节点不同。这两部分处理要合并有点困难。
但是目前这个函数有点长。在真正写代码时,如果真的不能合并处理,我会将其分为两个子函数。
*/
void TwoThreeFourNode::split_node(void)
{
if (is_root_node()) {
TwoThreeFourNode *new_left_child = new TwoThreeFourNode();
TwoThreeFourNode *new_right_child = new TwoThreeFourNode();
new_left_child->key[0] = key[0];
new_left_child->key_cnt = 1;
new_left_child->add_child(child[0], 0);
new_left_child->add_child(child[1], 1);
add_child(new_left_child, 0);
new_right_child->key[0] = key[2];
new_right_child->key_cnt = 1;
new_right_child->add_child(child[2], 0);
new_right_child->add_child(child[3], 1);
add_child(new_right_child, 1);
key[0] = key[1];
key_cnt = 1;
child[2] = NULL;
child[3] = NULL;
}
else {
TwoThreeFourNode *new_node = new TwoThreeFourNode();
new_node->key[0] = key[0];
new_node->key_cnt = 1;
new_node->add_child(child[0], 0);
new_node->add_child(child[1], 1);
int new_index = parent->get_child_node_index(this);
assert(new_index != -1);
memmove(parent->child+new_index+1, parent->child+new_index, (parent->key_cnt-new_index+1)*sizeof(TwoThreeFourNode *));
if (new_index < parent->key_cnt) {
memmove(parent->key+new_index+1, parent->key+new_index, (parent->key_cnt-new_index)*sizeof(int));
}
parent->key[new_index] = key[1];
++parent->key_cnt;
parent->add_child(new_node, new_index);
key[0] = key[2];
key_cnt = 1;
add_child(child[2], 0);
add_child(child[3], 0);
child[2] = NULL;
child[3] = NULL;
}
}
总结一下这次使用C++的体会。
1. 毕竟好久没用了,有些细节和语法有点生疏了;
2. 使用C++,按照面向对象的方式去思考,给程序的设计还是带了方便。毕竟减少了耦合性,可以尽量独立的考虑某一对象的问题,而不用去想着是否对其它对象有什么影响。所有的涉及某一对象的操作,都交由该对象自己去处理完成。
3. 当使用对象的方法去处理的时候。有时会忘记了需要指定正确的对象,而不是直接调用该方法。毕竟类的方法是基于对象的。写C写多了。当调用函数的时候,更多的是去关注参数,只要参数对了,就是我所期待的行为。而在C++中,由于类的方法是有一个隐藏参数this的。所以必须要指定正确的对象。这样,在两三处,都忘了指明正确的对象导致了问题的发生。