Red black tree sort/Wren: Difference between revisions
Content deleted Content added
m Fixed some typos. |
Improved approach to check for duplicates - see talk page. |
||
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
| |||