diff options
Diffstat (limited to 'avl.kpl')
| -rw-r--r-- | avl.kpl | 68 |
1 files changed, 34 insertions, 34 deletions
@@ -13,7 +13,7 @@ max : `{[I64 a; I64 b] ? a > b { a } { b } } get_balance : `{[Node n] ? n { - - (height `sync n.left; height `sync n.right) + - (height `call n.left; height `call n.right) } { 0 } @@ -32,8 +32,8 @@ right_rotate : `{[Node y] ? !y { `return `null } x : y.left; t2 : x.right; - y.height : 1 + max `sync (height `sync y.left; height `sync y.right) - x.height : 1 + max `sync (height `sync x.left; height `sync x.right) + y.height : 1 + max `call (height `call y.left; height `call y.right) + x.height : 1 + max `call (height `call x.left; height `call x.right) x } @@ -41,8 +41,8 @@ left_rotate : `{[Node x] ? !x { `return `null } y : x.right; t2 : y.left; - x.height : 1 + max `sync (height `sync x.left; height `sync x.right) - y.height : 1 + max `sync (height `sync y.left; height `sync y.right) + x.height : 1 + max `call (height `call x.left; height `call x.right) + y.height : 1 + max `call (height `call y.left; height `call y.right) y } @@ -54,72 +54,72 @@ left_rotate : `{[Node x] insert : `{[Node n] ? !n { avl.size +: 1 - `return new_node `sync (key; value) + `return new_node `call (key; value) } - cmp : avl.compare_fn `sync (n.key; key) + cmp : avl.compare_fn `call (n.key; key) ? { - cmp < 0 { n.left : insert `sync n.left } - cmp > 0 { n.right : insert `sync n.right } + cmp < 0 { n.left : insert `call n.left } + cmp > 0 { n.right : insert `call n.right } { n.value : value `return n } } - n.height : 1 + max `sync (height `sync n.left; height `sync n.right) - balance : get_balance `sync n + n.height : 1 + max `call (height `call n.left; height `call n.right) + balance : get_balance `call n ? { - & (balance > 1; cmp < 0) { right_rotate `sync n } - & (balance < -1; cmp > 0) { left_rotate `sync n } + & (balance > 1; cmp < 0) { right_rotate `call n } + & (balance < -1; cmp > 0) { left_rotate `call n } & (balance > 1; cmp > 0) { - n.left : left_rotate `sync n.left - right_rotate `sync n + n.left : left_rotate `call n.left + right_rotate `call n } & (balance < -1; cmp < 0) { - n.right : right_rotate `sync n.right - left_rotate `sync n + n.right : right_rotate `call n.right + left_rotate `call n } { n } } } - avl.root : insert `sync avl.root + avl.root : insert `call avl.root Void } `export avl_delete : `{[Avl avl; Any key] delete : `{[Node n; Any key] ? !n { `return n } - cmp : avl.compare_fn `sync (n.key; key) + cmp : avl.compare_fn `call (n.key; key) ? { - cmp < 0 { n.left : delete `sync (n.left; key) - cmp > 0 { n.right : delete `sync (n.right; key) + cmp < 0 { n.left : delete `call (n.left; key) + cmp > 0 { n.right : delete `call (n.right; key) { ? | (!n.left; !n.right) { n : ? n.left { n.left } { n.right } } { - tmp : min_value_node `sync n.right + tmp : min_value_node `call n.right n.key : tmp.key n.value : tmp.value - n.right : delete `sync (n.right; tmp.key) + n.right : delete `call (n.right; tmp.key) } } } ? !n { `return n } - n.height : 1 + max `sync (height `sync n.left; height `sync n.right) - balance : get_balance `sync n + n.height : 1 + max `call (height `call n.left; height `call n.right) + balance : get_balance `call n ? { - & (balance > 1; 0 <= get_balance `sync n.left) { right_rotate `sync n } - & (balance > 1; 0 > get_balance `sync n.left { - n.left : left_rotate `sync n.left - right_rotate `sync n + & (balance > 1; 0 <= get_balance `call n.left) { right_rotate `call n } + & (balance > 1; 0 > get_balance `call n.left { + n.left : left_rotate `call n.left + right_rotate `call n } - & (balance < -1; 0 >= get_balance `sync n.right) { left_rotate `sync n } - & (balance < -1; 0 > get_balance `sync n.right) { - n.right : right_rotate `sync n.right - left_rotate `sync n + & (balance < -1; 0 >= get_balance `call n.right) { left_rotate `call n } + & (balance < -1; 0 > get_balance `call n.right) { + n.right : right_rotate `call n.right + left_rotate `call n } { n } } } - avl.root : delete `sync (avl.root; key) + avl.root : delete `call (avl.root; key) Void } |