forked from JuliaLang/julia
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtree.jl
90 lines (76 loc) · 1.65 KB
/
tree.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
abstract Tree{K,V}
type EmptyTree{K,V} <: Tree{K,V}
end
type TreeNode{K,V} <: Tree{K,V}
key:: K
data:: V
left:: Tree{K,V}
right::Tree{K,V}
end
type BTree{K,V}
root:: Tree{K,V}
BTree() = new(EmptyTree{K,V}())
end
has(t::EmptyTree, key) = false
has(t::BTree, key) = has(t.root, key)
function has(t::TreeNode, key)
if t.key == key
true
elseif key < t.key
has(t.left, key)
else
has(t.right, key)
end
end
ref(t::EmptyTree, k) = throw(KeyError(k))
ref(t::BTree, k) = t.root[k]
function ref(t::TreeNode, key)
if t.key == key
t.data
elseif key < t.key
t.left[key]
else
t.right[key]
end
end
assign{K,V}(t::EmptyTree{K,V}, v, k) = TreeNode{K,V}(k, v, t, t)
assign(t::BTree, v, k) = (t.root = assign(t.root, v, k); t)
function assign(t::TreeNode, v, k)
if t.key == k
t.data = v
elseif k < t.key
t.left = assign(t.left, v, k)
else
t.right = assign(t.right, v, k)
end
t
end
del(t::EmptyTree, k) = throw(KeyError(k))
del(t::BTree, k) = (t.root = del(t.root, k); t)
function del(t::TreeNode, k)
if t.key == k
if isa(t.right,EmptyTree)
t = t.left
elseif isa(t.left,EmptyTree)
t = t.right
else
r = t.right
t = t.left
insert(t, r)
end
elseif k < t.key
t.left = del(t.left, k)
else
t.right = del(t.right, k)
end
t
end
insert(t::EmptyTree, r::TreeNode) = r
function insert(t::TreeNode, r::TreeNode)
if r.key < t.key
t.left = insert(t.left, r)
else
t.right = insert(t.right, r)
end
t
end