Red black tree sort/Wren: Difference between revisions
Content deleted Content added
m Fixed some typos. |
m Changed to Wren S/H |
||
| (2 intermediate revisions by the same user not shown) | |||
Line 2:
Although red black trees don't necessarily need to disallow duplicate keys, I've adjusted the code to optionally disallow them. Not that it matters here as the method of constructing the random keys ensures that there will be no duplicates in any case.
<
/* Represents a node in the red-black tree. */
Line 353:
// and fix the tree
insert(key) {
// if duplicates aren't allowed and the key has already been used, simply return▼
if (!_allowDups && hasKey(key)) return▼
// ordinary binary search insertion
var node = Node.new(key, null, _tnull, _tnull, 1) // new node must be red▼
var y = null
var x = _root
while (x != _tnull) {
y = x
if (
x = x.left
} else {
Line 368 ⟶ 364:
}
}
▲ // if duplicates aren't allowed and the key has already been used, simply return
// new node must be red
// y is parent of x
Line 423 ⟶ 425:
System.print(deletions)
System.print()
bst.prettyPrint()</
{{out}}
| |||