// root = rotationR( root ); public static Node rotationR( Node a ) { if( a.left != null ) { Node b = a.left; a.left = b.right; b.right = a; return b; } else { return a; } } // root = rotationL( root ); public static Node rotationL( Node a ) { if( a.right != null ) { Node b = a.right; a.right = b.left; b.left = a; return b; } else { return a; } }
루트노드의 왼쪽 자식노드가 null 이 아니면 Node b 가 가리키게 한다. 그리고 루트노드 왼쪽 자식노드가 Node b의 오른쪽 자식노드를 가리키게 하고 Node b의 오른쪽 자식노드는 매개변수의 node 를 가리키게 된다.
루트노드의 오른쪽 자식노드가 null 이 아니면 Node b가 가리키게 한다. Node b의 왼쪽 자식 노드를 루트노드의 오른쪽 자식 노드가 가리키게 하고 Node b 의 왼쪽 자식 노드는 루트 노드를 가리키게 된다.
public static Node delete( Node n ) { if( n.left == null ) { return n.right; } else if( n.right == null ) { return n.left; } else { System.out.println( n.data + " 양쪽 다 있는 경우"); if( false ) { Node max = findMax( n.left ); n.data = max.data; } else { Node min = findMin( n.right ); System.out.println( "->" + min.data ); n.data = min.data; } } return n; } // public static Node findMin( Node n ) { while( n.left != null ) { n = n.left; } return n; } // public static Node findMax( Node n ) { while( n.right != null ) { n = n.right; } return n; }
노드를 삭제하는 3가지 방법
class Node { String name = null; Node child = null; Node sibling = null; // public Node( String n ) { this.name = n; } // public void addChild( Node n ) { if( child == null ) { child = n; } else { Node t = child; while( t.sibling != null ) { t = t.sibling; } t.sibling = n; } } }
복잡한 구조도 구현 가능