Red black tree sort/Wren: Difference between revisions
Content deleted Content added
m Removed an unused line. |
m Fixed some typos. |
||
Line 4: | Line 4: | ||
<lang ecmascript>import "random" for Random |
<lang ecmascript>import "random" for Random |
||
/* Represents a node in the red |
/* Represents a node in the red-black tree. */ |
||
class Node { |
class Node { |
||
// constructs a new node |
// constructs a new node |
||
Line 31: | Line 31: | ||
} |
} |
||
/* Represents a red |
/* Represents a red-black tree data structure. */ |
||
class RBTree { |
class RBTree { |
||
// constructs a new red |
// constructs a new red-black tree specifying whether duplicate keys are allowed or not |
||
construct new(allowDups) { |
construct new(allowDups) { |
||
_tnull = Node.new() |
_tnull = Node.new() |
||
Line 278: | Line 278: | ||
// find the node with the maximum key |
// find the node with the maximum key |
||
maximum(node) { |
|||
while (node.right != _tnull) node = node.right |
while (node.right != _tnull) node = node.right |
||
return node |
return node |