etur
0
代码8
4删除
与BST一样，在Treap中删除元素要考虑多种情况。我们可以按照在BST中删除元素同样的方法来删除Treap中的元素，即用它的后继或前驱节点的值代替它，然后删除它的后继或前驱节点。为了不使Treap向一边偏沉，我们需要随机地选取是用后继还是前驱代替它，并保证两种选择的概率均等。上述方法期望时间复杂度为OlogN，但是这种方法并没有充分利用Treap已有的随机性质，而是重新得随机选取代替节点。我们给出一种更为通用的删除方法，这种方法是基于旋转调整的。首先要在Treap树中找到待删除节点的位置，然后分情况讨论：情况一，该节点为叶节点或链节点，则该节点是可以直接删除的节点可以直接删除的节点。若该节点有非空子节点，情况一可以直接删除的节点用非空子节点代替该节点的，否则用空节点代替该节点，然后删除该节点。情况二，该节点有两个非空子节点。我们的策略是通过旋转，使该节点变为可以直接删除的情况二节点。如果该节点的左子节点的修正值小于右子节点的修正值，右旋该节点，使该节点降为右子树的根节点，然后访问右子树的根节点，继续讨论；反之，左旋该节点，使该节点降为左子树的根节点，然后访问左子树的根节点，继续讨论，直到变成可以直接删除的节点。下面给一个删除例子：在Treap中删除值为6的元素。如图11，首先在Treap中找到6的位置。查找615
1
10
2
12
6
30
8
13
4
40
3
19
5
15
f7
15
1
10
2
12
6
30
8
13
4
40
3
19
5
15
7
图SEQ图ARABIC11发现节点6有两个子节点，且左子节点的修正值小于右子节点的修正值，需要右旋节点6，如图12。15
1
10
2
12
6
30
8
13
4
40
3
19
5
15
7
右旋615
1
10
2
13
4
f40
3
12
6
30
8
19
5
150
7
图SEQ图ARABIC12旋转后，节点6仍有两个节点，右子节点修正值较小，于是左旋节点6，如图13。15
1
10
2
13
4
40
3
12
6
30
8
19
5
150
7
左旋615
1
10
2
13
4
40
3
30
8
19
5
15
7
f12
6
图SEQ图ARABIC13
此时，节点6只有一个子节点，可以直接删除，用它的左子节点代替它，删除本身，如图14。15
1
10
2
13
4
40
3
30
8
19
5
15
7
12
6
删除615
1
10
2
13
4
40
3
30
8
19
5
15
7
图SEQ图ARABIC14
删除的复杂度稍高，但是期望时间仍为OlogN，但是在程序中更容易实现。代码9给出了后一种即上述图例中的删除方法，在给定的Treap中删除值为6的节点的代码。BST_Noderoot
fvoidTreap_DeleteTreap_NodePi
tvalue节点指针要传递引用节点指针要传递引用ifvaluePvalue找到要删除的节点对其删除找到要删除的节点ifPrightPr