根据我的理解,在一个已经排序的左-子-右兄弟树中,如果我想向其中添加一个子,我们说"F";在";E〃;我必须遍历每个兄弟节点,这样它的时间复杂度为O(n(。这是最理想的吗?有办法提高效率吗?如果是,如何?
A
/
B->C->D->E
如果我想给它添加一个子项,我们说"F";在";E〃;我必须遍历每个兄弟
对于您描述的特定操作,在您描述的特殊树上:是。
使得它的时间复杂度为O(n(。
不,它没有。这种分析从一个案例中作出了不恰当的概括。
对于大于2的一些k,左-子-右兄弟树通常用作k元树的二叉树表示。在这种情况下,性能特征与相应的k元树的性能特征没有什么不同。
您似乎忽略了一个关键点,即在任何给定的左-子-右同级树中,任何节点的同级数都将以常数为界。因此,遍历节点的同级节点的成本不会随着节点总数的增加而增加。相反,它是O(k(=O(1(。
还要考虑插入后的树可能是什么。如果你的例子对应于一个5(或更多(元树,那么它可能是
A
/
B->C->D->E->F
,但是如果它对应于四元树,那么这是不可能的。相反,结果可能是以下任何一种:
A
/
B->C->D->F
/
E
A
/
C->D->E->F
/
B
A
/
B->C->E->F
/
D
或许多其他。如果你进一步构建它,你会发现,只要树是近似平衡的,不,在树中搜索关键字或插入位置不会花费O(n(,而是O(logn(,就像搜索直k元(包括二进制(树一样。
这是最理想的吗?有办法提高效率吗?如果是,如何?
产生更平衡树的插入策略将比产生不平衡树的策略带来更好的最坏情况搜索效率。总体上最糟糕的情况确实是一个无分支树,它相当于一个链表,但这个问题与产生更好搜索结果的策略不一致。
如果只想在最后一个元素'E'
之后添加元素,那么可以通过保持指向存储在A
中的元素E
的指针,并在添加F
之后更新存储在A
中的指针,使其保持不变。
如果你想添加任何元素,并且仍然想保持元素的排序,那么你可以创建一个Binary Tree
,并达到O(log2 N)
的时间复杂性。您可以通过使该数据结构成为一个平衡树(,即AVL树(来进一步改进该数据结构。AVLs
比二叉树具有更好的平均和最坏情况下的复杂性,因为它们避免了某些子树过长,甚至在极端情况下,将列表作为子树。