2-3树是一颗一般查找树,其内部结点必须有2个或3个孩子。

 

2-结点含有1个数据项s和2个孩子,与二叉查找树的结点一样。数据s大于结点的左子树中的所有数据,且小于右子树中的所有数据。

3-结点含有2个数据项s和l,以及3个孩子。小于较小数据项s的数据出现结点的左子树中。大于较大数据项l的数据出现在结点的右子树中。介于s和l之间的数据出现在结点的中间子树中。

因为2-3树能含有3-结点,所以它比二叉查找树更低,要使2-3树平衡,需要所有的叶子出现在同一层。所以2-3树是完全平衡树。

        2-3树是一颗一般查找树,其内部结点必须含有2个或3个孩子,且叶子都在同一层。2-3树是完全平衡树。

Algorithm search23Tree(23Tree, desiredObject)
// 在2-3树中查找给定的对象
// 如果找到对象,则返回真
if (23Tree为空)
    return false
else if (desiredObject在23Tree的根中)
    return true
else if(23Tree的根含有两个项)
{
    if (desiredObject < 根中较小的对象)
        return search23Tree(23Tree的左子树,desiredObject)
    else if (desiredObject > 根中的较大的对象)
        return search23Tree(23Tree的右子树, desiredObject)
    else
        return search23Tree(23Tree的中间子树, desiredObject)
}
else if (desiredObject < 根中的对象)
    return search23Tree(23Tree的左子树, desiredObject)
else
    return search23Tree(23Tree的右子树, desiredObject)

Logo

魔乐社区(Modelers.cn) 是一个中立、公益的人工智能社区,提供人工智能工具、模型、数据的托管、展示与应用协同服务,为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作,由全产业链共同建设、共同运营、共同享有,推动国产AI生态繁荣发展。

更多推荐