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

Report this snippet  

You need to login to post a comment.