[211130] 교육 30일차

트리 로테이션

	//	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;
		}
	}

rotationR

루트노드의 왼쪽 자식노드가 null 이 아니면 Node b 가 가리키게 한다. 그리고 루트노드 왼쪽 자식노드가 Node b의 오른쪽 자식노드를 가리키게 하고 Node b의 오른쪽 자식노드는 매개변수의 node 를 가리키게 된다.

rotationL

루트노드의 오른쪽 자식노드가 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가지 방법

1. 왼쪽 자식노드가 null
   
2. 오른쪽 자식노드가 null
   
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;
		}
	}
}

복잡한 구조도 구현 가능