抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >
# T tree T tree 是一颗二叉树,他和avl tree有着一定的联系,总所周知,avl树为一颗二叉树,利用其中序维护信息,利用子树高度维护平衡。我们借此修改一下,我们尝试让avl树的每个节点维护多个信息[信息序列],于是T tree就出现了。T tree是一颗二叉树,每个节点维护一个有序序列,用T 树的中序遍历方式,将其节点维护的序列依次相连即成为了我们维护的信息。

T tree 解释

为了便于编码,我们不考虑序列中会出现相同的元素,可以证明,对于泛型编程方式而言,这并不影响该数据结构的功能,该数据结构依旧具备维护相同元素的能力

T tree结论

非叶节点维护的序列都充满了各自的容器

T tree树上信息

每一颗子树都要维护一个序列,对于每个节点,我们都维护一个稍微小一点的序列,比该序列中元素更小的元素放入左子树,否则放入右子树。

T tree搜索

搜索的话,就是普通二叉树的搜索,比当前节点维护的最小值小,就在左子树找,比当前节点维护的最大值大,就在右子树找,否则就在当前节点找

T tree插入

当我们插入一个数的时候,我们首先递归向下,找到插入的节点位置,若该节点中储存的序列未满,则置入该节点,否则,有两种处理方式,第一种是从该节点中取出最小值,放入左子树,然后把带插入的树放入该节点,第二种是放入右子树,这里不多说明。插入可能会导致树失去平衡,我们用avl树单旋的方式来让树重新平衡

T tree删除

当我们删除一个数的时候,像avl树一样处理,若该数在叶子上,简单删掉并维护树的平衡即可,让该数在非叶节点时,我们取出前驱或后继来顶替即可。

T tree一个容易出错的地方

笔者在编码的时候,遇到了一个问题,就是有时候会出现非叶节点维护的数据并未充满容器,这种情况发生的原因是单旋造成的。在单旋的时候,将叶子结点旋转成非叶节点后,我们应该调整数据,让非叶节点重新维护的数据充满容器

T treecode

TT代码

评论