API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Feb 19th, 2017
65
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 32.41 KB | None | 0 0
raw download clone embed print report
  1. /*
  2.  
  3. A generic AVL Tree implementation.
  4.  
  5. The AVLTree and associated classes are below the Test_AVLTree class.
  6. This version has been tested for edge cases, but no optimization
  7. effort has been made.
  8.  
  9. Tim Bartlett, Feb 19th, 2017.
  10.  
  11. */
  12.  
  13. import java.util.Random;
  14. import java.math.BigInteger;
  15.  
  16. /*
  17. Main test class
  18.  
  19. Test of Generic AVL Tree using Strings as data and BigIntegers as keys.
  20. A unique number is assigned to each String by the Converter class, and
  21. this number is used as the key. A higher key indicates a further place in
  22. Alphabetical order, so the result is that the Strings remain in alphabetical
  23. order and search time is limited: You could use the Converter on a String
  24. to get a key for avltree.getData(key), which searches the tree for this key
  25. and returns a reference to the data.
  26.  
  27. This could easily be extended so that the String is some other Object
  28. with a field that would could be used in the Converter method to generate
  29. unique keys.
  30.  
  31. */
  32. public class Test_AVLTree{
  33. static final char[] ALPHABET =
  34. {'A','B','C','D','E','F','G','H','I','J','K','L','M',
  35. 'N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
  36. static final int CHARACTER_LIM = 2;
  37. static final int NUM_INSERTS = 25;
  38. static final int NUM_REMOVES = 25;
  39.  
  40. public static void main(String args[]){
  41. //handle arguments
  42. Long seed = (new Random()).nextLong();
  43. if(args.length != 0){
  44. try{
  45. seed = Long.parseLong(args[0]);
  46. }catch(Exception ex){
  47. System.out.println("Bad seed arg");
  48. return;
  49. }
  50. }
  51.  
  52. Random rand = new Random(seed);
  53. System.out.println("\nseed (use as argument to repeat): " +
  54. seed + "\n");
  55.  
  56. /* class Converter
  57. Converts our random strings into unique BigIntegers, such that
  58. a greater number indicates a further place in the order
  59. defined by the characters in char[] order.
  60. in our case, this is the char[] ALPHABET above.
  61. */
  62. class Converter implements DataToKeyConverter<BigInteger,String>{
  63. char[] order = ALPHABET;
  64. int longest = CHARACTER_LIM;
  65.  
  66. public BigInteger dataToKey(String data){
  67. BigInteger n = new BigInteger("0");
  68. BigInteger n2;
  69. //for every char in string
  70. for(int j = 0, jLim = data.length(); j < jLim; j++){
  71. //for every char in order[]
  72. for(int k = 0, kLim = order.length; k < kLim; k++){
  73. //if current char equals char in order
  74. if(data.charAt(j) == order[k]){
  75. //add to n according to
  76. // n += (k+1)(order.length^(longest - j);
  77. // so the first character has the most weight
  78. // (little endian)
  79. n2 = new BigInteger(order.length + "");
  80. n2 = n2.pow(longest - j);
  81. n = n.add(
  82. n2.multiply(new BigInteger((k + 1) + "")));
  83. break;
  84. }
  85. }
  86. }
  87. return n;
  88. }
  89. }
  90. //construct an avltree using a new Converter as the parameter
  91. // This Converter will now be used every insert() and remove()
  92. AVLTree<BigInteger, String> avltree = new AVLTree<>(new Converter());
  93.  
  94. String[] insertedData = new String[NUM_INSERTS];
  95. String s = "";
  96. String data;
  97.  
  98. long t = System.currentTimeMillis();
  99.  
  100. for(int i = 0; i < NUM_INSERTS; i++){
  101. data = "";
  102. for(int j = 0; j < CHARACTER_LIM; j++){
  103. data += ALPHABET[rand.nextInt(ALPHABET.length)];
  104. }
  105. try{
  106. avltree.insert(data);
  107. }catch(Exception ex){
  108. //System.out.println(ex);
  109. }
  110. insertedData[i] = data;
  111. s += data += " ";
  112. }
  113. //System.out.println("Inserted in this order:\n" + s);
  114.  
  115. System.out.println(
  116. NUM_INSERTS + " inserts took " +
  117. (System.currentTimeMillis() - t) + "ms");
  118.  
  119. /*
  120. System.out.println(
  121. "\nInorder after insert() calls (dots indicate level):\n"+
  122. avltree.toString_InorderDetailed() + "\n"+
  123. "Inorder, displaying data:\n"+
  124. avltree.toString_InorderData() + "\n");
  125. */
  126.  
  127. s = "";
  128. t = System.currentTimeMillis();
  129. for(int i = 0; i < NUM_REMOVES; i++){
  130. data = insertedData[rand.nextInt(insertedData.length)];
  131. try{
  132. avltree.remove(data);
  133. }catch(Exception ex){
  134. //System.out.println(ex);
  135. }
  136. s += data += " ";
  137. }
  138. //System.out.println("\nRemoved in this order:\n" + s);
  139.  
  140. System.out.println(
  141. NUM_REMOVES + " removes took " +
  142. (System.currentTimeMillis() - t) + "ms");
  143.  
  144. /*
  145. System.out.println(
  146. "\nInorder after remove() calls (dots indicate level):\n" +
  147. avltree.toString_InorderDetailed() + "\n"+
  148. "Inorder, displaying data:\n"+
  149. avltree.toString_InorderData());
  150. */
  151.  
  152. System.out.println(avltree.toString_InorderDataDetailed());
  153.  
  154. }
  155.  
  156. }
  157.  
  158. /*
  159. This is the interface for data to key conversions. A class
  160. implementing this is required in the AVLTree constructor
  161. */
  162. interface DataToKeyConverter<K extends Comparable<K>, E>{
  163. public K dataToKey(E data);
  164. }
  165.  
  166. /*
  167. This node used in the AVLTree
  168. */
  169. class AVLNode<K extends Comparable<K>, E>{
  170. E data;
  171. K key;
  172. AVLNode<K,E> parent;
  173. AVLNode<K,E> left;
  174. AVLNode<K,E> right;
  175.  
  176. public AVLNode(){
  177. data = null;
  178. key = null;
  179. parent = null;
  180. left = null;
  181. right = null;
  182. }
  183.  
  184. public void setData(E data){this.data = data;}
  185. public void setKey(K key){this.key = key;}
  186. public void setParent(AVLNode<K,E> parent){this.parent = parent;}
  187. public void setLeft(AVLNode<K,E> left){this.left = left;}
  188. public void setRight(AVLNode<K,E> right){this.right = right;}
  189.  
  190. public E getData(){return data;}
  191. public K getKey(){return key;}
  192. public AVLNode<K,E> getParent(){return parent;}
  193. public AVLNode<K,E> getLeft(){return left;}
  194. public AVLNode<K,E> getRight(){return right;}
  195.  
  196. }
  197.  
  198. /*
  199. The AVLTree
  200.  
  201. public methods:
  202. insert(E data), remove(E data), getData(K key) and many toString()
  203. methods which are defined at the end of the class.
  204.  
  205. */
  206. class AVLTree<K extends Comparable<K>,E>{
  207. public AVLNode<K,E> root;
  208.  
  209. DataToKeyConverter<K,E> convert;
  210.  
  211. public AVLTree(DataToKeyConverter<K,E> convert){
  212. this.convert = convert;
  213. root = null;
  214. }
  215.  
  216. public void insert(E data) throws IndexOutOfBoundsException{
  217. AVLNode<K,E> node_new = new AVLNode<K,E>();
  218.  
  219. K key = convert.dataToKey(data);
  220. node_new.setKey(key);
  221. node_new.setData(data);
  222.  
  223. //if tree is empty
  224. if(root == null){
  225. root = node_new;
  226. return;
  227. }
  228.  
  229. //find position and insert new node
  230. AVLNode<K,E> node_temp = root;
  231. AVLNode<K,E> node_tempParent = null;
  232. boolean isDeepenedLeft = false;
  233. while(node_temp != null){
  234. if(node_temp.getKey().compareTo(key) < 0){
  235. if(node_temp.getRight() != null){
  236. node_tempParent = node_temp;
  237. node_temp = node_temp.getRight();
  238. }else{
  239. node_new.setParent(node_temp);
  240. node_temp.setRight(node_new);
  241. isDeepenedLeft = false;
  242. break;
  243. }
  244. }else if(node_temp.getKey().compareTo(key) > 0){
  245. if(node_temp.getLeft() != null){
  246. node_tempParent = node_temp;
  247. node_temp = node_temp.getLeft();
  248. }else{
  249. node_new.setParent(node_temp);
  250. node_temp.setLeft(node_new);
  251. isDeepenedLeft = true;
  252. break;
  253. }
  254. }else{
  255. //duplicate
  256. throw new IndexOutOfBoundsException(
  257. "ERR: insert(" + data + "): duplicate value");
  258. }
  259. }
  260.  
  261.  
  262. balance(node_new);
  263.  
  264. }
  265.  
  266. public void remove(E data) throws IndexOutOfBoundsException{
  267. K key = convert.dataToKey(data);
  268.  
  269. //search for node with matching key, node_temp
  270. AVLNode<K,E> node_temp = root;
  271. K temp_key;
  272. while(node_temp != null){
  273. temp_key = node_temp.getKey();
  274. if(temp_key.compareTo(key) > 0){
  275. node_temp = node_temp.getLeft();
  276. }else if(temp_key.compareTo(key) < 0){
  277. node_temp = node_temp.getRight();
  278. }else{
  279. //equal
  280. break;
  281. }
  282. }
  283. if(node_temp == null){
  284. throw new IndexOutOfBoundsException(
  285. "ERR: remove(" + data + "): no match");
  286. }
  287.  
  288. //reserve pointers of node_temp
  289. AVLNode<K,E> node_tL = node_temp.getLeft();
  290. AVLNode<K,E> node_tR = node_temp.getRight();
  291. AVLNode<K,E> node_tP = node_temp.getParent();
  292. AVLNode<K,E> node_toBalance = node_tP;
  293. AVLNode<K,E> node_tC = null; //temp Closest
  294.  
  295. //is the node_temp higher or lower than parent
  296. boolean isLeftOfParent = false;
  297. if(node_temp.getParent() != null &&
  298. node_temp.getParent().getKey().compareTo(node_temp.getKey())>0){
  299. isLeftOfParent = true;
  300. }
  301.  
  302. //four main cases, depending on number of branches from node_temp
  303. if(node_tL == null && node_tR == null){ //if no branches
  304. if(node_tP == null){
  305. root = null;
  306. throw new IndexOutOfBoundsException(
  307. "ERR: remove(" + data + "): all nodes removed");
  308. }
  309. if(isLeftOfParent){
  310. node_tP.setLeft(null);
  311. }else{
  312. node_tP.setRight(null);
  313. }
  314. }else if(node_tL == null){ //if one branch on right
  315. node_tR.setParent(node_tP);
  316. if(isLeftOfParent){
  317. if(node_tP != null) node_tP.setLeft(node_tR);
  318. else root = node_tR;
  319. }else{
  320. if(node_tP != null) node_tP.setRight(node_tR);
  321. else root = node_tR;
  322. }
  323. }else if(node_tR == null){ //if one branch on left
  324. node_tL.setParent(node_tP);
  325. if(isLeftOfParent){
  326. if(node_tP != null) node_tP.setLeft(node_tL);
  327. else root = node_tL;
  328. }else{
  329. if(node_tP != null) node_tP.setRight(node_tL);
  330. else root = node_tL;
  331. }
  332. }else{ //both branches exist
  333. int depthL = getDepth(node_tL);
  334. int depthR = getDepth(node_tR);
  335.  
  336. //two cases for if replacement is on left or right
  337. if(depthL > depthR){ //take replacement from deeper, left side
  338.  
  339. //search for closest to node_temp
  340. AVLNode<K,E> node = node_tL;
  341. while(node != null){
  342. node_tC = node;
  343. node = node.getRight();
  344. }
  345.  
  346. //if closest is not just one below
  347. if(node_tC.getParent() != node_temp){
  348. node_toBalance = node_tC.getParent();
  349. node_tC.getParent().setRight(node_tC.getLeft());
  350. if(node_tC.getLeft() != null){
  351. node_tC.getLeft().setParent(node_tC.getParent());
  352. }
  353. }else{ //closest is just one below
  354. if(node_tP != null){
  355. if(isLeftOfParent){
  356. node_tP.setLeft(node_tC);
  357. }else{
  358. node_tP.setRight(node_tC);
  359. }
  360. }
  361. if(node_tL != null) node_tL.setParent(node_tC);
  362. if(node_tR != null) node_tR.setParent(node_tC);
  363. }
  364.  
  365. }else{ //take replacement from right
  366.  
  367. //search for closest to node_temp
  368. AVLNode<K,E> node = node_tR;
  369. while(node != null){
  370. node_tC = node;
  371. node = node.getLeft();
  372. }
  373.  
  374. //if closest is not just one below
  375. if(node_tC.getParent() != node_temp){
  376. node_toBalance = node_tC.getParent();
  377. node_tC.getParent().setLeft(node_tC.getRight());
  378. if(node_tC.getRight() != null){
  379. node_tC.getRight().setParent(node_tC.getParent());
  380. }
  381. }else{ //closest is just one below
  382. if(node_tP != null){
  383. if(isLeftOfParent){
  384. node_tP.setLeft(node_tC);
  385. }else{
  386. node_tP.setRight(node_tC);
  387. }
  388. }
  389. if(node_tL != null) node_tL.setParent(node_tC);
  390. if(node_tR != null) node_tR.setParent(node_tC);
  391. }
  392. }
  393.  
  394. //set node_tC.left to that of removed node
  395. if(node_tC == node_tL){ //if they're the same
  396. if(node_tC.getLeft() != null){
  397. node_tC.getLeft().setParent(node_tC);
  398. }
  399. node_tC.setLeft(node_tC.getLeft());
  400. }else{
  401. node_tC.setLeft(node_tL);
  402. }
  403.  
  404. //set parent for node left of removed node
  405. if(node_tL != null){
  406. node_tL.setParent(node_tC);
  407. }
  408.  
  409. //set node_tC.right to that of removed node
  410. if(node_tC == node_tR){ //if they're the same
  411. if(node_tC.getRight() != null){
  412. node_tC.getRight().setParent(node_tC);
  413. }
  414. node_tC.setRight(node_tC.getRight());
  415. }else{
  416. node_tC.setRight(node_tR);
  417. }
  418.  
  419. //set parent for node right of removed node
  420. if(node_tR != null){
  421. node_tR.setParent(node_tC);
  422. }
  423. node_tC.setParent(node_tP);
  424.  
  425. //set the left or right of removed node, if it's higher or lower
  426. if(node_tP == null){
  427. root = node_tC;
  428. }else{
  429. if(isLeftOfParent){
  430. node_tP.setLeft(node_tC);
  431. }else{
  432. node_tP.setRight(node_tC);
  433. }
  434. }
  435. }
  436.  
  437.  
  438. balance(node_toBalance);
  439.  
  440. }
  441.  
  442. public E getData(K key){
  443.  
  444. AVLNode<K,E> node_temp = root;
  445. while(node_temp != null){
  446. if(node_temp.getKey().compareTo(key) < 0){
  447. node_temp = node_temp.getRight();
  448. }else if(node_temp.getKey().compareTo(key) > 0){
  449. node_temp = node_temp.getLeft();
  450. }else{
  451. //equal
  452. return node_temp.getData();
  453. }
  454. }
  455. //no match
  456. return null;
  457. }
  458.  
  459. int getDepth(AVLNode<K,E> avlnode){
  460. return getDepth(avlnode,0);
  461. }
  462. int getDepth(AVLNode<K,E> avlnode, int depthAbove){
  463. if(avlnode == null) return depthAbove;
  464.  
  465. AVLNode<K,E> avlnodeR = avlnode.getRight();
  466. AVLNode<K,E> avlnodeL = avlnode.getLeft();
  467.  
  468. int depthRight = getDepth(avlnodeR, depthAbove);
  469. int depthLeft = getDepth(avlnodeL, depthAbove);
  470.  
  471. if(depthRight > depthLeft) return depthRight + 1;
  472. else return depthLeft + 1;
  473. }
  474.  
  475.  
  476. //This function begins at the given node_temp and
  477. // checks the balance at every level up to the root,
  478. // calling rotate functions as necessary.
  479. private void balance(AVLNode<K,E> node_temp){
  480.  
  481. /*
  482. tp
  483. / \
  484. L R
  485. / \ / \
  486. LL LR RL RR
  487.  
  488. */
  489.  
  490. //check given node for balance, continue to parent if balanced
  491. AVLNode<K,E> node_tempL, node_tempR;
  492. int depthL, depthR, depthLL, depthLR, depthRL, depthRR;
  493. while(node_temp != null){
  494.  
  495. //depths from branches
  496. depthL = getDepth(node_temp.getLeft());
  497. depthR = getDepth(node_temp.getRight());
  498. //reserve temp left and right pointers
  499. node_tempL = node_temp.getLeft();
  500. node_tempR = node_temp.getRight();
  501.  
  502. //if left branch exists, get its depths
  503. if(node_tempL != null){
  504. depthLL = getDepth(node_tempL.getLeft());
  505. depthLR = getDepth(node_tempL.getRight());
  506. }else{
  507. depthLL = -1;
  508. depthLR = -1;
  509. }
  510.  
  511. //if right branch exists, get its depths
  512. if(node_tempR != null){
  513. depthRL = getDepth(node_tempR.getLeft());
  514. depthRR = getDepth(node_tempR.getRight());
  515. }else{
  516. depthRL = -1;
  517. depthRR = -1;
  518. }
  519.  
  520. //continue to parent node if balanced
  521. switch(depthL - depthR){
  522. case 0:
  523. case -1:
  524. case 1:
  525. node_temp = node_temp.getParent();
  526. continue;
  527. }
  528.  
  529. //4 cases of rotations, based on depths of branches
  530. if(depthR > depthL && depthRR > depthRL){ //if longer R & RR
  531.  
  532. rotationL(node_temp);
  533.  
  534. //check blanace of lengthened side
  535. balance(node_temp);
  536.  
  537. break;
  538.  
  539. }else if(depthR > depthL && depthRL > depthRR){ //if longer R & RL
  540.  
  541. rotationLR(node_temp);
  542.  
  543. //check balance of both sides
  544. balance(node_temp);
  545. balance(node_tempR);
  546.  
  547. break;
  548.  
  549. }else if(depthL > depthR && depthLL > depthLR){ //if longer L & LL
  550.  
  551. rotationR(node_temp);
  552.  
  553. //check blanace of lengthened side
  554. balance(node_temp);
  555.  
  556. break;
  557.  
  558. }else if(depthL > depthR && depthLR > depthLL){ //if longer L & LR
  559.  
  560. rotationRL(node_temp);
  561.  
  562. //check balance of both sides
  563. balance(node_temp);
  564. balance(node_tempL);
  565.  
  566. break;
  567.  
  568. }
  569.  
  570. //if codes makes it here, continue to parent node
  571. node_temp = node_temp.getParent();
  572.  
  573. }//EO while(node_temp != null)
  574. }
  575.  
  576. void rotationL(AVLNode<K,E> node_root){
  577.  
  578. /*
  579. Pr
  580. |
  581. Rt
  582. / \
  583. l1 r1
  584. / \
  585. l2 r2
  586. / \
  587. l3 r3
  588. */
  589.  
  590. AVLNode<K,E> node_parent = node_root.getParent();
  591. AVLNode<K,E> node_r1 = node_root.getRight();
  592. AVLNode<K,E> node_r2 = node_r1.getRight();
  593. AVLNode<K,E> node_r3 = node_r2.getRight();
  594. AVLNode<K,E> node_l1 = node_root.getLeft();
  595. AVLNode<K,E> node_l2 = node_r1.getLeft();
  596. AVLNode<K,E> node_l3 = node_r2.getLeft();
  597.  
  598. if(node_root == this.root){
  599. root = node_r1;
  600. }
  601.  
  602. /*
  603. Pr
  604. |
  605. r1
  606. / \
  607. Rt r2
  608. / \ / \
  609. l1 l2 l3 r3
  610. */
  611.  
  612. boolean isRootLeftOfParent = false;
  613. if(node_parent != null && node_parent.getLeft() == node_root){
  614. isRootLeftOfParent = true;
  615. }
  616. if(node_parent != null){
  617. if(isRootLeftOfParent){
  618. node_parent.setLeft(node_r1);
  619. }else{
  620. node_parent.setRight(node_r1);
  621. }
  622. }
  623. if(node_r1 != null){
  624. node_r1.setParent(node_parent);
  625. node_r1.setLeft(node_root);
  626. node_r1.setRight(node_r2);
  627. }
  628. if(node_root != null){
  629. node_root.setParent(node_r1);
  630. //node_l1 already on left
  631. node_root.setRight(node_l2);
  632. }
  633. if(node_r2 != null){
  634. node_r2.setParent(node_r1);
  635. //node_l3 already on left
  636. //node_r3 already on right
  637.  
  638. }
  639. if(node_l1 != null) node_l1.setParent(node_root);
  640. if(node_l2 != null) node_l2.setParent(node_root);
  641. if(node_l3 != null) node_l3.setParent(node_r2);
  642. if(node_r3 != null) node_r3.setParent(node_r2);
  643.  
  644. }
  645.  
  646. void rotationLR(AVLNode<K,E> node_root){
  647. /*
  648. Pr
  649. |
  650. Rt
  651. / \
  652. l1 r1
  653. / \
  654. l2 r2
  655. / \
  656. l3 r3
  657. */
  658.  
  659. AVLNode<K,E> node_parent = node_root.getParent();
  660. AVLNode<K,E> node_l1 = node_root.getLeft();
  661. AVLNode<K,E> node_r1 = node_root.getRight();
  662. AVLNode<K,E> node_l2 = node_r1.getLeft();
  663. AVLNode<K,E> node_r2 = node_r1.getRight();
  664. AVLNode<K,E> node_l3 = node_l2.getLeft();
  665. AVLNode<K,E> node_r3 = node_l2.getRight();
  666.  
  667. if(node_root == this.root){
  668. root = node_l2;
  669. }
  670.  
  671. /*
  672. Pr
  673. |
  674. l2
  675. / \
  676. Rt r1
  677. / \ / \
  678. l1 l3 r3 r2
  679. */
  680. boolean isRootLeftOfParent = false;
  681. if(node_parent != null && node_parent.getLeft() == node_root){
  682. isRootLeftOfParent = true;
  683. }
  684. if(node_parent != null){
  685. if(isRootLeftOfParent){
  686. node_parent.setLeft(node_l2);
  687. }else{
  688. node_parent.setRight(node_l2);
  689. }
  690. }
  691. if(node_l2 != null){
  692. node_l2.setParent(node_parent);
  693. node_l2.setLeft(node_root);
  694. node_l2.setRight(node_r1);
  695. }
  696. if(node_root != null){
  697. node_root.setParent(node_l2);
  698. //node_l1 already on left
  699. node_root.setRight(node_l3);
  700. }
  701. if(node_r1 != null){
  702. node_r1.setParent(node_l2);
  703. node_r1.setLeft(node_r3);
  704. //node_r2 already on right
  705.  
  706. }
  707. if(node_l1 != null) node_l1.setParent(node_root);
  708. if(node_l3 != null) node_l3.setParent(node_root);
  709. if(node_r3 != null) node_r3.setParent(node_r1);
  710. if(node_r2 != null) node_r2.setParent(node_r1);
  711.  
  712. }
  713.  
  714. void rotationR(AVLNode<K,E> node_root){
  715. /*
  716. Pr
  717. |
  718. Rt
  719. / \
  720. l1 r1
  721. / \
  722. l2 r2
  723. / \
  724. l3 r3
  725. */
  726.  
  727. AVLNode<K,E> node_parent = node_root.getParent();
  728. AVLNode<K,E> node_l1 = node_root.getLeft();
  729. AVLNode<K,E> node_r1 = node_root.getRight();
  730. AVLNode<K,E> node_l2 = node_l1.getLeft();
  731. AVLNode<K,E> node_r2 = node_l1.getRight();
  732. AVLNode<K,E> node_l3 = node_l2.getLeft();
  733. AVLNode<K,E> node_r3 = node_l2.getRight();
  734.  
  735. if(node_root == this.root){
  736. root = node_l1;
  737. }
  738.  
  739. /*
  740. Pr
  741. |
  742. l1
  743. / \
  744. l2 Rt
  745. / \ / \
  746. l3 r3 r2 r1
  747. */
  748. boolean isRootLeftOfParent = false;
  749. if(node_parent != null && node_parent.getLeft() == node_root){
  750. isRootLeftOfParent = true;
  751. }
  752. if(node_parent != null){
  753. if(isRootLeftOfParent){
  754. node_parent.setLeft(node_l1);
  755. }else{
  756. node_parent.setRight(node_l1);
  757. }
  758. }
  759. if(node_l1 != null){
  760. node_l1.setParent(node_parent);
  761. node_l1.setLeft(node_l2);
  762. node_l1.setRight(node_root);
  763. }
  764. if(node_l2 != null){
  765. node_l2.setParent(node_l1);
  766. //node_l1 already on left
  767. //node_r3 already on right
  768. }
  769. if(node_root != null){
  770. node_root.setParent(node_l1);
  771. node_root.setLeft(node_r2);
  772. //node_r1 already on right
  773.  
  774. }
  775. if(node_l3 != null) node_l3.setParent(node_l2);
  776. if(node_r3 != null) node_r3.setParent(node_l2);
  777. if(node_r2 != null) node_r2.setParent(node_root);
  778. if(node_r1 != null) node_r1.setParent(node_root);
  779.  
  780. }
  781.  
  782. void rotationRL(AVLNode<K,E> node_root){
  783. /*
  784. Pt
  785. |
  786. Rt
  787. / \
  788. l1 r1
  789. / \
  790. l2 r2
  791. / \
  792. l3 r3
  793. */
  794.  
  795. AVLNode<K,E> node_parent = node_root.getParent();
  796. AVLNode<K,E> node_l1 = node_root.getLeft();
  797. AVLNode<K,E> node_r1 = node_root.getRight();
  798. AVLNode<K,E> node_l2 = node_l1.getLeft();
  799. AVLNode<K,E> node_r2 = node_l1.getRight();
  800. AVLNode<K,E> node_l3 = node_r2.getLeft();
  801. AVLNode<K,E> node_r3 = node_r2.getRight();
  802.  
  803. if(node_root == this.root){
  804. root = node_r2;
  805. }
  806.  
  807. /*
  808. Pt
  809. |
  810. r2
  811. / \
  812. l1 Rt
  813. / \ / \
  814. l2 l3 r3 r1
  815. */
  816. boolean isRootLeftOfParent = false;
  817. if(node_parent != null && node_parent.getLeft() == node_root){
  818. isRootLeftOfParent = true;
  819. }
  820. if(node_parent != null){
  821. if(isRootLeftOfParent){
  822. node_parent.setLeft(node_r2);
  823. }else{
  824. node_parent.setRight(node_r2);
  825. }
  826. }
  827. if(node_r2 != null){
  828. node_r2.setParent(node_parent);
  829. node_r2.setLeft(node_l1);
  830. node_r2.setRight(node_root);
  831. }
  832. if(node_l1 != null){
  833. node_l1.setParent(node_r2);
  834. //node_l2 already on left
  835. node_l1.setRight(node_l3);
  836. }
  837. if(node_root != null){
  838. node_root.setParent(node_r2);
  839. node_root.setLeft(node_r3);
  840. //node_r1 already on right
  841.  
  842. }
  843. if(node_l2 != null) node_l2.setParent(node_l1);
  844. if(node_l3 != null) node_l3.setParent(node_l1);
  845. if(node_r3 != null) node_r3.setParent(node_root);
  846. if(node_r1 != null) node_r1.setParent(node_root);
  847.  
  848. }
  849.  
  850. public String toString_InorderDetailed(){
  851. String r_s = "[ ";
  852. int count = 0;
  853.  
  854. r_s += inorderDetailed(root, count);
  855.  
  856. r_s += "]";
  857. return r_s;
  858. }
  859. private String inorderDetailed(AVLNode<K,E> node_ref, int count){
  860. String r_s = "";
  861.  
  862. String dots = "";
  863. for(int i = 0; i < count; i++){
  864. dots += '.';
  865. }
  866.  
  867. if(node_ref != null){
  868. count++;
  869. r_s += inorderDetailed(node_ref.getLeft(), count);
  870. if(dots.equals("")){
  871. r_s += "<" + node_ref.getKey() + "> ";
  872. }else{
  873. r_s += dots + node_ref.getKey() + " ";
  874. }
  875. r_s += inorderDetailed(node_ref.getRight(), count);
  876. }
  877.  
  878. return r_s;
  879. }
  880.  
  881. public String toString_PreorderDetailed(){
  882. String r_s = "[ ";
  883. int count = 0;
  884.  
  885. r_s += preorderDetailed(root, count);
  886.  
  887. r_s += "]";
  888. return r_s;
  889. }
  890. private String preorderDetailed(AVLNode<K,E> node_ref, int count){
  891. String r_s = "";
  892.  
  893. String dots = "";
  894. for(int i = 0; i < count; i++){
  895. dots += '.';
  896. }
  897.  
  898. if(node_ref != null){
  899. count++;
  900. if(dots.equals("")){
  901. r_s += "<" + node_ref.getKey() + "> ";
  902. }else{
  903. r_s += dots + node_ref.getKey() + " ";
  904. }
  905. r_s += preorderDetailed(node_ref.getLeft(), count);
  906. r_s += preorderDetailed(node_ref.getRight(), count);
  907. }
  908.  
  909. return r_s;
  910. }
  911.  
  912. public String toString_PostorderDetailed(){
  913. String r_s = "[ ";
  914. int count = 0;
  915.  
  916. r_s += postorderDetailed(root, count);
  917.  
  918. r_s += "]";
  919. return r_s;
  920. }
  921. private String postorderDetailed(AVLNode<K,E> node_ref, int count){
  922. String r_s = "";
  923.  
  924. String dots = "";
  925. for(int i = 0; i < count; i++){
  926. dots += '.';
  927. }
  928.  
  929. if(node_ref != null){
  930. count++;
  931. r_s += postorderDetailed(node_ref.getLeft(), count);
  932. r_s += postorderDetailed(node_ref.getRight(), count);
  933. if(dots.equals("")){
  934. r_s += "<" + node_ref.getKey() + "> ";
  935. }else{
  936. r_s += dots + node_ref.getKey() + " ";
  937. }
  938. }
  939.  
  940. return r_s;
  941. }
  942.  
  943. public String toString_InorderData(){
  944. String r_s = "[ ";
  945. int count = 0;
  946.  
  947. r_s += inorderData(root);
  948.  
  949. r_s += "]";
  950. return r_s;
  951. }
  952. private String inorderData(AVLNode<K,E> node_ref){
  953. String r_s = "";
  954.  
  955. if(node_ref != null){
  956. r_s += inorderData(node_ref.getLeft());
  957. r_s += node_ref.getData() + " ";
  958. r_s += inorderData(node_ref.getRight());
  959. }
  960.  
  961. return r_s;
  962. }
  963.  
  964. public String toString_InorderDataDetailed(){
  965. String r_s = "[ ";
  966. int count = 0;
  967.  
  968. r_s += inorderDataDetailed(root, count);
  969.  
  970. r_s += "]";
  971. return r_s;
  972. }
  973. private String inorderDataDetailed(AVLNode<K,E> node_ref, int count){
  974. String r_s = "";
  975.  
  976. String dots = "";
  977. for(int i = 0; i < count; i++){
  978. dots += '.';
  979. }
  980.  
  981. if(node_ref != null){
  982. count++;
  983. r_s += inorderDataDetailed(node_ref.getLeft(), count);
  984. if(dots.equals("")){
  985. r_s += "<" + node_ref.getData() + "> ";
  986. }else{
  987. r_s += dots + node_ref.getData() + " ";
  988. }
  989. r_s += inorderDataDetailed(node_ref.getRight(), count);
  990. }
  991.  
  992. return r_s;
  993. }
  994.  
  995. public String toString_Inorder(){
  996. String r_s = "[ ";
  997.  
  998. r_s += inorder(root);
  999.  
  1000. r_s += "]";
  1001. return r_s;
  1002. }
  1003. private String inorder(AVLNode<K,E> node_ref){
  1004. String r_s = "";
  1005.  
  1006. if(node_ref != null){
  1007. r_s += inorder(node_ref.getLeft());
  1008. r_s += node_ref.getKey() + " ";
  1009. r_s += inorder(node_ref.getRight());
  1010. }
  1011.  
  1012. return r_s;
  1013. }
  1014.  
  1015. public String toString_Preorder(){
  1016. String r_s = "[ ";
  1017.  
  1018. r_s += preorder(root);
  1019.  
  1020. r_s += "]";
  1021. return r_s;
  1022. }
  1023. private String preorder(AVLNode<K,E> node_ref){
  1024. String r_s = "";
  1025.  
  1026. if(node_ref != null){
  1027. r_s += node_ref.getKey() + " ";
  1028. r_s += preorder(node_ref.getLeft());
  1029. r_s += preorder(node_ref.getRight());
  1030. }
  1031.  
  1032. return r_s;
  1033. }
  1034.  
  1035. public String toString_Postorder(){
  1036. String r_s = "[ ";
  1037.  
  1038. r_s += postorder(root);
  1039.  
  1040. r_s += "]";
  1041. return r_s;
  1042. }
  1043. private String postorder(AVLNode<K,E> node_ref){
  1044. String r_s = "";
  1045.  
  1046. if(node_ref != null){
  1047. r_s += postorder(node_ref.getLeft());
  1048. r_s += postorder(node_ref.getRight());
  1049. r_s += node_ref.getKey() + " ";
  1050. }
  1051.  
  1052. return r_s;
  1053. }
  1054.  
  1055. }
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!