데이터 구조의 자체 균형 이 진 트 리 찾기 (1)
AVL 트 리 의 특징 은 트 리 의 모든 노드 에 대해 노드 의 좌우 서브 트 리 의 높이 차이 가 최대 1 이 므 로 AVL 트 리 를 고도 밸 런 스 트 리 라 고도 부른다.AVL 트 리 는 발명자 G. M. Adelson - Velsky 와 E. M. Landis 에서 이름 을 얻 었 다. 그들 은 1962 년 논문 'An algorithm for the organization of information' 에서 발표 했다.
우리 가 노드 의 균형 요 소 를 정의 하 는 것 은 바로 이 노드 의 왼쪽 나무 높이 와 오른쪽 나무 높이 의 차이 이다. 위의 설명 에 따 르 면 우 리 는 + 1, 0, - 1 균형 요 소 를 가 진 노드 는 균형 노드 이 고 다른 것 은 모두 불 균형 노드 라 는 것 을 알 수 있다.노드 가 불 균형 일 때 우 리 는 이 노드 를 균형 화 시 켜 야 한다.우 리 는 균형 인 자 를 노드 의 내부 에 저장 할 수도 있 고 노드 의 높이 를 통 해 계산 할 수도 있다.
높이 가 h 인 AVL 트 리 로 노드 수가 N 이 가장 많 습 니 다.최소최소 노드 n 예 를 들 어 페 베 르 나시 수열 은 수학 귀납법 으로 증명 할 수 있다. = - 1 (Fibonacci polynomial).즉: = 0 (AVL Tree 높이 0 을 나타 내 는 노드 총수) = 1 (AVL Tree 높이 1 을 나타 내 는 노드 총수) = 2 (AVL Tree 높이 2 를 나타 내 는 노드 총수) = + + 1 (AVL Tree 높이 h 를 나타 내 는 노드 총수) 은 노드 수가 N 일 때 높이 h 가 가장 많다 는 것 이다.
불 균형 노드 의 균형 화 는 보통 네 가지 상황 이 있 는데 지금 은 아래 에 열거 되 어 있다.
이 네 가지 방식 의 코드 는 다음 과 같다.
//
private AVLTreeNode rotateWithLeftChild(AVLTreeNode node)
{
AVLTreeNode root=node.left;
node.left=root.right;
root.right=node;
node.height=Math.max(height(node.left),height(node.right))+1;
root.height=Math.max(height(root.left),height(root.right))+1;
return root;
}
//
private AVLTreeNode rotateWithRightChild(AVLTreeNode node)
{
AVLTreeNode root=node.right;
node.right=root.left;
root.left=node;
node.height=Math.max(height(node.left),height(node.right))+1;
root.height=Math.max(height(root.left),height(root.right))+1;
return root;
}
//
private AVLTreeNode doubleRotateLeftChild(AVLTreeNode node)
{
node.left=rotateWithRightChild(node.left);
return rotateWithLeftChild(node);
}
//
private AVLTreeNode doubleRotateRightChild(AVLTreeNode node)
{
node.left=rotateWithLeftChild(node.right);
return rotateWithRightChild(node);
}AVL 트 리 의 동작 은 삽입, 삭제, 찾기 세 가지 기본 동작 을 포함 하 는데 이 세 가지 상황 은 평균 과 최 악의 상황 에서 시간 복잡 도 는 모두 O (log n) 이다.
삽입:
AVL 트 리 에 삽입 하면 균형 이 잡 히 지 않 은 이 진 트 리 처럼 주어진 값 을 트 리 에 삽입 한 다음 아래 에서 위로 뿌리 노드 를 되 돌려 삽입 하 는 동안 불 균형 이 된 모든 노드 를 회전 시 켜 완성 할 수 있 습 니 다.루트 노드 로 되 돌아 가 는 길에 최대 1.5 곱 하기 logn 개의 노드 가 있 고 AVL 회전 할 때마다 일정한 시간 을 소모 하기 때문에 삽입 처 리 는 전체적으로 O (logn) 시간 을 소모 합 니 다.
삭제:
AVL 트 리 에서 삭제 하면 삭제 할 노드 를 아래로 한 잎 노드 로 회전 시 킨 다음 에 이 잎 노드 를 직접 잘라 서 완성 할 수 있 습 니 다.잎 노드 로 회전 하 는 동안 최대 log n 개의 노드 가 회전 되 고 매번 AVL 회전 은 일정한 시간 을 소모 하기 때문에 삭제 처 리 는 전체적으로 O (logn) 시간 을 소모 합 니 다.
찾기:
일반 이 진 트 리 처럼 진행 할 수 있 기 때문에 O (log n) 시간 이 걸 립 니 다. AVL 트 리 는 항상 균형 을 유지 하기 때 문 입 니 다.특별한 준비 가 필요 없 이 나무의 구 조 는 찾 아서 바 뀌 지 않 습 니 다.(이것 은 스 트 레 칭 트 리 와 상대 적 으로 서 있 는 것 입 니 다. 찾기 때문에 트 리 구 조 를 변경 합 니 다.)
균형 이 잡 힌 이 진 트 리 와 일반적인 이 진 트 리 의 차 이 를 관찰 하기 위해 서 는 같은 이 진 트 리 에 대해 두 가지 다른 결 과 를 내 놓 을 것 입 니 다. 옮 겨 다 니 는 결 과 를 통 해 이 진 트 리 의 구조 상 태 를 알 수 있 습 니 다.다음은 먼저 일반 두 갈래 로 나 무 를 찾 는 프로그램 을 보 여 줍 니 다.
package mianshiti;
import java.util.*;
public class BinarySearchTree {
private TreeNode root=null;//
public static void main(String[] args) {
// TODO Auto-generated method stub
BinarySearchTree mytree=new BinarySearchTree();
mytree.insert(4);
mytree.insert(3);
mytree.insert(2);
mytree.insert(1);
mytree.insert(5);
System.out.println(" ：");
mytree.preorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.inorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.postorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.nonRecursivePreorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.nonRecursiveInorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.nonRecursivePostorder(mytree.getRoot());
System.out.println();
}
//
public void preorder(TreeNode node)
{
if(node!=null)
{
this.getNodeInfo(node);
preorder(node.left);
preorder(node.right);
}
}
//
public void inorder(TreeNode node)
{
if(node!=null)
{
inorder(node.left);
this.getNodeInfo(node);
inorder(node.right);
}
}
//
public void postorder(TreeNode node)
{
if(node!=null)
{
postorder(node.left);
postorder(node.right);
this.getNodeInfo(node);
}
}
//
public void nonRecursivePreorder(TreeNode node)
{
Stack<TreeNode> mystack=new Stack<TreeNode>();
if(node!=null)
{
mystack.push(node);
while(!mystack.isEmpty())
{
TreeNode temp=mystack.pop();
this.getNodeInfo(temp);
if(temp.right!=null)
{
mystack.push(temp.right);
}
if(temp.left!=null)
{
mystack.push(temp.left);
}
}
}
}
//
public void nonRecursiveInorder(TreeNode node)
{
Stack<TreeNode> mystack=new Stack<TreeNode>();
while(node!=null)
{
while(node!=null)
{
if(node.right!=null)
{
mystack.push(node.right);
}
mystack.push(node);
node=node.left;
}
node=mystack.pop();
while(!mystack.isEmpty()&&node.right==null)
{
this.getNodeInfo(node);
node=mystack.pop();
}
this.getNodeInfo(node);
if(!mystack.isEmpty())
{
node=mystack.pop();
}else
{
node=null;
}
}
}
//
public void nonRecursivePostorder(TreeNode node)
{
Stack<TreeNode> mystack=new Stack<TreeNode>();
TreeNode temp=node;
while(node!=null)
{
for(;node.left!=null;node=node.left)
{
mystack.push(node);
}
while(node!=null&&(node.right==null||node.right==temp))
{
this.getNodeInfo(node);
temp=node;
if(mystack.isEmpty())
return;
node=mystack.pop();
}
mystack.push(node);
node=node.right;
}
}
//
public BinarySearchTree()
{
this.root=null;
}
public TreeNode getRoot()
{
return this.root;
}
//
public void insert(int value)
{
TreeNode nextnode=new TreeNode(value);
TreeNode temp=this.root;
if(this.root==null)
{
this.root=nextnode;
nextnode.parent=null;
return ;
}
while(temp!=null)
{
if(value<temp.data)
{
if(temp.left==null)
{
temp.left=nextnode;
nextnode.parent=temp;
return;
}else
{
temp=temp.left;
}
}else if(value>temp.data)
{
if(temp.right==null)
{
temp.right=nextnode;
nextnode.parent=temp;
return;
}else
{
temp=temp.right;
}
}
}
}
// begin
private TreeNode minTreeNode(TreeNode begin)
{
if(begin==null)
return null;
while(begin.left!=null)
{
begin=begin.left;
}
return begin;
}
// begin
private TreeNode maxTreeNode(TreeNode begin)
{
if(begin==null)
return null;
while(begin.right!=null)
{
begin=begin.right;
}
return begin;
}
//
public void delete(int value)
{
if(this.root==null)
{
System.out.println(" ， "+value);
return;
}
TreeNode temp=this.root;
while(temp!=null)
{
if(value>temp.data)
{
if(temp.right==null)
{
System.out.println(" ");
}else
{
temp=temp.right;
}
}else if(value<temp.data)
{
if(temp.left==null)
{
System.out.println(" ");
}else
{
temp=temp.left;
}
}else
{
//
if(temp.left==null&&temp.right==null)//
{
if(temp.parent.right==temp)
{
temp.parent.right=null;
}else
{
temp.parent.left=null;
}
}else if(temp.right!=null&&temp.left==null)// ，
{
if(temp.parent.right==temp)
{
temp.parent.right=temp.right;
temp.right.parent=temp.parent;
}else
{
temp.parent.left=temp.right;
temp.right.parent=temp.parent;
}
}else if(temp.left!=null&&temp.right==null)// ，
{
if(temp.parent.right==temp)
{
temp.parent.right=temp.left;
temp.left.parent=temp.parent;
}
else
{
temp.parent.left=temp.left;
temp.left.parent=temp.parent;
}
}else//
{
TreeNode replacenode=minTreeNode(temp.right);
delete(replacenode.data);
temp.data=replacenode.data;
}
break;
}
}
}
public void getNodeInfo(TreeNode treenode)
{
if(treenode!=null)
{
System.out.print(treenode.data+" ");
}
}
}
class TreeNode{
public int data;
public TreeNode left;//
public TreeNode right;//
public TreeNode parent;//
//
public TreeNode(int data)
{
this(data,null,null,null);
}
public TreeNode(int data,TreeNode left,TreeNode right,TreeNode parent)
{
this.data=data;
this.left=left;
this.right=right;
this.parent=parent;
}
}
실행 결 과 는 다음 과 같다.
：
4 3 2 1 5
：
1 2 3 4 5
：
1 2 3 5 4
：
4 3 2 1 5
：
1 2 3 4 5
：
1 2 3 5 4
그 다음 에 우 리 는 균형 이 잡 힌 두 갈래 에서 나 온 나무의 실현 을 찾 습 니 다.
package mianshiti;
import java.util.Stack;
//AVL
public class AVLTree {
AVLTreeNode rootnode=null;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
AVLTree mytree=new AVLTree();
mytree.insert(4);
mytree.insert(3);
mytree.insert(2);
mytree.insert(1);
mytree.insert(5);
System.out.println(" ：");
mytree.preorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.inorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.postorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.nonRecursivePreorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.nonRecursiveInorder(mytree.getRoot());
System.out.println();
System.out.println(" ：");
mytree.nonRecursivePostorder(mytree.getRoot());
System.out.println();
}
public AVLTreeNode getRoot()
{
return rootnode;
}
//
public void preorder(AVLTreeNode node)
{
if(node!=null)
{
this.getNodeInfo(node);
preorder(node.left);
preorder(node.right);
}
}
//
public void inorder(AVLTreeNode node)
{
if(node!=null)
{
inorder(node.left);
this.getNodeInfo(node);
inorder(node.right);
}
}
//
public void postorder(AVLTreeNode node)
{
if(node!=null)
{
postorder(node.left);
postorder(node.right);
this.getNodeInfo(node);
}
}
//
public void nonRecursivePreorder(AVLTreeNode node)
{
Stack<AVLTreeNode> mystack=new Stack<AVLTreeNode>();
if(node!=null)
{
mystack.push(node);
while(!mystack.isEmpty())
{
AVLTreeNode temp=mystack.pop();
this.getNodeInfo(temp);
if(temp.right!=null)
{
mystack.push(temp.right);
}
if(temp.left!=null)
{
mystack.push(temp.left);
}
}
}
}
//
public void nonRecursiveInorder(AVLTreeNode node)
{
Stack<AVLTreeNode> mystack=new Stack<AVLTreeNode>();
while(node!=null)
{
while(node!=null)
{
if(node.right!=null)
{
mystack.push(node.right);
}
mystack.push(node);
node=node.left;
}
node=mystack.pop();
while(!mystack.isEmpty()&&node.right==null)
{
this.getNodeInfo(node);
node=mystack.pop();
}
this.getNodeInfo(node);
if(!mystack.isEmpty())
{
node=mystack.pop();
}else
{
node=null;
}
}
}
//
public void nonRecursivePostorder(AVLTreeNode node)
{
Stack<AVLTreeNode> mystack=new Stack<AVLTreeNode>();
AVLTreeNode temp=node;
while(node!=null)
{
for(;node.left!=null;node=node.left)
{
mystack.push(node);
}
while(node!=null&&(node.right==null||node.right==temp))
{
this.getNodeInfo(node);
temp=node;
if(mystack.isEmpty())
return;
node=mystack.pop();
}
mystack.push(node);
node=node.right;
}
}
public void getNodeInfo(AVLTreeNode node)
{
if(node!=null)
{
System.out.print(node.data+" ");
}
}
public void insert(int data)
{
rootnode=insert(data,rootnode);
}
private AVLTreeNode insert(int data,AVLTreeNode root)
{
if(root==null)
{
AVLTreeNode node=new AVLTreeNode(data);
return node;
}
if(data<root.data)
{
root.left=insert(data,root.left);
}else if(data>root.data)
{
root.right=insert(data,root.right);
}else
{
System.out.println(" "+data);
}
return balance(root);
}
//
private AVLTreeNode balance(AVLTreeNode root)
{
if(root==null)
return root;
if(height(root.left)-height(root.right)>1)
{
if(height(root.left.left)>=height(root.left.right))
{
root=rotateWithLeftChild(root);
}else
{
root=doubleRotateLeftChild(root);
}
}else if(height(root.right)-height(root.left)>1)
{
if(height(root.right.right)>=height(root.right.left))
{
root=rotateWithRightChild(root);
}else
{
root=doubleRotateRightChild(root);
}
}
root.height=Math.max(height(root.left), height(root.right))+1;
return root;
}
//
private AVLTreeNode rotateWithLeftChild(AVLTreeNode node)
{
AVLTreeNode root=node.left;
node.left=root.right;
root.right=node;
node.height=Math.max(height(node.left),height(node.right))+1;
root.height=Math.max(height(root.left),height(root.right))+1;
return root;
}
//
private AVLTreeNode rotateWithRightChild(AVLTreeNode node)
{
AVLTreeNode root=node.right;
node.right=root.left;
root.left=node;
node.height=Math.max(height(node.left),height(node.right))+1;
root.height=Math.max(height(root.left),height(root.right))+1;
return root;
}
//
private AVLTreeNode doubleRotateLeftChild(AVLTreeNode node)
{
node.left=rotateWithRightChild(node.left);
return rotateWithLeftChild(node);
}
//
private AVLTreeNode doubleRotateRightChild(AVLTreeNode node)
{
node.left=rotateWithLeftChild(node.right);
return rotateWithRightChild(node);
}
//
private int height(AVLTreeNode node)
{
return node==null?-1:node.height;
}
}
// AVL
class AVLTreeNode
{
int data;
AVLTreeNode left;
AVLTreeNode right;
int height;
//
public AVLTreeNode(int data)
{
this(data,null,null);
}
public AVLTreeNode(int data,AVLTreeNode left,AVLTreeNode right)
{
this.data=data;
this.left=left;
this.right=right;
this.height=0;
}
}실행 결 과 는 다음 과 같다.
：
3 2 1 4 5
：
1 2 3 4 5
：
1 2 5 4 3
：
3 2 1 4 5
：
1 2 3 4 5
：
1 2 5 4 3
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
