Docjar: A Java Source and Docuemnt Enginecom.*    java.*    javax.*    org.*    all    new    plug-in

Quick Search    Search Deep

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