C++ 中的 2-3 树实现

• 下载源代码 - 18.2 KB 
• 下载 2-3TreeImplementation.zip (VS2012 项目) 
• 下载 TreeTestCases.zip
• 下载 2-3 树演示文稿

引言   

本文提供 C++ 语言的 2-3 树实现。该实现基于网上找到的几篇文章。这些文章可以在参考文献部分找到，其中还提供了对 2-3 树进行深入解释的文章。

在实现中，我使用了一种线索树。线索树使用父指针。这个父指针可以更容易地从子节点移动到其对应的父节点，而无需使用递归。此外，我使用了模板，以便在 2-3 树中使用不同的数据类型。  

背景   

2-3 树是一种多叉搜索树，其中每个节点有两个子节点（称为二节点）或三个子节点（称为三节点）。二节点包含一个元素。左子树包含小于节点元素的元素。右子树包含大于节点元素的元素。然而，与二叉搜索树不同的是，二节点可以有零个子节点或两个子节点，但不能只有一个子节点。 三节点包含两个元素，一个指定为较小元素，一个指定为较大元素。三节点可以有零个子节点或三个子节点。如果三节点有子节点，左子树包含小于较小节点元素的元素。右子树包含大于较大节点元素的元素。中间子树包含大于较小节点元素且小于较大节点元素的元素。 由于 2-3 树的自平衡特性，所有叶子都在同一级别。大小为 N 的 2-3 树的搜索时间复杂度为 O(log N)。  

向 2-3 树插入元素   

在 2-3 树中，所有插入都发生在树的叶子节点。搜索树以确定新元素的位置，然后进行插入。向 2-3 树插入元素的过程可能会对树的其余结构产生连锁反应。向 2-3 树插入元素可分为三种情况。  

1. 最简单的情况是树为空。在这种情况下，创建一个包含新元素的新节点。然后将该节点指定为树的根。 
2. 第二种情况发生在我们要将新元素插入到作为二节点的叶子节点中时。在这种情况下，将新元素添加到二节点中，使其成为三节点。 
3. 第三种插入情况发生在我们要将新元素插入到作为三节点的叶子节点中时。在这种情况下，将三节点拆分，并将中间元素移到树中的上一级别，然后重复插入过程。当拆分树的根时，树的高度会增加一。 

从 2-3 树中删除元素   

从 2-3 树中删除元素也包含三种情况。 

1. 最简单的情况是，要删除的元素位于作为三节点的叶子节点中。在这种情况下，删除只是从节点中删除该元素的问题。  
2. 第二种情况是，要删除的元素位于作为二节点的叶子节点中。 这种情况称为下溢，并造成了我们必须旋转或合并节点以维持 2-3 树属性的情况。 
3. 第三种情况是，要删除的元素位于内部节点中。 在这种情况下，我们可以简单地用其按中序遍历的后继节点替换要删除的元素。内部元素的按中序遍历的后继节点始终是叶子节点元素。替换后，我们可以使用第一种或第二种情况简单地删除叶子节点元素。  

 

使用代码

可下载的项目包含一个 2-3 树实现和演示树用法的测试用例。测试用例在项目中包含的文档 TreeTestcases.pdf 中进行了描述。将 zip 文件解压缩到某个目录，即可使用。CTree 的使用非常简单。唯一需要满足的条件是，键对象支持“<”和“<<”运算符，因为在 CTree 类中使用了这两个运算符。 

所有树函数都封装在两个模板类 CTree 和 CNode 中。每个树函数都有一个注释块，描述了该函数的功能。我避免在树中使用递归函数，以避免堆栈溢出。因此，您会发现我所有的代码都使用 while 循环。因此，代码会变得有点复杂，尤其是在打印函数中。 

要创建树对象，请调用默认构造函数： 

CTree<CMovie> *pMovieTree = new CTree<CMovie>(); 

为了使 CTree 对象能够进行必要的键比较，键对象必须实现“<”运算符。  

class CMovie
{
    inline bool operator< (const CMovie& rCMovie) const
    {
        return (strcmp(this->getTitle(), rCMovie.getTitle()) < 0);
    };
}

int CTree<T>::TCompare(const T* const pT1, const T* const pT2) const
{
    int iReturnCode = FAILURE;
    if(*pT1 < *pT2)
    {
        iReturnCode = LESS;
    }
    else if(*pT2 < *pT1)
    {
        iReturnCode = GREATER;
    }
    else
    {
        iReturnCode = EQUAL;
    }
    return iReturnCode;
}     

为了使 CTree 对象能够打印键对象，键对象还必须实现“<<”运算符。

friend std::ostream& operator<< (std::ostream& out, CMovie& rCMovie)
{
    out <<rCMovie.getTitle()<<";"<<rCMovie.getReleaseYear(); 
    return out;
}  

公共 CTree 函数概览

• int insert(const T* const pKey)： 将新键插入树中。  
• int deleteItem(const T* const pKey)：删除一个键并修复树。 
• const T* const find(const T* const)： 在树中搜索指定的键。 
• int print(eTreeTraversal eTraversalMethod) const： 打印所有键（中序、后序和前序）。 
• int removeAll(void)：删除所有树节点。 

测试项目输出 

示例项目演示了对树的各种方法调用。结果输出显示在控制台窗口中。执行其中一个测试用例会产生以下输出： 

  

兴趣点 

该树存储（键）对象。这些对象可以嵌入键属性（用于比较）以及数据属性。如果我们想在树中执行搜索以查找特定对象，就需要创建一个搜索对象，并设置比较属性。然后可以将搜索对象传递给 find 方法，该方法会搜索树并返回找到的对象。 有关如何搜索树的示例可以在演示项目中找到。 

Tree 类中使用的模板在头文件中实现。 由于使用了模板变量，因此使用布尔标志来指示设置了哪些键。 

T m_tSmallKey;
T m_tBigKey;
bool m_bBigKeyIsSet;
bool m_bSmallKeyIsSet;   

代码经过充分测试。测试用例的摘要可以在包含的文档 TreeTestcases.pdf 中找到。 可以对代码进行改进，包括： 将树以图形格式显示，而不是在 Windows 控制台中显示； 优化代码以提高速度；并提高打印函数的可读性。 

参考文献

• Java Software Structures: Lewis and Chase designing and& using data structures (second edition)。 
• 2-3 树实现 UC Riverside. 
• 2-3 树实现 Teach Solaris Games。 
• 涵盖 2-3 树。 
• 2-3 树 Applet 动画。