Splay heapsΒΆ
A search binary tree is defined by subclassing
CTBinaryTreeAbstract subclass: #CTSplayHeap
instanceVariableNames: ''
classVariableNames: ''
package: 'Containers-SplayHeap'
and the corresponding test class defines,
"CTSplayHeapTest, protocol tests"
tree: aCollection
^ aCollection asSplayHeap
that uses
"Collection, protocol *Containers-SplayHeap"
asSplayHeap
^ self asBinaryTree: CTSplayHeap
to show the following inspectors. First, the empty tree looks like
Second, we have the four cases:
sorted data in arrayed collection,
by means of
"CTBinaryTreeNodeSplayHeap, protocol actions" mergeBinaryTreeElement: aBTElement inBinaryTree: aBinaryTree ^ aBTElement partition: value inSplayHeap: aBinaryTree do: [ :l :r | | lMerged rMerged | lMerged := l mergeBinaryTreeElement: previousLink inBinaryTree: aBinaryTree. rMerged := r mergeBinaryTreeElement: nextLink inBinaryTree: aBinaryTree. aBinaryTree leftBinaryTreeElement: lMerged value: value rightBinaryTreeElement: rMerged ]
that dispatches over
"CTBinaryTreeEmptySplayHeap, protocol partitioning" partition: pivot inSplayHeap: aHeap do: aBlock ^ aBlock value: aHeap binaryTreeElementEmpty value: aHeap binaryTreeElementEmpty
"CTBinaryTreeNodeSplayHeap, protocol partitioning" partition: pivot inSplayHeap: aHeap do: aBlock ^ (aHeap is: value lessThan: pivot) ifTrue: [ self partitionLessThan: pivot inSplayHeap: aHeap do: aBlock ] ifFalse: [ self partitionGreaterThanOrEqualTo: pivot inSplayHeap: aHeap do: aBlock ]
where the latter uses both
"CTBinaryTreeNodeSplayHeap, protocol partitioning" partitionLessThan: pivot inSplayHeap: aHeap do: aBlock ^ nextLink ifEmpty: [ aBlock value: self value: aHeap binaryTreeElementEmpty ] ifNotEmpty: [ | y | y := nextLink value. (aHeap is: y lessThan: pivot) ifTrue: [ nextLink nextLink partition: pivot inSplayHeap: aHeap do: [ :s :b | | ll l | ll := aHeap leftBinaryTreeElement: previousLink value: value rightBinaryTreeElement: nextLink previousLink. l := aHeap leftBinaryTreeElement: ll value: y rightBinaryTreeElement: s. aBlock value: l value: b ] ] ifFalse: [ nextLink previousLink partition: pivot inSplayHeap: aHeap do: [ :s :b | | r l | l := aHeap leftBinaryTreeElement: previousLink value: value rightBinaryTreeElement: s. r := aHeap leftBinaryTreeElement: b value: y rightBinaryTreeElement: nextLink nextLink. aBlock value: l value: r ] ] ]
and
"CTBinaryTreeNodeSplayHeap, protocol partitioning" partitionGreaterThanOrEqualTo: pivot inSplayHeap: aHeap do: aBlock ^ previousLink ifEmpty: [ aBlock value: aHeap binaryTreeElementEmpty value: self ] ifNotEmpty: [ | y | y := previousLink value. (aHeap is: y lessThan: pivot) ifTrue: [ previousLink nextLink partition: pivot inSplayHeap: aHeap do: [ :s :b | | r l | l := aHeap leftBinaryTreeElement: previousLink previousLink value: y rightBinaryTreeElement: s. r := aHeap leftBinaryTreeElement: b value: value rightBinaryTreeElement: nextLink. aBlock value: l value: r ] ] ifFalse: [ previousLink previousLink partition: pivot inSplayHeap: aHeap do: [ :s :b | | r rr | rr := aHeap leftBinaryTreeElement: previousLink nextLink value: value rightBinaryTreeElement: nextLink. r := aHeap leftBinaryTreeElement: b value: y rightBinaryTreeElement: rr. aBlock value: s value: r ] ] ]
in turn.
sorted data in ordered collection,
by means of
"CTSplayHeap, protocol adding" push: anObject representation := representation partition: anObject inSplayHeap: self do: [ :l :r | self leftBinaryTreeElement: l value: anObject rightBinaryTreeElement: r ]
shuffled data in arrayed collection,
shuffled data in ordered collection,
