📄 avltreenode.java
字号:
/**
* @ AVLTreeNode.java
* @ Designed by BySelf
*/
import java.util.Stack;
import java.lang.Math;
/**
* AVLTreeNode
* Tree node used to implemennt the AVLTree.
* NOTE:
* 1. The node has a unique value, that will used to decide its in tree position
* 2. You should implement rotateLeft and rotateRight for further implementation
* did in AVLTree.
*/
class AVLTreeNode
{
/**
* Constructor
* initialize all the node fields values.
*/
public AVLTreeNode(int value)
{
subTreeHeight = 0; // initialize to be zero
leftChild = null;
rightChild = null;
parent = null;
this.value = value;
}
/**
* public int balanceValue
* balance value of this TreeNode, initialized to be 0
* balanceValue = leftChild.getSubTreeHeight() - rightChild.getSubTreeHeight().
* NOTE:
* You can use this field and make your AVLTree insert and delete a little
* easier, but you can also omit it.
*/
public int balanceValue;
/**
* private int value
* Decide the value of this node, which is used to decide the
* insert position of this node.
*/
private int value;
/**
* public int getValue()
* Get the value of this node.
* NOTE:
* leftChild.value < this.value < rightChild.value
*/
public int getValue()
{
return value;
}
/**
* private int subTreeHeight
* The balance value of this AVLTreeNode
* NOTE:
* 1. initialized to be zero
* 2. value = the height of its subtree, i will use this feature
* to test the correctness of your subTreeHeight
* 3. whenever rotate or do something change the height of subtree
* remember to change its value
*/
private int subTreeHeight;
/**
* public int setValue(int newValue)
* Set this.subTreeHeight to be newValue.
* Return old subTreeHeight;
*/
public int setSubTreeHeight(int newValue)
{
int oldValue = subTreeHeight;
subTreeHeight = newValue;
return oldValue;
}
/**
* public int getValue()
* Get current node's subTreeHeight.
* Return this.subTreeHeight.
*/
public int getSubTreeHeight()
{
return subTreeHeight;
}
/**
* private AVLTreeNode leftChild
* The left child of current tree node. It is true that
* child.subTreeHeight <= this.subTreeHeight-1.
*/
private AVLTreeNode leftChild;
/**
* public AVLTreeNode setLeftChild(AVLTreeNode leftChild)
* Set the left child node.
* Return old child.
*/
public AVLTreeNode setLeftChild(AVLTreeNode leftChild)
{
AVLTreeNode oldChild = this.leftChild;
this.leftChild = leftChild;
return oldChild;
}
/**
* public AVLTreeNode getLeftChild()
* Get the left child node of this.
*/
public AVLTreeNode getLeftChild()
{
return leftChild;
}
/**
* private AVLTreeNode rightChild
* The right child of current tree node. It is true that
* child.subTreeHeight <= this.subTreeHeight-1.
* NOTE:
* this.subTreeHeight = max(rightChild.subTreeHeight+1,
* leftChild.subTreeHeight+1).
*/
private AVLTreeNode rightChild;
/**
* public AVLTreeNode setRightChild(AVLTreeNode rightChild)
* Set the right child node.
* Return old child.
*/
public AVLTreeNode setRightChild(AVLTreeNode rightChild)
{
AVLTreeNode oldChild = this.rightChild;
this.rightChild = rightChild;
return oldChild;
}
/**
* public AVLTreeNode getRightChild()
* Get the right child node of this.
*/
public AVLTreeNode getRightChild()
{
return rightChild;
}
/**
* private AVLTreeNode parent
* The parent node of this tree node, it may be useful when
* doing rotating.
*/
private AVLTreeNode parent;
/**
* public AVLTreeNode setParent(AVLTreeNode parent)
* Set the parent node.
* Return old parent.
*/
public AVLTreeNode setParent(AVLTreeNode parent)
{
AVLTreeNode oldParent = this.parent;
this.parent = parent;
return oldParent;
}
/**
* public AVLTreeNode getParent()
* Get the parent node of this.
*/
public AVLTreeNode getParent()
{
return parent;
}
public void setBalance(AVLTreeNode node)
{
if ( node == null)
return;
if ( node.leftChild == null && node.rightChild == null )
node.balanceValue = 0;
else if ( node.leftChild == null )
node.balanceValue = -1;
else if ( node.rightChild == null )
node.balanceValue = 1;
else
{
if ( node.leftChild.subTreeHeight == node.rightChild.subTreeHeight )
node.balanceValue = 0;
else if ( node.leftChild.subTreeHeight < node.rightChild.subTreeHeight )
node.balanceValue = -1;
else
node.balanceValue = 1;
}
}
public void setSubHeight(AVLTreeNode node)
{
if ( node == null)
return;
if ( node.leftChild == null && node.rightChild == null )
node.setSubTreeHeight(0);
else if ( node.leftChild == null )
node.setSubTreeHeight( node.rightChild.subTreeHeight + 1 );
else if ( node.rightChild == null )
node.setSubTreeHeight( node.leftChild.subTreeHeight + 1 );
else
node.setSubTreeHeight( Math.max( node.leftChild.subTreeHeight + 1, node.rightChild.subTreeHeight + 1 ) );
}
/**
* public AVLTreeNode rotateLeft();
* Rotate current AVLTreeNode left, then return the parent node
* NOTE:
* Do not forget to change balance value when doing rotate
*/
public AVLTreeNode rotateLeft()
{
// fill your implementation code here
// you can change the return value as you like
// remember that you cannot change the _value_ field
AVLTreeNode temp = this.parent;
AVLTreeNode node1 = this;
AVLTreeNode node2 = this.leftChild;
if ( temp == null )
return null;
node1.setParent(temp.parent);
if ( temp.parent != null )
{
if ( temp.value < temp.parent.value )
temp.parent.setLeftChild(node1);
else
temp.parent.setRightChild(node1);
}
node1.setLeftChild(temp);
temp.setParent(node1);
temp.setRightChild(node2);
if ( node2 != null )
node2.setParent(temp);
setSubHeight(temp);
setSubHeight(node1);
setSubHeight(node2);
setBalance(temp);
setBalance(node1);
return node1;
}
/**
* public AVLTreeNode rotateRight();
* Rotate current AVLTreeNode right, then return the parent node
* NOTE:
* Do not forget to change balance value when doing rotate
*/
public AVLTreeNode rotateRight()
{
// fill your implementation code here
// you can change the return value as you like
// remember that you cannot change the _value_ field
AVLTreeNode temp = this;
AVLTreeNode node1 = this.leftChild;
AVLTreeNode node2 = this.leftChild.rightChild;
if ( node1 == null )
return null;
node1.setParent(this.parent);
if ( this.parent != null )
{
if ( this.value < this.parent.value )
this.parent.setLeftChild(node1);
else
this.parent.setRightChild(node1);
}
node1.setRightChild(temp);
temp.setParent(node1);
temp.setLeftChild(node2);
if ( node2 != null )
node2.setParent(temp);
setSubHeight(temp);
setSubHeight(node1);
setSubHeight(node2);
setBalance(temp);
setBalance(node1);
return node1;
}
/**
* public void inOrder(AVLTreeNode node)
* Do inOrder walk in this subnode.
*/
public static void inOrder(AVLTreeNode node)
{
Stack stack=new Stack();
stack.push(node);
while(!stack.empty())
{
Object obj = stack.pop();
if(obj instanceof AVLTreeNode)
{
AVLTreeNode curNode = (AVLTreeNode)obj;
if (curNode.rightChild != null)
stack.push(curNode.rightChild);
stack.push(new Integer(curNode.value));
if (curNode.leftChild != null)
stack.push(curNode.leftChild);
}
else
{
System.out.print("[" + obj + "] ");
}
}
}
/**
* public static void main(String[] args)
* Do test.
*/
public static void main(String[] args)
{
System.out.println("============ Testing Rotate ============");
System.out.println(">>>> In order walk should always be:");
System.out.println("[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18]");
System.out.println();
// init tree:
// [15]
// / \
// [11] [17]
// / \ / \
// [7] [13] [16] [18]
// / \ / \
// [3] [9] [12] [14]
// / \ / \
// [1] [5] [8] [10]
// / \ / \
// [0][2][4][6]
AVLTreeNode[] node = new AVLTreeNode[19];
for (int i = 0; i < 19; i++)
{
node[i] = new AVLTreeNode(i);
}
node[0].parent = node[1];
node[2].parent = node[1];
node[1].leftChild = node[0];
node[1].rightChild = node[2];
node[4].parent = node[5];
node[6].parent = node[5];
node[5].leftChild = node[4];
node[5].rightChild = node[6];
node[1].parent = node[3];
node[5].parent = node[3];
node[3].leftChild = node[1];
node[3].rightChild = node[5];
node[8].parent = node[9];
node[10].parent = node[9];
node[9].leftChild = node[8];
node[9].rightChild = node[10];
node[3].parent = node[7];
node[9].parent = node[7];
node[7].leftChild = node[3];
node[7].rightChild = node[9];
node[12].parent = node[13];
node[14].parent = node[13];
node[13].leftChild = node[12];
node[13].rightChild = node[14];
node[7].parent = node[11];
node[13].parent = node[11];
node[11].leftChild = node[7];
node[11].rightChild = node[13];
node[16].parent = node[17];
node[18].parent = node[17];
node[17].leftChild = node[16];
node[17].rightChild = node[18];
node[11].parent = node[15];
node[17].parent = node[15];
node[15].leftChild = node[11];
node[15].rightChild = node[17];
System.out.println("First inwalk after init:");
AVLTreeNode.inOrder(node[15]);
System.out.println();
System.out.println();
// After node[11].rotateRight:
// [15]
// / \
// [7] [17]
// / \ / \
// [3] [11] [16] [18]
// / \ / \
// [1] [5] [9] [13]
// / \ / \ / \ / \
// [0][2][4][6][8] [10][12] [14]
System.out.println(">>>> Rotating right:");
AVLTreeNode a7 = node[11].rotateRight();
System.out.println("Rotating finished");
System.out.println("Check subtree root node current subtree root node should be [ 7 ]:");
System.out.println("> The result subtree root is : [ " + a7.getValue() + " ]");
System.out.println("> Parent of node [ 7 ] should be [ 15 ] : [ "
+ node[7].parent.getValue() + " ]");
System.out.println("> Left child of node [ 7 ] should be [ 3 ] : [ "
+ node[7].leftChild.getValue() + " ]");
System.out.println("> Right child of node [ 7 ] should be [ 11 ] : [ "
+ node[7].rightChild.getValue() + " ]");
System.out.println("> Parent of node [ 9 ] should be [ 11 ] : [ "
+ node[9].parent.getValue() + " ]");
System.out.println("> Parent of node [ 11 ] should be [ 7 ] : [ "
+ node[11].parent.getValue() + " ]");
System.out.println("> Left child of node [ 11 ] should be [ 9 ] : [ "
+ node[11].leftChild.getValue() + " ]");
System.out.println("> Left child of node [ 15 ] should be [ 7 ] : [ "
+ node[15].leftChild.getValue() + " ]");
System.out.println();
System.out.println("Second inwalk after rotate right:");
AVLTreeNode.inOrder(node[15]);
System.out.println();
System.out.println();
// After node[11].rotateLeft:
// [15]
// / \
// [11] [17]
// / \ / \
// [7] [13] [16] [18]
// / \ / \
// [3] [9] [12] [14]
// / \ / \
// [1] [5] [8] [10]
// / \ / \
// [0][2][4][6]
System.out.println(">>>> Rotating left:");
AVLTreeNode a11 = node[11].rotateLeft();
System.out.println("Rotating finished");
System.out.println("Check subtree root node current subtree root node should be [ 11 ]:");
System.out.println("> The result subtree root is : [ " + a11.getValue() + " ]");
System.out.println("> Parent of node [ 7 ] should be [ 11 ] : [ "
+ node[7].parent.getValue() + " ]");
System.out.println("> Left child of node [ 7 ] should be [ 3 ] : [ "
+ node[7].leftChild.getValue() + " ]");
System.out.println("> Right child of node [ 7 ] should be [ 9 ] : [ "
+ node[7].rightChild.getValue() + " ]");
System.out.println("> Parent of node [ 9 ] should be [ 7 ] : [ "
+ node[9].parent.getValue() + " ]");
System.out.println("> Parent of node [ 11 ] should be [ 15 ] : [ "
+ node[11].parent.getValue() + " ]");
System.out.println("> Left child of node [ 11 ] should be [ 7 ] : [ "
+ node[11].leftChild.getValue() + " ]");
System.out.println("> Left child of node [ 15 ] should be [ 11 ] : [ "
+ node[15].leftChild.getValue() + " ]");
System.out.println();
System.out.println("Third inwalk after rotate left:");
AVLTreeNode.inOrder(node[15]);
System.out.println();
System.out.println();
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -