트리-균형 두 갈래 트리 삽입 및 찾기 JAVA 구현(2): 삭제 방법 증가
36879 단어 java 구현
package com.tomsnail.data.tree;
/**
* AVL
* @author tomsnail
* @date 2015 3 30 4:35:50
*/
public class AVLTree {
/**
*
* @author tomsnail
* @date 2015 3 30 4:36:54
*/
private AVLNode rootNode;
private String bulidType = "";
/**
*
* @author tomsnail
* @date 2015 3 30 4:36:08
*/
public void add(int value){
AVLNode subNode = null;
if(rootNode==null){
subNode = new AVLNode(value);
rootNode = subNode;
}else{
subNode = addNode(rootNode,value);
}
reBuild(subNode);
}
private AVLNode addNode(AVLNode node,int value){
AVLNode subNode = null;
if(node.getValue()>value){
if(node.getLeftNode()==null){
subNode = new AVLNode(value);
node.setLeftNode(subNode);
}else{
subNode = addNode(node.getLeftNode(), value);
}
}
if(node.getValue()<value){
if(node.getRightNode()==null){
subNode = new AVLNode(value);
node.setRightNode(subNode);
}else{
subNode = addNode(node.getRightNode(),value);
}
}
return subNode;
}
/**
*
* @author tomsnail
* @date 2015 3 30 5:42:00
*/
private void reBuild(AVLNode node){
if(node!=null){
AVLNode tempRootNode = findTempRootNode(node);
if(tempRootNode!=null){
if(bulidType.equals("ll")){
Lrotate(node,tempRootNode);
}else if(bulidType.equals("rr")){
Rrotate(node,tempRootNode);
}else if(bulidType.equals("lr")){
Rrotate(node,tempRootNode.getLeftNode());
Lrotate(node,tempRootNode);
}else if(bulidType.equals("rl")){
Lrotate(node,tempRootNode.getRightNode());
Rrotate(node,tempRootNode);
}
reBuild(tempRootNode);
}
}
}
/**
*
* @author tomsnail
* @date 2015 3 30 9:23:28
*/
private void Rrotate(AVLNode node,AVLNode tempRootNode){
AVLNode rotateNode = tempRootNode.getRightNode();//
AVLNode rootNode = tempRootNode.getRootNode();//
String type = "";
if(rootNode!=null){
if(rootNode.getLeftNode()==tempRootNode){
type="l";
}else{
type="r";
}
}
AVLNode adjustNode = rotateNode.getLeftNode();//
rotateNode.setLeftNode(tempRootNode);
tempRootNode.setRightNode(null);
if(adjustNode!=null){
tempRootNode.setRightNode(adjustNode);
}
if(rootNode==null){
rotateNode.setRootNode(null);
this.rootNode = rotateNode;
}
if(type.equals("r")){
rootNode.setRightNode(rotateNode);
}else if(type.equals("l")){
rootNode.setLeftNode(rotateNode);
}
}
/**
*
* @author tomsnail
* @date 2015 3 30 9:23:28
*/
private void Lrotate(AVLNode node,AVLNode tempRootNode){
AVLNode rotateNode = tempRootNode.getLeftNode();//
AVLNode rootNode = tempRootNode.getRootNode();//
String type = "";
if(rootNode!=null){//
if(rootNode.getLeftNode()==tempRootNode){
type="l";
}else{
type="r";
}
}
AVLNode adjustNode = rotateNode.getRightNode();//
rotateNode.setRightNode(tempRootNode);
tempRootNode.setLeftNode(null);
if(adjustNode!=null){
tempRootNode.setLeftNode(adjustNode);
}
if(rootNode==null){
rotateNode.setRootNode(null);
this.rootNode = rotateNode;
}
if(type.equals("r")){
rootNode.setRightNode(rotateNode);
}else if(type.equals("l")){
rootNode.setLeftNode(rotateNode);
}
}
/**
*
* @author tomsnail
* @date 2015 3 30 5:40:55
*/
private AVLNode findTempRootNode(AVLNode node){
AVLNode noB = getNoBalance(node);
if(noB==null){
return null;
}
if(isTypeLL(noB)){
bulidType = "ll";
}else if(isTypeRR(noB)){
bulidType = "rr";
}else if(isTypeLR(noB)){
bulidType = "lr";
}else if(isTypeRL(noB)){
bulidType = "rl";
}
return noB;
}
//
private boolean isTypeLL(AVLNode noB){
try {
if(noB.getRightNode()==null&&noB.getLeftNode().getRightNode()==null&&!noB.getLeftNode().getLeftNode().hasSubNode()){
return true;
}
if(noB.getRightNode()!=null&&noB.getLeftNode().getRightNode()!=null&&noB.getLeftNode().getLeftNode().hasSubNode()){
return true;
}
} catch (Exception e) {
}
return false;
}
//
private boolean isTypeRR(AVLNode noB){
try {
if(noB.getLeftNode()==null&&noB.getRightNode().getLeftNode()==null&&!noB.getRightNode().getRightNode().hasSubNode()){
return true;
}
if(noB.getLeftNode()!=null&&noB.getRightNode().getLeftNode()!=null&&noB.getRightNode().getRightNode().hasSubNode()){
return true;
}
} catch (Exception e) {
}
return false;
}
//
private boolean isTypeLR(AVLNode noB){
try {
if(noB.getRightNode()==null&&noB.getLeftNode().getLeftNode()==null&&!noB.getLeftNode().getRightNode().hasSubNode()){
return true;
}
if(noB.getRightNode()!=null&&noB.getLeftNode().getLeftNode()!=null&&noB.getLeftNode().getRightNode().hasSubNode()){
return true;
}
} catch (Exception e) {
}
return false;
}
//
private boolean isTypeRL(AVLNode noB){
try {
if(noB.getLeftNode()==null&&noB.getRightNode().getRightNode()==null&&!noB.getRightNode().getLeftNode().hasSubNode()){
return true;
}
if(noB.getLeftNode()!=null&&noB.getRightNode().getRightNode()!=null&&noB.getRightNode().getLeftNode().hasSubNode()){
return true;
}
} catch (Exception e) {
}
return false;
}
//
private AVLNode getNoBalance(AVLNode node){
if(node.getRootNode()==null){
return null;
}else{
if(!isBalance(node.getRootNode())){
return node.getRootNode();
}else{
return getNoBalance(node.getRootNode());
}
}
}
/**
*
* @author tomsnail
* @date 2015 3 30 4:36:20
*/
public void delete(int value){
AVLNode wantDeleteNode = find(value);
if(wantDeleteNode==null){
return;
}else{
if(wantDeleteNode.getLeftNode()==null&&wantDeleteNode.getRightNode()==null){//
AVLNode rootNode = wantDeleteNode.getRootNode();
if(rootNode!=null){
if(rootNode.getLeftNode()==wantDeleteNode){
rootNode.setLeftNode(null);
}else{
rootNode.setRightNode(null);
}
reBuild(rootNode);
}
}else if(wantDeleteNode.getRightNode()==null){//
AVLNode rootNode = wantDeleteNode.getRootNode();
if(rootNode!=null){
if(rootNode.getLeftNode()==wantDeleteNode){
rootNode.setLeftNode(wantDeleteNode.getLeftNode());
}else{
rootNode.setRightNode(wantDeleteNode.getLeftNode());
}
wantDeleteNode.setLeftNode(null);
reBuild(rootNode);
}
}else if(wantDeleteNode.getLeftNode()==null){//
AVLNode rootNode = wantDeleteNode.getRootNode();
if(rootNode!=null){
if(rootNode.getRightNode()==wantDeleteNode){
rootNode.setLeftNode(wantDeleteNode.getRightNode());
}else{
rootNode.setRightNode(wantDeleteNode.getRightNode());
}
wantDeleteNode.setRightNode(null);
reBuild(rootNode);
}
}else {//
AVLNode maxNode = getLeftMaxValueNode(wantDeleteNode.getLeftNode());//
AVLNode rootMaxNode = maxNode.getRootNode();//
if(maxNode.getLeftNode()!=null){// ，
rootMaxNode.setRightNode(maxNode.getLeftNode());
maxNode.setLeftNode(null);
}else{//
rootMaxNode.setRightNode(null);
}
wantDeleteNode.setValue(maxNode.getValue());//
maxNode=null;//
reBuild(rootMaxNode);
}
}
}
//
private AVLNode getLeftMaxValueNode(AVLNode node){
if(node!=null&&node.getRightNode()!=null){
return getLeftMaxValueNode(node.getRightNode());
}else{
return node;
}
}
/**
*
* @author tomsnail
* @date 2015 3 30 4:36:35
*/
public AVLNode find(int value){
return findWith2(rootNode,value);
}
private AVLNode findWith2(AVLNode node,int value){
if(node==null){
return null;
}
System.out.println(node.getValue());
if(node.getValue()>value){
return findWith2(node.getLeftNode(),value);
}else if(node.getValue()<value){
return findWith2(node.getRightNode(),value);
}else{
return node;
}
}
/**
*
* @author tomsnail
* @date 2015 3 31 6:23:05
*/
public void midScan(AVLNode node){
if(node==null){
return;
}
midScan(node.getLeftNode());
System.out.println(node.getValue());
midScan(node.getRightNode());
}
public AVLNode getRootNode() {
return rootNode;
}
public static void main(String[] args) {
int[] is = new int[]{10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80};//10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80
AVLTree tree = new AVLTree();
for(int i=0;i<is.length;i++){
tree.add(is[i]);
}
System.out.println(tree.getRootNode().getValue());
System.out.println("----------------------------");
tree.midScan(tree.getRootNode());
tree.delete(4);
System.out.println(isBalance(tree.getRootNode()));
System.out.println();
//tree.find(40);
}
public static int depth(AVLNode node){
if(node==null){
return 0;
}else{
int ld = depth(node.getLeftNode());
int rd = depth(node.getRightNode());
return 1 + (ld >rd ? ld : rd);
}
}
public static boolean isBalance(AVLNode node){
if (node==null)
return true;
int dis = depth(node.getLeftNode()) - depth(node.getRightNode());
if (dis>1 || dis<-1 )
return false;
else
return isBalance(node.getLeftNode()) && isBalance(node.getRightNode());
}
}
class AVLNode{
private int value;
private AVLNode leftNode;
private AVLNode rightNode;
private AVLNode rootNode;
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public AVLNode getLeftNode() {
return leftNode;
}
public void setLeftNode(AVLNode leftNode) {
this.leftNode = leftNode;
if(leftNode!=null){
leftNode.setRootNode(this);
}
}
public AVLNode getRightNode() {
return rightNode;
}
public void setRightNode(AVLNode rightNode) {
this.rightNode = rightNode;
if(rightNode!=null){
rightNode.setRootNode(this);
}
}
public AVLNode getRootNode() {
return rootNode;
}
public void setRootNode(AVLNode rootNode) {
this.rootNode = rootNode;
}
public boolean hasSubNode(){
if(this.leftNode!=null||this.rightNode!=null){
return true;
}else{
return false;
}
}
public AVLNode(){
}
public AVLNode(int value){
this.value = value;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JAVA는 두 갈래 나무의 전, 중, 후 순서를 반복한다(귀속과 비귀속)최근 면접에서 두 갈래 나무 뒤에 비귀속 실현 방법을 물어본 적이 있는데, 귀속 해결이 될 줄 알았으면 OK인 줄 알았는데 너무 요행을 바라는 것 같아서 다음 면접을 앞두고 이 문제를 정리해 봤다. 우선 두 갈래 트...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
