Source code: Freenet/support/BinaryTree.java
1 package Freenet.support;
2 /*
3 This code is part of the Java Adaptive Network Client by Ian Clarke.
4 It is distributed under the GNU Public Licence (GPL) version 2. See
5 http://www.gnu.org/ for further details of the GPL.
6
7 Explanation of Code Versions:
8 0.0.0 = Initial Description
9 0.0.1 = API Specified
10 0.x (x>0) = Partial Implementation
11 x.0 (x>0) = Operational
12
13 Requires Classes: Class (version)
14 Class (version)
15 ...
16 */
17
18 /**
19 * This class represents a simple binary search tree.
20 *
21 * @version 1.0
22 * @author <A HREF="mailto:I.Clarke@strs.co.uk">Ian Clarke</A>
23 **/
24
25 public class BinaryTree
26 {
27 public String toString()
28 {
29 return tree.toString();
30 }
31
32 public Branch tree = null;
33 protected int size = 0;
34
35 public void put(long key, Object value)
36 {
37 size++;
38 if (tree == null)
39 {
40 tree = new Branch(key, value, null);
41 }
42 else
43 {
44 tree.put(key, value);
45 }
46 }
47
48 public void delete(long key)
49 {
50 Branch x,y,z;
51 z=tree.get(key);
52 if ((z.left == null) || (z.right == null))
53 y=z;
54 else
55 y=z.successor();
56 if (y.left != null)
57 x = y.left;
58 else
59 x = y.right;
60 if (x != null)
61 x.parent = y.parent;
62 if (y.parent == null)
63 tree = x;
64 else
65 if (y == y.parent.left)
66 y.parent.left = x;
67 else
68 y.parent.right = x;
69 if (y != z)
70 {
71 z.key = y.key;
72 z.value = y.value;
73 }
74 }
75
76 public Object get(long key)
77 {
78 if (tree == null)
79 return null;
80 else
81 {
82 Branch r = tree.get(key);
83 if (r == null)
84 return null;
85 else
86 return r.value;
87 }
88 }
89 }
90
91 class Branch
92 {
93 public Branch left = null;
94 public Branch right = null;
95 public Branch parent;
96 public long key;
97 public Object value;
98
99 public Branch(long key, Object value, Branch parent)
100 {
101 this.key = key;
102 this.value = value;
103 this.parent = parent;
104 }
105
106 public String toString()
107 {
108 return "(Key:"+key+" Left:"+left+" Right:"+right+")";
109 }
110
111 public void put (long key, Object value)
112 {
113 if (key<this.key)
114 {
115 if (left == null)
116 {
117 left=new Branch(key,value,this);
118 }
119 else
120 left.put(key, value);
121 }
122 else
123 {
124 if (right == null)
125 right=new Branch(key, value, this);
126 else
127 right.put(key, value);
128 }
129 }
130
131 public Branch get(long key)
132 {
133 if (this.key == key)
134 return this;
135 else
136 {
137 if (key < this.key)
138 {
139 if (left == null)
140 return null;
141 else
142 return left.get(key);
143 }
144 else
145 {
146 if (right == null)
147 return null;
148 else
149 return right.get(key);
150 }
151 }
152 }
153
154 public Branch successor()
155 {
156 if (right != null)
157 return right.minimum();
158 else
159 {
160 Branch y = this;
161 while((y != null) && (y.parent.left != this))
162 {
163 y = y.parent;
164 }
165 if (y == null)
166 return null;
167 else
168 return y.parent;
169 }
170 }
171
172 public Branch minimum()
173 {
174 if (left == null)
175 return this;
176 else
177 return left.minimum();
178 }
179 }
180
181
182
183
184