1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.server.core.avltree;
21
22
23
24
25
26
27
28
29 public class LinkedAvlNode<T>
30 {
31
32 T key;
33
34
35 LinkedAvlNode<T> left;
36
37
38 LinkedAvlNode<T> right;
39
40
41 LinkedAvlNode<T> next;
42
43
44 LinkedAvlNode<T> previous;
45
46 transient int depth;
47 transient int index;
48
49 boolean isLeft;
50 transient int height = 1;
51
52
53
54
55
56
57
58 public LinkedAvlNode( T theKey )
59 {
60 key = theKey;
61 left = null;
62 right = null;
63 }
64
65
66 public void setLeft( LinkedAvlNode<T> left )
67 {
68 this.left = left;
69 }
70
71
72 public void setRight( LinkedAvlNode<T> right )
73 {
74 this.right = right;
75 }
76
77
78 public LinkedAvlNode<T> getNext()
79 {
80 return next;
81 }
82
83
84 public LinkedAvlNode<T> getPrevious()
85 {
86 return previous;
87 }
88
89
90 public LinkedAvlNode<T> getLeft() {
91 return left;
92 }
93
94
95 public LinkedAvlNode<T> getRight() {
96 return right;
97 }
98
99 public T getKey() {
100 return key;
101 }
102
103 public boolean isLeaf()
104 {
105 return ( right == null && left == null );
106 }
107
108 public int getDepth() {
109 return depth;
110 }
111
112 public void setDepth( int depth ) {
113 this.depth = depth;
114 }
115
116 public int getHeight()
117 {
118 return height;
119 }
120
121
122 public void setNext( LinkedAvlNode<T> next )
123 {
124 this.next = next;
125 }
126
127
128 public void setPrevious( LinkedAvlNode<T> previous )
129 {
130 this.previous = previous;
131 }
132
133
134 public int computeHeight()
135 {
136
137 if(right == null && left == null)
138 {
139 height = 1;
140 return height;
141 }
142
143 int lh,rh;
144
145 if( isLeft )
146 {
147 lh = ( left == null ? -1 : left.computeHeight() );
148 rh = ( right == null ? -1 : right.getHeight() );
149 }
150 else
151 {
152 rh = ( right == null ? -1 : right.computeHeight() );
153 lh = ( left == null ? -1 : left.getHeight() );
154 }
155
156 height = 1 + Math.max( lh, rh );
157
158 return height;
159 }
160
161 public int getBalance()
162 {
163 int lh = ( left == null ? 0 : left.computeHeight() );
164 int rh = ( right == null ? 0 : right.computeHeight() );
165
166 return ( rh - lh );
167 }
168
169 public int getIndex()
170 {
171 return index;
172 }
173
174 public void setIndex(int index)
175 {
176 this.index = index;
177 }
178
179
180 @Override
181 public String toString() {
182 return "[" + key + "]";
183 }
184
185 }