API tools faq
paste
Advertisement
FNSY

Untitled

FNSY
Mar 23rd, 2017
120
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.21 KB | None | 0 0
raw download clone embed print report
  1. package eg.edu.alexu.csd.filestructure.avl;
  2.  
  3. public class AVLTree<T extends Comparable<T>> implements IAVLTree<T> {
  4. private Node<T> root;
  5. private boolean haveRoot;
  6.  
  7. public AVLTree() {
  8. haveRoot = false;
  9. root = new Node<T>(null, null);
  10. }
  11.  
  12. @Override
  13. public void insert(T key) {
  14.  
  15. Node<T> cursor = null; // y
  16. Node<T> current = root; // x
  17. Node<T> newNode = new Node<T>(key, null); // z
  18. while (current != null && current.getValue() != null) {
  19. cursor = current;
  20. try {
  21. if (newNode.getValue().compareTo(current.getValue()) < 0) {
  22. current = (Node<T>) current.getLeftChild();
  23. } else if (newNode.getValue().compareTo(current.getValue()) > 0) {
  24. current = (Node<T>) current.getRightChild();
  25. }
  26. } catch (NullPointerException ex) {
  27. break;
  28. }
  29. }
  30.  
  31. newNode.setParent(cursor);
  32. if (cursor == null) {
  33. root = newNode;
  34. } else if (newNode.getValue().compareTo(cursor.getValue()) < 0) {
  35. cursor.setLeftChild(newNode);
  36. newNode.setParent(cursor);
  37. reBalance((Node<T>) cursor.getLeftChild());
  38. } else if (newNode.getValue().compareTo(cursor.getValue()) > 0) {
  39. cursor.setRightChild(newNode);
  40. newNode.setParent(cursor);
  41. reBalance((Node<T>) cursor.getRightChild());
  42. }
  43.  
  44. }
  45.  
  46. public void reBalance(Node<T> t) {
  47. Node<T> parent = null; // up
  48. Node<T> check = t;
  49. Node<T> child = t;
  50. while (check.hasParent()) {
  51. // parent = (Node<T>) check.getParent();
  52. child = check;
  53. check = (Node<T>) check.getParent();
  54. int balanceFactor = check.getBalanceFactor();
  55. if (balanceFactor == 2) {
  56. if (check.getParent() != null)
  57. parent = (Node<T>) check.getParent();
  58. if (child.getBalanceFactor() == 1) {
  59. leftLeft(check, child, parent);
  60. break;
  61. } else if (child.getBalanceFactor() == -1) {
  62. leftRight(check, child, parent);
  63. break;
  64. }
  65. } else if (balanceFactor == -2) {
  66.  
  67. if (check.getParent() != null)
  68. parent = (Node<T>) check.getParent();
  69. if (child.getBalanceFactor() == 1) {
  70. rightLeft(check, child, parent);
  71. break;
  72. } else if (child.getBalanceFactor() == -1) {
  73. rightRight(check, child, parent);
  74. break;
  75.  
  76. }
  77. }
  78. }
  79. }
  80.  
  81. private void rightRight(Node<T> check, Node<T> child, Node<T> parent) {
  82. boolean right = false, noParent = false;
  83. check.setRightChild(null);
  84. child.setParent(null);
  85. if (parent == null)
  86. noParent = true;
  87. else if (parent.getValue().compareTo(check.getValue()) < 0)
  88. right = true;
  89.  
  90. if (!noParent) {
  91. if (right)
  92. parent.setRightChild(child);
  93. else
  94. parent.setLeftChild(child);
  95. child.setParent(parent);
  96. }
  97. if (child.hasLeftChild())
  98. check.setRightChild((Node<T>) child.getLeftChild());
  99. child.setLeftChild(check);
  100. check.setParent(child);
  101. if (check == root)
  102. root = child;
  103. }
  104.  
  105. private void rightLeft(Node<T> check, Node<T> child, Node<T> parent) {
  106. Node<T> n = (Node<T>) child.getLeftChild();
  107. boolean right = false, noParent = false;
  108. check.setRightChild(null);
  109. child.setLeftChild(null);
  110. if (parent == null)
  111. noParent = true;
  112. else if (parent.getValue().compareTo(check.getValue()) < 0)
  113. right = true;
  114.  
  115. if (!noParent) {
  116. if (right)
  117. parent.setRightChild(n);
  118. else
  119. parent.setLeftChild(n);
  120. n.setParent(parent);
  121. }
  122.  
  123. if (n.hasRightChild()) {
  124. ((Node<T>) n.getRightChild()).setParent(child);
  125. child.setLeftChild((Node<T>) n.getRightChild());
  126. }
  127. n.setRightChild(child);
  128. child.setParent(n);
  129. if (n.hasLeftChild()) {
  130. ((Node<T>) n.getLeftChild()).setParent(check);
  131. check.setRightChild((Node<T>) n.getLeftChild());
  132. }
  133. n.setLeftChild(check);
  134. check.setParent(n);
  135. if (check == root)
  136. root = n;
  137.  
  138. }
  139.  
  140. private void leftRight(Node<T> check, Node<T> child, Node<T> parent) {
  141. Node<T> n = (Node<T>) child.getRightChild();
  142. boolean right = false, noParent = false;
  143. check.setLeftChild(null);
  144. child.setRightChild(null);
  145. if (parent == null)
  146. noParent = true;
  147. else if (parent.getValue().compareTo(check.getValue()) < 0)
  148. right = true;
  149.  
  150. if (!noParent) {
  151. if (right)
  152. parent.setRightChild(n);
  153. else
  154. parent.setLeftChild(n);
  155. n.setParent(parent);
  156. }
  157.  
  158. if (n.hasRightChild()) {
  159. ((Node<T>) n.getRightChild()).setParent(check);
  160. check.setLeftChild((Node<T>) n.getRightChild());
  161. }
  162. n.setRightChild(check);
  163. check.setParent(n);
  164. if (n.hasLeftChild()) {
  165. ((Node<T>) n.getLeftChild()).setParent(child);
  166. child.setRightChild((Node<T>) n.getLeftChild());
  167. }
  168. n.setLeftChild(child);
  169. child.setParent(n);
  170. if (check == root)
  171. root = n;
  172.  
  173. }
  174.  
  175. private void leftLeft(Node<T> check, Node<T> child, Node<T> parent) {
  176. boolean right = false, noParent = false;
  177. check.setLeftChild(null);
  178. child.setParent(null);
  179. if (parent == null)
  180. noParent = true;
  181. else if (parent.getValue().compareTo(check.getValue()) < 0)
  182. right = true;
  183.  
  184. if (!noParent) {
  185. if (right)
  186. parent.setRightChild(child);
  187. else
  188. parent.setLeftChild(child);
  189. child.setParent(parent);
  190. }
  191. if (child.hasRightChild())
  192. check.setLeftChild((Node<T>) child.getRightChild());
  193. child.setRightChild(check);
  194. check.setParent(child);
  195. if (check == root)
  196. root = child;
  197. }
  198.  
  199. public Node<T> getNodes() {
  200. return this.root;
  201. }
  202.  
  203. public void inOrder(Node root) {
  204.  
  205. if (root != null) {
  206. inOrder((Node<T>) root.getLeftChild());
  207. System.out.println(root.getValue());
  208. inOrder((Node) root.getRightChild());
  209. }
  210. }
  211.  
  212. private Node<T> minimum(Node<T> node) {
  213. if (!node.hasLeftChild())
  214. return node;
  215. return minimum((Node<T>) node.getLeftChild());
  216.  
  217. }
  218.  
  219. // private Node<T> getMySuccessor(Node<T> node) {
  220. // if (node.hasRightChild()) {
  221. // return this.minimum((Node<T>) node.getRightChild());
  222. // } else {
  223. // Node<T> carry = (Node<T>) node.getParent();
  224. // while (carry != null && ((Node<T>) node).equals((Node<T>)
  225. // carry.getRightChild())) {
  226. // node = carry;
  227. // carry = (Node<T>) node.getParent();
  228. // }
  229. // return carry;
  230. // }
  231. //
  232. // }
  233.  
  234. private void deleteRebalance(Node<T> t) {
  235. Node<T> parent = null; // up
  236. Node<T> check = t;
  237. Node<T> child = t;
  238. while (check.hasParent()) {
  239. check = (Node<T>) check.getParent();
  240. int balanceFactor = check.getBalanceFactor();
  241. if (balanceFactor == 2) {
  242. if (check.getParent() != null)
  243. parent = (Node<T>) check.getParent();
  244. if (check.hasLeftChild()) {
  245. int leftChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  246. if (leftChildBF == 1) {
  247. child = (Node<T>) check.getLeftChild();
  248. leftLeft(check, child, parent);
  249. }
  250. } else if (check.hasRightChild()) {
  251. int rightChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  252. if (rightChildBF == -1) {
  253. child = (Node<T>) check.getRightChild();
  254. leftRight(check, child, parent);
  255. }
  256. }
  257. } else if (balanceFactor == -2) {
  258. if (check.getParent() != null)
  259. parent = (Node<T>) check.getParent();
  260. if (check.hasLeftChild()) {
  261. int leftChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  262. if (leftChildBF == -1) {
  263. child = (Node<T>) check.getRightChild();
  264. rightRight(check, child, parent);
  265. }
  266. } else if (check.hasRightChild()) {
  267. int rightChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  268. if (rightChildBF == 1) {
  269. child = (Node<T>) check.getLeftChild();
  270. rightLeft(check, child, parent);
  271. }
  272. }
  273. }
  274. }
  275. }
  276.  
  277. private void transplant(Node<T> toBeRemoved, Node<T> toBePlanted) {
  278.  
  279. Node<T> toBeRemovedParent = (Node<T>) toBeRemoved.getParent();
  280. if (!toBeRemoved.hasParent()) {
  281. root = toBePlanted;
  282. } else if (toBeRemoved.equals(toBeRemovedParent.getLeftChild())) {
  283. toBeRemovedParent.setLeftChild(toBePlanted);
  284. } else if (toBeRemoved.equals(toBeRemovedParent.getRightChild())) {
  285. toBeRemovedParent.setRightChild(toBePlanted);
  286. }
  287. toBeRemoved.setParent(null);
  288.  
  289. if (toBePlanted != null) {
  290. Node<T> toBePlantedParent = (Node<T>) toBePlanted.getParent();
  291. if (!toBeRemoved.equals(toBePlantedParent)) {
  292. if (toBePlantedParent.hasLeftChild() && toBePlantedParent.getLeftChild().equals(toBePlanted)) {
  293. toBePlantedParent.setLeftChild((Node) toBePlanted.getRightChild());
  294. if (toBePlanted.hasRightChild())
  295. ((Node) toBePlanted.getRightChild()).setParent(toBePlantedParent);
  296. } else if (toBePlantedParent.hasRightChild() && toBePlantedParent.getRightChild().equals(toBePlanted)) {
  297. toBePlantedParent.setRightChild(null);
  298. }
  299.  
  300. toBePlanted.setParent(toBeRemovedParent);
  301.  
  302. if (toBeRemoved.hasLeftChild()) {
  303. Node<T> leftOfToBeRemoved = ((Node<T>) toBeRemoved.getLeftChild());
  304. toBePlanted.setLeftChild(leftOfToBeRemoved);
  305. leftOfToBeRemoved.setParent(toBePlanted);
  306. toBeRemoved.setLeftChild(null);
  307.  
  308. }
  309.  
  310. if (toBeRemoved.hasRightChild()) {
  311. Node<T> rightOfToBeRemoved = ((Node<T>) toBeRemoved.getRightChild());
  312. toBePlanted.setRightChild(rightOfToBeRemoved);
  313. rightOfToBeRemoved.setParent(toBePlanted);
  314. toBeRemoved.setRightChild(null);
  315.  
  316. }
  317. } else if (toBeRemoved.equals(toBePlantedParent)) {
  318. toBePlanted.setParent(toBeRemovedParent);
  319. if (toBeRemoved.hasRightChild() && toBeRemoved.getRightChild().equals(toBePlanted)) {
  320. toBePlanted.setLeftChild((Node) toBeRemoved.getLeftChild());
  321. if (toBeRemoved.hasLeftChild())
  322. ((Node) toBePlanted.getLeftChild()).setParent(toBePlanted);
  323. } else if (toBeRemoved.hasLeftChild() && toBeRemoved.getLeftChild().equals(toBePlanted)) {
  324. toBePlanted.setRightChild((Node) toBeRemoved.getRightChild());
  325. if (toBeRemoved.hasRightChild())
  326. ((Node) toBePlanted.getRightChild()).setParent(toBePlanted);
  327. }
  328. }
  329. deleteRebalance(toBePlanted);
  330. }
  331. }
  332.  
  333. @Override
  334. public boolean delete(T key) {
  335. if (!search(key))
  336. return false;
  337.  
  338. Node<T> toBeDeleted = searchReturnsNode(key);
  339. if (!toBeDeleted.hasLeftChild()) {
  340. this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getRightChild());
  341. } else if (!toBeDeleted.hasRightChild()) {
  342. this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getLeftChild());
  343. } else {
  344. Node<T> node = minimum((Node<T>) toBeDeleted.getRightChild());
  345. this.transplant(toBeDeleted, node);
  346. }
  347.  
  348. return true;
  349. }
  350.  
  351. private Node<T> searchReturnsNode(T key, Node<T> node) {
  352. if (key.compareTo(node.getValue()) == 0)
  353. return node;
  354. if (key.compareTo(node.getValue()) < 0)
  355. return searchReturnsNode(key, (Node<T>) node.getLeftChild());
  356. else
  357. return searchReturnsNode(key, (Node<T>) node.getRightChild());
  358.  
  359. }
  360.  
  361. public Node<T> searchReturnsNode(T key) {
  362. return this.searchReturnsNode(key, root);
  363. }
  364.  
  365. private boolean search(T key, Node<T> node) {
  366. if (node != null) {
  367. if (key.compareTo(node.getValue()) == 0)
  368. return true;
  369. if (key.compareTo(node.getValue()) < 0)
  370. return search(key, (Node<T>) node.getLeftChild());
  371. else
  372. return search(key, (Node<T>) node.getRightChild());
  373. }
  374. return false;
  375.  
  376. }
  377.  
  378. @Override
  379. public boolean search(T key) {
  380. return this.search(key, root);
  381. }
  382.  
  383. @Override
  384. public int height() {
  385. if (root.getValue() == null) {
  386. return -1;
  387. } else {
  388. return Math.max(root.getLeftHeight(), root.getLeftHeight());
  389. }
  390. }
  391.  
  392. @Override
  393. public INode<T> getTree() {
  394. return root;
  395. }
  396.  
  397. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!