API tools faq
paste
Advertisement
FNSY

Untitled

FNSY
Mar 23rd, 2017
121
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.95 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. if (n.hasLeftChild()) {
  129. ((Node<T>) n.getLeftChild()).setParent(check);
  130. check.setRightChild((Node<T>) n.getLeftChild());
  131. }
  132. n.setLeftChild(check);
  133. if (check == root)
  134. root = n;
  135.  
  136. }
  137.  
  138. private void leftRight(Node<T> check, Node<T> child, Node<T> parent) {
  139. Node<T> n = (Node<T>) child.getRightChild();
  140. boolean right = false, noParent = false;
  141. check.setLeftChild(null);
  142. child.setRightChild(null);
  143. if (parent == null)
  144. noParent = true;
  145. else if (parent.getValue().compareTo(check.getValue()) < 0)
  146. right = true;
  147.  
  148. if (!noParent) {
  149. if (right)
  150. parent.setRightChild(n);
  151. else
  152. parent.setLeftChild(n);
  153. n.setParent(parent);
  154. }
  155.  
  156. if (n.hasRightChild()) {
  157. ((Node<T>) n.getRightChild()).setParent(check);
  158. check.setLeftChild((Node<T>) n.getRightChild());
  159. }
  160. n.setRightChild(check);
  161. check.setParent(n);
  162. if (n.hasLeftChild()) {
  163. ((Node<T>) n.getLeftChild()).setParent(child);
  164. child.setRightChild((Node<T>) n.getLeftChild());
  165. }
  166. n.setLeftChild(child);
  167. child.setParent(n);
  168. if (check == root)
  169. root = n;
  170.  
  171. }
  172.  
  173. private void leftLeft(Node<T> check, Node<T> child, Node<T> parent) {
  174. boolean right = false, noParent = false;
  175. check.setLeftChild(null);
  176. child.setParent(null);
  177. if (parent == null)
  178. noParent = true;
  179. else if (parent.getValue().compareTo(check.getValue()) < 0)
  180. right = true;
  181.  
  182. if (!noParent) {
  183. if (right)
  184. parent.setRightChild(child);
  185. else
  186. parent.setLeftChild(child);
  187. child.setParent(parent);
  188. }
  189. if (child.hasRightChild())
  190. check.setLeftChild((Node<T>) child.getRightChild());
  191. child.setRightChild(check);
  192. check.setParent(child);
  193. if (check == root)
  194. root = child;
  195. }
  196.  
  197. public Node<T> getNodes() {
  198. return this.root;
  199. }
  200.  
  201. public void inOrder(Node root) {
  202.  
  203. if (root != null) {
  204. inOrder((Node<T>) root.getLeftChild());
  205. System.out.println(root.getValue());
  206. inOrder((Node) root.getRightChild());
  207. }
  208. }
  209.  
  210. private Node<T> minimum(Node<T> node) {
  211. if (!node.hasLeftChild())
  212. return node;
  213. return minimum((Node<T>) node.getLeftChild());
  214.  
  215. }
  216.  
  217. // private Node<T> getMySuccessor(Node<T> node) {
  218. // if (node.hasRightChild()) {
  219. // return this.minimum((Node<T>) node.getRightChild());
  220. // } else {
  221. // Node<T> carry = (Node<T>) node.getParent();
  222. // while (carry != null && ((Node<T>) node).equals((Node<T>)
  223. // carry.getRightChild())) {
  224. // node = carry;
  225. // carry = (Node<T>) node.getParent();
  226. // }
  227. // return carry;
  228. // }
  229. //
  230. // }
  231.  
  232. private void deleteRebalance(Node<T> t) {
  233. Node<T> parent = null; // up
  234. Node<T> check = t;
  235. Node<T> child = t;
  236. while (check.hasParent()) {
  237. check = (Node<T>) check.getParent();
  238. int balanceFactor = check.getBalanceFactor();
  239. if (balanceFactor == 2) {
  240. if (check.getParent() != null)
  241. parent = (Node<T>) check.getParent();
  242. if (check.hasLeftChild()) {
  243. int leftChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  244. if (leftChildBF == 1) {
  245. child = (Node<T>) check.getLeftChild();
  246. leftLeft(check, child, parent);
  247. }
  248. } else if (check.hasRightChild()) {
  249. int rightChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  250. if (rightChildBF == -1) {
  251. child = (Node<T>) check.getRightChild();
  252. leftRight(check, child, parent);
  253. }
  254. }
  255. } else if (balanceFactor == -2) {
  256. if (check.getParent() != null)
  257. parent = (Node<T>) check.getParent();
  258. if (check.hasLeftChild()) {
  259. int leftChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  260. if (leftChildBF == -1) {
  261. child = (Node<T>) check.getRightChild();
  262. rightRight(check, child, parent);
  263. }
  264. } else if (check.hasRightChild()) {
  265. int rightChildBF = ((Node) check.getLeftChild()).getBalanceFactor();
  266. if (rightChildBF == 1) {
  267. child = (Node<T>) check.getLeftChild();
  268. rightLeft(check, child, parent);
  269. }
  270. }
  271. }
  272. }
  273. }
  274.  
  275. private void transplant(Node<T> toBeRemoved, Node<T> toBePlanted) {
  276.  
  277. Node<T> toBeRemovedParent = (Node<T>) toBeRemoved.getParent();
  278. if (!toBeRemoved.hasParent()) {
  279. root = toBePlanted;
  280. } else if (toBeRemoved.equals(toBeRemovedParent.getLeftChild())) {
  281. toBeRemovedParent.setLeftChild(toBePlanted);
  282. } else {
  283. toBeRemovedParent.setRightChild(toBePlanted);
  284. }
  285. toBeRemoved.setParent(null);
  286. if (toBePlanted != null) {
  287. Node<T> toBePlantedParent = (Node<T>) toBePlanted.getParent();
  288.  
  289. // change
  290. if (!toBeRemoved.equals(toBePlantedParent)) {
  291. if (toBePlantedParent.hasLeftChild() && toBePlantedParent.getLeftChild().equals(toBePlanted)) {
  292. toBePlantedParent.setLeftChild((Node) toBePlanted.getRightChild());
  293. if (toBePlanted.hasRightChild())
  294. ((Node) toBePlanted.getRightChild()).setParent(toBePlantedParent);
  295. } else if (toBePlantedParent.hasRightChild() && toBePlantedParent.getRightChild().equals(toBePlanted)) {
  296. toBePlantedParent.setRightChild(null);
  297. }
  298.  
  299. toBePlanted.setParent(toBeRemovedParent);
  300.  
  301. if (toBeRemoved.hasLeftChild()) {
  302. Node<T> leftOfToBeRemoved = ((Node<T>) toBeRemoved.getLeftChild());
  303. toBePlanted.setLeftChild(leftOfToBeRemoved);
  304. leftOfToBeRemoved.setParent(toBePlanted);
  305. toBeRemoved.setLeftChild(null);
  306.  
  307. }
  308.  
  309. if (toBeRemoved.hasRightChild()) {
  310. Node<T> rightOfToBeRemoved = ((Node<T>) toBeRemoved.getRightChild());
  311. toBePlanted.setRightChild(rightOfToBeRemoved);
  312. rightOfToBeRemoved.setParent(toBePlanted);
  313. toBeRemoved.setRightChild(null);
  314.  
  315. }
  316. } else {
  317.  
  318. toBePlanted.setParent(toBeRemovedParent);
  319.  
  320. if (toBeRemoved.getRightChild().equals(toBePlanted)) {
  321. toBePlanted.setLeftChild((Node) toBeRemoved.getLeftChild());
  322. ((Node) toBePlanted.getLeftChild()).setParent(toBePlanted);
  323. } else if (toBeRemoved.getLeftChild().equals(toBePlanted)) {
  324. toBePlanted.setRightChild((Node) toBeRemoved.getRightChild());
  325. ((Node) toBePlanted.getRightChild()).setParent(toBePlanted);
  326. }
  327. }
  328.  
  329. deleteRebalance(toBePlanted);
  330.  
  331. }
  332.  
  333. }
  334.  
  335. @Override
  336. public boolean delete(T key) {
  337. if (!search(key))
  338. return false;
  339.  
  340. Node<T> toBeDeleted = searchReturnsNode(key);
  341. if (!toBeDeleted.hasLeftChild()) {
  342. this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getRightChild());
  343. } else if (!toBeDeleted.hasRightChild()) {
  344. this.transplant(toBeDeleted, (Node<T>) toBeDeleted.getLeftChild());
  345. } else {
  346. Node<T> node = minimum((Node<T>) toBeDeleted.getRightChild());
  347. this.transplant(toBeDeleted, node);
  348. }
  349.  
  350. return true;
  351. }
  352.  
  353. private Node<T> searchReturnsNode(T key, Node<T> node) {
  354. if (key.compareTo(node.getValue()) == 0)
  355. return node;
  356. if (key.compareTo(node.getValue()) < 0)
  357. return searchReturnsNode(key, (Node<T>) node.getLeftChild());
  358. else
  359. return searchReturnsNode(key, (Node<T>) node.getRightChild());
  360.  
  361. }
  362.  
  363. public Node<T> searchReturnsNode(T key) {
  364. return this.searchReturnsNode(key, root);
  365. }
  366.  
  367. private boolean search(T key, Node<T> node) {
  368. if (node != null) {
  369. if (key.compareTo(node.getValue()) == 0)
  370. return true;
  371. if (key.compareTo(node.getValue()) < 0)
  372. return search(key, (Node<T>) node.getLeftChild());
  373. else
  374. return search(key, (Node<T>) node.getRightChild());
  375. }
  376. return false;
  377.  
  378. }
  379.  
  380. @Override
  381. public boolean search(T key) {
  382. return this.search(key, root);
  383. }
  384.  
  385. @Override
  386. public int height() {
  387. if (root.getValue() == null) {
  388. return -1;
  389. } else {
  390. return Math.max(root.getLeftHeight(), root.getLeftHeight());
  391. }
  392. }
  393.  
  394. @Override
  395. public INode<T> getTree() {
  396. return root;
  397. }
  398.  
  399. }
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!