Posted By

obrienm on 08/29/14


Tagged


Versions (?)

Editor Trees - Node Class


 / Published in: Java
 

Data Structures & Algorithm Analysis Project

  1. package editortrees;
  2.  
  3.  
  4. /**
  5.  * Creates and edits Nodes for Editor Trees.
  6.  *
  7.  * @author burchtm, havensd, obrienm Created April 2014.
  8.  */
  9. public class Node {
  10. public static final Node NULL_NODE = new NullNode();
  11.  
  12. enum Code {
  13. SAME, LEFT, RIGHT
  14. };
  15.  
  16. char element;
  17. Node left, right;
  18. Node parent; // subtrees
  19. int rank; // inorder position of this node within its own subtree.
  20. int height;
  21. int size;
  22. Code balance;
  23.  
  24. /**
  25. * Constructs a node with the given element and parent.
  26. *
  27. * @param e
  28. * @param parent
  29. */
  30. public Node(char e, Node parent) {
  31. this.element = e;
  32. this.left = NULL_NODE;
  33. this.right = NULL_NODE;
  34. this.balance = Code.SAME;
  35. this.parent = parent;
  36. this.height = 0;
  37. this.size = 1;
  38. this.rank = 0;
  39. }
  40.  
  41. /**
  42. * Constructs a node with the given element.
  43. *
  44. * @param e
  45. */
  46. public Node(char e) {
  47. this.element = e;
  48. this.left = NULL_NODE;
  49. this.right = NULL_NODE;
  50. this.balance = Code.SAME;
  51. this.parent = NULL_NODE;
  52. this.height = 0;
  53. this.size = 1;
  54. this.rank = 0;
  55. }
  56.  
  57. /**
  58. * Constructs a NULL_NODE.
  59. *
  60. */
  61. public Node() {
  62. this.element = Character.MIN_VALUE;
  63. this.rank = Integer.MIN_VALUE;
  64. this.size = 0;
  65. this.balance = Code.SAME;
  66. this.height = -1;
  67. this.left = null;
  68. this.right = null;
  69. this.parent = NULL_NODE;
  70. }
  71.  
  72. public String toString() {
  73. if (this == NULL_NODE) {
  74. return "";
  75. }
  76. return this.left.toString() + this.element + this.right.toString();
  77. }
  78.  
  79. /**
  80. * Returns the height of the node's subtree
  81. *
  82. * @return height of the node's subtree
  83. */
  84. public int height() {
  85. return this.height;
  86. }
  87.  
  88. /**
  89. * Returns the size of the node
  90. *
  91. * @return size of the node
  92. */
  93. public int size() {
  94. return this.size;
  95. }
  96.  
  97. /**
  98. * Returns a Node at the given index position.
  99. *
  100. * @param pos
  101. * @return Node at given position
  102. */
  103. public Node get(int pos) {
  104. if (pos > this.rank) { // go right
  105. return this.right.get(pos - rank - 1);
  106. } else if (pos < this.rank) { // go left
  107. return this.left.get(pos);
  108. } else {
  109. return this;
  110. }
  111. }
  112.  
  113. /**
  114. *
  115. * @param length
  116. * @return the string starting at the given position with the given length
  117. */
  118. public String getString(int length) {
  119. if (length == 0) {
  120. return "";
  121. }
  122. Node current = this;
  123. String temp = current.element + ""; // get current character
  124. if (current.right != NULL_NODE) { // current has a right child
  125. current = current.right;
  126. // Iterate all the way left after going right to inorder sucessor
  127. while (current.left != NULL_NODE) {
  128. current = current.left;
  129. }
  130. return temp + current.getString(length - 1);
  131. } else { // current does not have a right child
  132. // Get back up to the node that was branched off of
  133. while (current.parent.right == current) {
  134. current = current.parent;
  135. }
  136. return temp + current.parent.getString(length - 1);
  137. }
  138. }
  139.  
  140. /**
  141. * Adds a new node with a given char element at the given index position to
  142. * the Editor Tree.
  143. *
  144. * @param c
  145. * @param pos
  146. * @param e
  147. */
  148. public void add(char c, int pos, EditTree e) {
  149. if (pos > this.rank) { // go right
  150. if (this.right == NULL_NODE) { // Make a right child
  151. this.right = new Node(c, this);
  152. } else { // Recurse on the right child
  153. this.right.add(c, pos - rank - 1, e);
  154. }
  155. int rotate = needsRotation();
  156. switch (rotate) {
  157. case (-2):
  158. doubleLeftRotate(this, this.right, this.right.left, e);
  159. break;
  160. case (-1):
  161. singleLeftRotate(this, this.right, e);
  162. break;
  163. case (0):
  164. setFields();
  165. break;
  166. case (1):
  167. singleRightRotate(this, this.left, e);
  168. break;
  169. case (2):
  170. doubleRightRotate(this, this.left, this.left.right, e);
  171. break;
  172. }
  173. } else { // go left
  174. if (this.left == NULL_NODE) { // Make a left child
  175. this.left = new Node(c, this);
  176. } else {
  177. this.left.add(c, pos, e); // Recurse on left child
  178. }
  179. int rotate = needsRotation();
  180. switch (rotate) {
  181. case (-2):
  182. doubleLeftRotate(this, this.right, this.right.left, e);
  183. break;
  184. case (-1):
  185. singleLeftRotate(this, this.right, e);
  186. break;
  187. case (0):
  188. setFields();
  189. break;
  190. case (1):
  191. singleRightRotate(this, this.left, e);
  192. break;
  193. case (2):
  194. doubleRightRotate(this, this.left, this.left.right, e);
  195. break;
  196. }
  197. }
  198. }
  199.  
  200. /**
  201. * Sets the fields after there is no rotate.
  202. */
  203. private void setFields() {
  204. this.setHeight();
  205. this.setSize();
  206. this.setBalance();
  207. this.setRank();
  208. }
  209.  
  210. /**
  211. * Sets the balance of a node.
  212. */
  213. private void setBalance() {
  214. if (this.left.height > this.right.height) {
  215. this.balance = Code.LEFT;
  216. } else if (this.left.height < this.right.height) {
  217. this.balance = Code.RIGHT;
  218. } else {
  219. this.balance = Code.SAME;
  220. }
  221. }
  222.  
  223. /**
  224. * Sets the height of a node.
  225. */
  226. private void setHeight() {
  227. if (this == NULL_NODE) {
  228. this.height = -1;
  229. }
  230. this.height = Math.max(this.left.height, this.right.height) + 1;
  231. }
  232.  
  233. /**
  234. * Sets the size of a node.
  235. */
  236. private void setSize() {
  237. this.size = this.left.size + this.right.size + 1;
  238. }
  239.  
  240. /**
  241. * Sets the rank of a node.
  242. */
  243. private void setRank() {
  244. this.rank = this.left.size;
  245. }
  246.  
  247. /**
  248. * Performs a double right rotate at the given node. (Performs single left
  249. * on child and then single right on parent.)
  250. *
  251. * @param parent
  252. * @param child
  253. * @param grandchild
  254. * @param e
  255. */
  256. private void doubleRightRotate(Node parent, Node child, Node grandchild,
  257. EditTree e) {
  258. singleLeftRotate(child, grandchild, e);
  259. singleRightRotate(parent, child, e);
  260.  
  261. // Set the fields on the nodes after rotation.
  262. grandchild.setFields();
  263. child.setFields();
  264. parent.setFields();
  265. }
  266.  
  267. /**
  268. * Performs a single right rotate at the given node.
  269. *
  270. * @param parent
  271. * @param child
  272. * @param e
  273. */
  274. private void singleRightRotate(Node parent, Node child, EditTree e) {
  275. // Swap elements in parent and child
  276. char parentElement = parent.element;
  277. parent.element = child.element;
  278. child.element = parentElement;
  279. // Swing child over to the right
  280. Node childSubtree = child.right;
  281. child.right = parent.right;
  282. child.right.parent = child;
  283. // Suck up child's left to its parent's left
  284. parent.left = child.left;
  285. child.left.parent = parent;
  286. parent.right = child;
  287. child.left = childSubtree;
  288.  
  289. // Set fields on the appropriate nodes after rotation and increase total
  290. // rotation count
  291. child.setFields();
  292. parent.setFields();
  293. e.totalRotationCount++;
  294. }
  295.  
  296. /**
  297. * Performs a single left rotate at the given node.
  298. *
  299. * @param parent
  300. * @param child
  301. * @param e
  302. */
  303. private void singleLeftRotate(Node parent, Node child, EditTree e) {
  304. // Swaps elements in the parent and child
  305. char parentElement = parent.element;
  306. parent.element = child.element;
  307. child.element = parentElement;
  308. // Swing child over to the left
  309. Node childSubtree = child.left;
  310. child.left = parent.left;
  311. child.left.parent = child;
  312. // Suck up child's right to its parent's right
  313. parent.right = child.right;
  314. child.right.parent = parent;
  315. parent.left = child;
  316. child.right = childSubtree;
  317.  
  318. // Set fields on the appropriate nodes after rotation and increase total
  319. // rotation count
  320. child.setFields();
  321. parent.setFields();
  322. e.totalRotationCount++;
  323. }
  324.  
  325. /**
  326. * Performs a double left rotate at the given node. (Performs single right
  327. * on child and then single left on parent.)
  328. *
  329. * @param parent
  330. * @param child
  331. * @param grandchild
  332. * @param e
  333. */
  334. private void doubleLeftRotate(Node parent, Node child, Node grandchild,
  335. EditTree e) {
  336. singleRightRotate(child, grandchild, e);
  337. singleLeftRotate(parent, child, e);
  338.  
  339. // Set the fields on the nodes after rotation.
  340. grandchild.setFields();
  341. child.setFields();
  342. parent.setFields();
  343. }
  344.  
  345. /**
  346. * Determines what kind of rotation is needed, if any.
  347. *
  348. * @return an integer indicating which rotation is needed.
  349. */
  350. private int needsRotation() {
  351. if (this.left.height - this.right.height > 1) {
  352. // rotate right
  353. if (this.left.balance == Code.LEFT) {
  354. return 1; // single
  355. } else {
  356. return 2; // double
  357. }
  358. } else if (this.right.height - this.left.height > 1) {
  359. // rotate left
  360. if (this.right.balance == Code.RIGHT) {
  361. return -1; // single
  362. } else {
  363. return -2; // double
  364. }
  365. } else {
  366. return 0; // No rotation needed.
  367. }
  368. }
  369.  
  370. /**
  371. * Creates a copy of the given current node from an original Editor Tree.
  372. *
  373. * @param e
  374. * @param eCurrent
  375. */
  376. public void editTreeCopy(Node eCurrent) {
  377. // Sets the fields of the current node
  378. this.element = eCurrent.element;
  379. this.balance = eCurrent.balance;
  380. this.height = eCurrent.height;
  381. this.rank = eCurrent.rank;
  382. this.size = eCurrent.size;
  383. // Recurse on the left
  384. if (eCurrent.left != Node.NULL_NODE) {
  385. this.left = new Node();
  386. this.left.editTreeCopy(eCurrent.left);
  387. } else {
  388. this.left = Node.NULL_NODE;
  389. }
  390. // Recurse on the right
  391. if (eCurrent.right != Node.NULL_NODE) {
  392. this.right = new Node();
  393. this.right.editTreeCopy(eCurrent.right);
  394. } else {
  395. this.right = Node.NULL_NODE;
  396. }
  397. // Set the parent fields
  398. this.left.parent = this;
  399. this.right.parent = this;
  400. }
  401.  
  402. /**
  403. * Deletes the given node from the tree.
  404. *
  405. * @param e
  406. * @return the element of the deleted node
  407. */
  408. public char delete(EditTree e) {
  409. char element = this.element;
  410. if (this.left == NULL_NODE && this.right == NULL_NODE) { // no children
  411.  
  412. if (this.parent.left == this) {// node is on left
  413. this.parent.left = NULL_NODE;
  414. this.parent.left.parent = this.parent;
  415. } else if (this.parent.right == this) { // node is on right
  416. this.parent.right = NULL_NODE;
  417. this.parent.right.parent = this.parent;
  418. }
  419. } else if (this.left == NULL_NODE ^ this.right == NULL_NODE) { // one
  420.  
  421. if (this.left == NULL_NODE) { // only right child
  422. if (this.parent == NULL_NODE) {
  423. e.root = this.right;
  424. } else if (this.parent.left == this) { // Node is on the left
  425. this.parent.left = this.right;
  426. } else { // Node is on the right
  427. this.parent.right = this.right;
  428. }
  429. } else { // only left child
  430. if (this.parent == NULL_NODE) {
  431. e.root = this.left;
  432. } else if (this.parent.left == this) { // Node is on the left
  433. this.parent.left = this.left;
  434. } else { // Node is on the right
  435. this.parent.right = this.left;
  436. }
  437. }
  438. } else { // two children
  439. // Finds inorder successor
  440. Node temp = this.right;
  441. while (temp.left != NULL_NODE) {
  442. temp = temp.left;
  443. }
  444. this.element = temp.element;
  445. if (this.right.left == NULL_NODE) {
  446. this.right = this.right.right;
  447. this.right.parent = this;
  448. } else {
  449. temp.parent.left = temp.right;
  450. temp.right.parent = temp.parent;
  451. }
  452. temp.backTrack(e);
  453. }
  454.  
  455. // Set all the required fields and returns element
  456. e.setTreeSize();
  457. this.setFields();
  458. this.backTrack(e);
  459. return element;
  460. }
  461.  
  462. /**
  463. * Backtracks up the tree, rotating if necessary.
  464. *
  465. * @param e
  466. */
  467. private void backTrack(EditTree e) {
  468. if (this == NULL_NODE) {
  469. return;
  470. }
  471. int rotate = needsRotation();
  472. switch (rotate) {
  473. case (-2):
  474. doubleLeftRotate(this, this.right, this.right.left, e);
  475. break;
  476. case (-1):
  477. singleLeftRotate(this, this.right, e);
  478. break;
  479. case (0):
  480. setFields();
  481. break;
  482. case (1):
  483. singleRightRotate(this, this.left, e);
  484. break;
  485. case (2):
  486. doubleRightRotate(this, this.left, this.left.right, e);
  487. break;
  488. }
  489. this.parent.backTrack(e);
  490. }
  491.  
  492. /**
  493. * Builds a tree from the given string.
  494. *
  495. * @param s
  496. */
  497. public void buildStringTree(String s) {
  498. // Recurse on the left
  499. if (!(s.length() == 1)) {
  500. this.left = new Node('x');
  501. this.left.parent = this;
  502. this.left.buildStringTree(s.substring(0, s.length() / 2));
  503. }
  504.  
  505. // Set the current node's element
  506. this.element = s.charAt(s.length() / 2);
  507.  
  508. // Recurse on the right
  509. if (!(s.length() == 1 || s.charAt(s.length() - 1) == s.charAt(s
  510. .length() / 2))) {
  511. this.right = new Node('x');
  512. this.right.parent = this;
  513. this.right.buildStringTree(s.substring(s.length() / 2 + 1,
  514. s.length()));
  515. }
  516.  
  517. // Set fields
  518. this.setFields();
  519. }
  520.  
  521. /**
  522. * Concatenates a Tree with the given root "otherRoot" at the given
  523. * otherNode to the original tree.
  524. *
  525. * @param otherRoot
  526. * @param otherNode
  527. */
  528. public void concatenate(Node otherRoot, Node otherNode) {
  529. if (this.height > otherRoot.height()) {
  530. // Adjusts the height field for nodes and the recursion goes down
  531. // the original tree.
  532. if (this.balance == Code.LEFT) {
  533. this.height -= 2;
  534. } else {
  535. this.height--;
  536. }
  537. // Recurses down the original tree.
  538. this.right.concatenate(otherRoot, otherNode);
  539. } else {
  540. // Case for if we are at the root of the original tree
  541. if (this.parent == NULL_NODE) {
  542. otherNode.parent.left = NULL_NODE;
  543. } else {
  544. // Sets the right node of the parent to the node where
  545. // concatenation happens. Removes otherNode from subtree and set
  546. // otherNode's parent.
  547. this.parent.right = otherNode;
  548. otherNode.parent.left = NULL_NODE;
  549. otherNode.parent = this.parent;
  550. }
  551. // Checks if the otherNode was the root and sets that node's right
  552. // and parent if not.
  553. if (otherRoot != otherNode) {
  554. otherNode.right = otherRoot;
  555. otherRoot.parent = otherNode;
  556. }
  557. otherNode.left = this;
  558. this.parent = otherNode;
  559. // Sets the new fields of the otherNode, otherRoot, and the balance
  560. // code of the otherNode's new parent.
  561. otherNode.setFields();
  562. otherRoot.setFields();
  563. otherNode.parent.setBalance();
  564. }
  565. }
  566.  
  567. }

Report this snippet  

You need to login to post a comment.