MarouaneTheViper

Untitled

Apr 22nd, 2019
76
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package Main;
  2.  
  3. import static java.lang.Math.pow;
  4.  
  5.  
  6. public class RB_Tree {
  7. public Node root;
  8. public static final boolean RED = true;
  9. public static final boolean BLACK = false;
  10.  
  11. public boolean isRed(Node x){
  12. if(x==null)
  13. return false;
  14. return x.color==RED;
  15. }
  16.  
  17. public int size(Node x){
  18. if(x==null)
  19. return 0;
  20. return x.size;
  21. }
  22.  
  23. public boolean isEmpty(){
  24. return root==null;
  25. }
  26.  
  27. public float generateKey(String val)
  28. {
  29. float key = 0;
  30. val = val.toUpperCase();
  31. char[] arr = val.toCharArray();
  32. for(int i=0; i<val.length();i++)
  33. {
  34. System.out.println(arr[i]);
  35. key += arr[i]/pow(10,2*i);
  36. }
  37. System.out.println(key);
  38. return key;
  39. }
  40.  
  41. public Node insert(Node h,int key,String val){
  42. if(h==null)
  43. return new Node(key,val,RED);
  44.  
  45. int cmp= h.compareTo(key);
  46.  
  47. if(cmp<0)
  48. h.left=insert(h.left,key,val);
  49. else if(cmp>0)
  50. h.right = insert(h.right, key, val);
  51. else
  52. <<<<<<< HEAD
  53. h.val=val;
  54. return h;
  55. }
  56. public void delete(float key) {
  57. if (0.0f == key) throw new IllegalArgumentException("argument to delete() is null");
  58. if (!contains(key)) return;
  59.  
  60. // if both children of root are black, set root to red
  61. if (!isRed(root.left) && !isRed(root.right))
  62. root.color = RED;
  63.  
  64. root = delete(root, key);
  65. if (!isEmpty()) root.color = BLACK;
  66. // assert check();
  67. }
  68.  
  69. private Node delete(Node h, float key) {
  70. if (h.compareTo(key) < 0) {
  71. if (!isRed(h.left) && !isRed(h.left.left))
  72. h = moveRedLeft(h);
  73. h.left = delete(h.left, key);
  74. }
  75. else {
  76. if (isRed(h.left))
  77. h = rotateRight(h);
  78. if (h.compareTo(key) == 0 && (h.right == null))
  79. return null;
  80. if (!isRed(h.right) && !isRed(h.right.left))
  81. h = moveRedRight(h);
  82. if (h.compareTo(key) == 0) {
  83. Node x = min(h.right);
  84. h.key = x.key;
  85. h.val = x.val;
  86. h.right = deleteMin(h.right);
  87. }
  88. else h.right = delete(h.right, key);
  89. }
  90. return balance(h);
  91. }
  92.  
  93. private Node balance(Node h) {
  94.  
  95. if (isRed(h.right)) h = rotateLeft(h);
  96. if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
  97. if (isRed(h.left) && isRed(h.right)) flipColors(h);
  98.  
  99. =======
  100. h.val=val;
  101. if(isRed(h.right)&&!isRed(h.left)){
  102. h=rotateLeft(h);
  103. }
  104. if(isRed(h.left)&&isRed(h.left.left)){
  105. h=rotateRight(h);
  106. }
  107. if(isRed(h.left)&&isRed(h.right)){
  108. flipColors(h);
  109. }
  110. >>>>>>> parent of 256eb3e... maroooo
  111. h.size = size(h.left) + size(h.right) + 1;
  112.  
  113. return h;
  114. }
  115. <<<<<<< HEAD
  116.  
  117. private Node rotateRight(Node h) {
  118. Node x = h.left;
  119. h.left = x.right;
  120. x.right = h;
  121. x.color = x.right.color;
  122. x.right.color = RED;
  123. x.size = h.size;
  124. h.size = size(h.left) + size(h.right) + 1;
  125. =======
  126. public Node rotateLeft(Node h){
  127. Node x=h.right;
  128. h.right=x.left;
  129. x.left=h;
  130. x.color=x.left.color;
  131. x.left.color=RED;
  132. x.size=h.size;
  133. h.size=size(h.left)+size(h.right)+1;
  134. >>>>>>> parent of 256eb3e... maroooo
  135. return x;
  136. }
  137. public Node rotateRight(Node h){
  138. Node x=h.left;
  139. h.left=x.right;
  140. x.right=h;
  141. x.color=x.right.color;
  142. x.right.color=RED;
  143. x.size=h.size;
  144. h.size=size(h.left)+size(h.right);
  145. return x;
  146. }
  147. public void flipColors(Node h){
  148. h.color=!h.color;
  149. h.left.color=!h.left.color;
  150. h.right.color=!h.right.color;
  151. }
  152.  
  153. public void insert(String val){
  154. if(val==null){
  155. return;
  156. }
  157. float key = generateKey(val);
  158. root=insert(root,key,val);
  159. root.color=BLACK;
  160. }
  161.  
  162. public Node insert(Node h, float key, String val){
  163. if(h==null)
  164. return new Node(key,val,RED);
  165.  
  166. int cmp= h.compareTo(key);
  167.  
  168. if(cmp<0)
  169. h.left=insert(h.left,key,val);
  170. else if(cmp>0)
  171. h.right = insert(h.right, key, val);
  172. else
  173. h.val=val;
  174. return h;
  175. <<<<<<< HEAD
  176. }
  177. public boolean isEmpty() {
  178. return root == null;
  179. }
  180. public void deleteMin() {
  181. if (isEmpty()) throw new NoSuchElementException("BST underflow");
  182. if (!isRed(root.left) && !isRed(root.right))
  183. root.color = RED;
  184.  
  185. root = deleteMin(root);
  186. if (!isEmpty()) root.color = BLACK;
  187. }
  188. private Node deleteMin(Node h) {
  189. if (h.left == null)
  190. return null;
  191.  
  192. if (!isRed(h.left) && !isRed(h.left.left))
  193. h = moveRedLeft(h);
  194.  
  195. h.left = deleteMin(h.left);
  196. return balance(h);
  197. }
  198. public void deleteMax() {
  199. if (isEmpty()) throw new NoSuchElementException("BST underflow");
  200. if (!isRed(root.left) && !isRed(root.right))
  201. root.color = RED;
  202.  
  203. root = deleteMax(root);
  204. if (!isEmpty()) root.color = BLACK;
  205.  
  206. }
  207. private Node deleteMax(Node h) {
  208. if (isRed(h.left))
  209. h = rotateRight(h);
  210.  
  211. if (h.right == null)
  212. return null;
  213.  
  214. if (!isRed(h.right) && !isRed(h.right.left))
  215. h = moveRedRight(h);
  216.  
  217. h.right = deleteMax(h.right);
  218.  
  219. return balance(h);
  220. }
  221.  
  222. public float min() {
  223. if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
  224. return min(root).key;
  225. }
  226. private Node min(Node x) {
  227. if (x.left == null) return x;
  228. else return min(x.left);
  229. }
  230.  
  231. public float max() {
  232. if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
  233. return max(root).key;
  234. }
  235. private Node max(Node x) {
  236. // assert x != null;
  237. if (x.right == null) return x;
  238. else return max(x.right);
  239. }
  240. private int size(Node x) {
  241. if (x == null) return 0;
  242. return x.size;
  243. }
  244. public int size() {
  245. return size(root);
  246. }
  247. public boolean contains(float key) {
  248. return get(key) != null;
  249. }
  250. public String get(float key) {
  251. if (0.0f == key) throw new IllegalArgumentException("argument to get() is null");
  252. return get(root, key);
  253. }
  254.  
  255. private String get(Node x, float key) {
  256. while (x != null) {
  257. int cmp = x.compareTo(key);
  258. if (cmp < 0) x = x.left;
  259. else if (cmp > 0) x = x.right;
  260. else return x.val;
  261. }
  262. return null;
  263. }
  264. =======
  265. }
  266. >>>>>>> parent of 256eb3e... maroooo
  267. }
RAW Paste Data