[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가지 방법
- 왼쪽 자식노드가 null
- 오른쪽 자식노드가 null
- 자식노드가 둘 다 존재하는 경우
트리
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; } } }
복잡한 구조도 구현 가능
Author And Source
이 문제에 관하여([211130] 교육 30일차), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@choiyezz/211130-교육-30일차저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)