Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class RBTree <Key extends Comparable<Key>> {
- private static final boolean RED = true;
- private static final boolean BLACK = false;
- Node root;
- /* 1)jesli puste to dodajemy jako czarny korzeń
- * 2)else{ skladamy na prawo/lewo w zaleznosci od wielkosci
- * a) if parent is black OK!
- * b) if parent is red
- * -if black or absent sibling = rotuj
- * -if red sibling, recolour & check again
- */
- //NO LINK TO PARENT
- public RBTree(){
- root=null;
- }
- private boolean isRed( Node x){
- return x!= null && x.color==RED;
- }
- public void insert(Key key){
- root = insert(key, root);
- root.color=BLACK;
- }
- public Node insert(Key key, Node aktualny) {
- /*if (root == null) {
- root = new Node(key);
- }*/
- if(aktualny == null){
- return new Node(key);
- }
- //aktualny = root;
- //while(true){
- int comp = key.compareTo(aktualny.key);
- //jesli wstawiany<aktualnego
- if(comp<0)
- aktualny.left=insert(key,aktualny.left);
- else if(comp>0)
- aktualny.right=insert(key,aktualny.right);
- else throw new RuntimeException("Duplicate"+key.toString());
- //break;}
- if (isRed(aktualny.left) && isRed(aktualny.left.left))
- aktualny.color=RED;
- aktualny.left.color=BLACK;
- aktualny = rotateR(aktualny);
- if (isRed(aktualny.right) && isRed(aktualny.right.right))
- aktualny.color=RED;
- aktualny.right.color=BLACK;
- aktualny = rotateL(aktualny);
- if (isRed(aktualny.left) && isRed(aktualny.left.right))
- aktualny.color=RED;
- aktualny.left.right.color=BLACK;
- aktualny.left = rotateL(aktualny.left);
- aktualny = rotateR(aktualny);
- if( isRed( aktualny.right ) && isRed( aktualny.right.left ) ) {
- aktualny.color =RED ;
- aktualny.right.left.color = BLACK ;
- aktualny.right= rotateR(aktualny.right);
- aktualny = rotateL( aktualny );
- }
- if (isRed(aktualny.left) && isRed(aktualny.right))
- colorFlip(aktualny);
- return aktualny;
- }
- /*public int zewn(Node aktualny){
- if(aktualny == null) return 1;
- return aktualny.key = zewn(aktualny.left)+zewn(aktualny.right);
- }*/
- private void colorFlip(Node aktualny){
- aktualny.color=!aktualny.color;
- aktualny.left.color=!aktualny.left.color;
- aktualny.right.color=!aktualny.right.color;
- }
- /*private Node rotateL(Node aktualny)
- { Node key=aktualny.right;
- aktualny.right=key.left;
- key.left=aktualny;
- key.color=aktualny.color;
- aktualny.color=RED;
- return key; }*/
- private Node rotateL(Node aktualny) {
- assert (aktualny != null) && isRed(aktualny.right);
- Node x = aktualny.right;
- aktualny.right = x.left;
- x.left = aktualny;
- x.color = x.left.color;
- x.left.color = RED;
- return x;
- }
- private Node rotateR(Node aktualny) {
- assert (aktualny != null) && isRed(aktualny.right);
- Node x = aktualny.left;
- aktualny.left = x.right;
- x.right = aktualny;
- x.color = x.right.color;
- x.right.color = RED;
- return x;
- }
- /*private Node rotateR(Node aktualny)
- { Node key=aktualny.left;
- aktualny.left=key.right;
- key.right=aktualny;
- key.color=aktualny.color;
- aktualny.color=RED;
- return key; }*/
- public Node findNode(Key key){
- Node aktualny = root;
- int comp = 0;
- while (aktualny != null && (comp = key.compareTo(aktualny.key))!=0)
- aktualny = comp<0 ? aktualny.left : aktualny.right;
- return aktualny;
- }
- public void printInOrder(Node aktualny)
- { //od najmniejszego do najwiekszego
- if(aktualny.left!=null)
- printInOrder(aktualny.left);
- System.out.println(aktualny);
- if(aktualny.right!=null)
- printInOrder(aktualny.right);
- }
- public void printPostOrder(Node aktualny)
- { //parent comes last
- if(aktualny.left!=null)
- printPostOrder(aktualny.left);
- if(aktualny.right!=null)
- printPostOrder(aktualny.right);
- System.out.println(aktualny);
- }
- public void printPreOrder(Node aktualny)
- {
- if(aktualny != null){
- System.out.println(aktualny);
- printPreOrder(aktualny.left);
- printPreOrder(aktualny.right);
- }
- }
- public int height(Node aktualny){
- if(aktualny == null){
- return 0;
- }else{
- //jako ze to nie koniec to dodajemy jeden do obecnie obliczonej juz wysokosci,
- //wieksza z głebokosci, bo poddrzewo lew i prawe mogą byc roznej wiekosci
- return 1 + Math.max(height(aktualny.left), height(aktualny.right));
- }
- }
- private class Node {
- Key key; // key
- Node left;
- Node right; // links to left and right subtrees
- boolean color; // color of parent link
- int N; // subtree count
- public Node(Key key) {
- this.key = key;
- left = right = null;
- color = RED;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement