在JAVA中实现AVL树 [英] Implementing an AVL tree in JAVA
本文介绍了在JAVA中实现AVL树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
public class AVLNode {
private int size; / **树的大小。 * /
private int height; / **树的高度。 * /
private Object key; / **当前节点的密钥。 * /
私有对象数据; / **当前节点的数据。 * /
私人比较器comp; / **节点使用的{@link比较器}。 * /
/ *当前节点指向的所有节点* /
private AVLNode left，right，parent，succ，pred;
/ *实例化一个新的AVL节点。
*
* @param key节点的键
* @param数据节点应该保留的数据
* @param comp比较器在树中使用
* /
public AVLNode（Object key，Object data，Comparator comp）{
this（key，data，comp，null）;
}
/ *实例化一个新的AVL节点。
*
* @param key节点的键
* @param数据节点应该保留的数据
* @param comp比较器在树中使用
* @param parent创建节点的父节点
* /
public AVLNode（Object key，Object data，Comparator comp，AVLNode parent）{
this.data = data;
this.key = key;
this.comp = comp;
this.parent = parent;
this.left = null;
this.right = null;
this.succ = null;
this.pred = null;
this.size = 1;
this.height = 0;
}
/ *将给定的数据添加到树中。
*
* @param键
* @param数据数据
* @插入和旋转后返回树的根
* @author< b>学生< / b>
* /
public AVLNode add（Object key，Object data）{
return null;
}
/ *删除一个节点，该节点的key等于
*（由{@link比较器}）到给定的参数。
*
* @param键
* @删除和轮换后的根
* @author< b>学生< / b>
* /
public AVLNode remove（Object key）{
return null;
}
我需要实现添加和删除功能。这是我到目前为止，都应该运行在 O（log（n））时间。两者都应该返回整个树的根：
/ *在树中添加一个新节点。
* @param键新节点的键
* @param数据新节点的数据
* /
public void add（Object key，Object data）{
if（isEmpty（））{
this.root = new AVLNode（key，data，comp）;
}
else {
root = this.root.add（key，data）;
}
}
/ **
*从
* n.key相等的树中删除一个节点n（由{@link比较器}）到给定的键。
*
* @param键
* /
public void remove（Object key）{
if（isEmpty（））{
return;
}
else
root = this.root.remove（key）;
}
我需要帮助才能添加和删除功能。
是否有任何指南来描述添加和删除操作的工作原理？要复制的图书馆或可以找出如何/为什么AVL树工作？
解决方案
来源，以防链接发生故障
package com.jwetherell.algorithms.data_structures;
import java.util.ArrayList;
import java.util.List;
/ **
* AVL树是一个自平衡二叉搜索树，它是第一个这样的
*数据结构。在AVL树中，任何节点的两个孩子
*子树的高度最多只有一个。 AVL树通常与
*红黑树进行比较，因为它们支持相同的操作集，并且因为
*红黑树也为基本操作花费了O（log n）时间。因为AVL
*树更刚性平衡，它们比
*查找密集型应用程序的红黑树更快。但是，b $ b *插入和删除时，红黑树更快。
*
* http://en.wikipedia.org/wiki/AVL_tree
*
* @author Justin Wetherell< phishman3579@gmail.com&
* /
public class AVLTree< T extends Comparable< T>扩展BinarySearchTree< T>实现BinarySearchTree.INodeCreator< T> {
私人枚举余额{
LEFT_LEFT，LEFT_RIGHT，RIGHT_LEFT，RIGHT_RIGHT
};
/ **
*默认构造函数。
* /
public AVLTree（）{
this.creator = this;
}
/ **
*具有外部节点创建者的构造函数。
* /
public AVLTree（INodeCreator< T>创建者）{
super（creator）;
}
/ **
* {@inheritDoc}
* /
@Override
protected Node< T> addValue（T id）{
Node< T> nodeToReturn = super.addValue（id）;
AVLNode< T> nodeAdded =（AVLNode< T>）nodeToReturn;
while（nodeAdded！= null）{
nodeAdded.updateHeight（）;
balanceAfterInsert（nodeAdded）;
nodeAdded =（AVLNode< T>）nodeAdded.parent;
}
return nodeToReturn;
}
/ **
*根据AVL插入后算法平衡树。
*
* @param node
*树的根平衡。
* /
private void balanceAfterInsert（AVLNode< T>节点）{
int balanceFactor = node.getBalanceFactor（）;
if（balanceFactor> 1 || balanceFactor< -1）{
AVLNode< T> parent = null;
AVLNode< T> child = null;
余额余额= null;
if（balanceFactor< 0）{
parent =（AVLNode< T>）node.lesser;
balanceFactor = parent.getBalanceFactor（）;
if（balanceFactor< 0）{
child =（AVLNode< T>）parent.lesser;
balance = Balance.LEFT_LEFT;
} else {
child =（AVLNode< T>）parent.greater;
balance = Balance.LEFT_RIGHT;
}
} else {
parent =（AVLNode< T>）node.greater;
balanceFactor = parent.getBalanceFactor（）;
if（balanceFactor< 0）{
child =（AVLNode< T>）parent.lesser;
balance = Balance.RIGHT_LEFT;
} else {
child =（AVLNode< T>）parent.greater;
balance = Balance.RIGHT_RIGHT;
}
}
if（balance == Balance.LEFT_RIGHT）{
//左 - 右（左旋转，右旋转）
rotateLeft父母）;
rotateRight（node）;
} else if（balance == Balance.RIGHT_LEFT）{
//右 - 左（右旋转，左旋）
rotateRight（parent）;
rotateLeft（node）;
} else if（balance == Balance.LEFT_LEFT）{
//左 - 左（右旋转）
rotateRight（node）;
} else {
//右 - 右（左旋）
rotateLeft（node）;
}
node.updateHeight（）; //新的子节点
child.updateHeight（）; //新的子节点
parent.updateHeight（）; //新建父节点
}
}
/ **
* {@inheritDoc}
* /
@Override
受保护的节点< T> removeValue（T value）{
//查找要删除的节点
Node< T> nodeToRemoved = this.getNode（value）;
if（nodeToRemoved！= null）{
//查找替换节点
Node< T> replacementNode = this.getReplacementNode（nodeToRemoved）;
//找到替换节点的父代重新确定
//树的高度/平衡
AVLNode< T> nodeToRefactor = null;
if（replacementNode！= null）
nodeToRefactor =（AVLNode< T>）replacementNode.parent;
if（nodeToRefactor == null）
nodeToRefactor =（AVLNode< T>）nodeToRemoved.parent;
if（nodeToRefactor！= null&& NodeToRefactor.equals（nodeToRemoved））
nodeToRefactor =（AVLNode< T>）replacementNode;
//替换节点
replaceNodeWithNode（nodeToRemoved，replacementNode）;
//在树上重新平衡树
if（nodeToRefactor！= null）{
while（nodeToRefactor！= null）{
nodeToRefactor .updateHeight（）;
balanceAfterDelete（nodeToRefactor）;
nodeToRefactor =（AVLNode< T>）nodeToRefactor.parent;
}
}
}
返回nodeToRemoved;
}
/ **
*根据AVL后删除算法平衡树。
*
* @param node
*树的根平衡。
* /
private void balanceAfterDelete（AVLNode< T>节点）{
int balanceFactor = node.getBalanceFactor（）;
if（balanceFactor == -2 || balanceFactor == 2）{
if（balanceFactor == -2）{
AVLNode< T> ll =（AVLNode< T>）node.lesser.lesser;
int lower =（ll！= null）？ ll.height：0;
AVLNode< T> lr =（AVLNode< T>）node.lesser.greater;
int greater =（lr！= null）？ lr.height：0;
if（less> = greater）{
rotateRight（node）;
node.updateHeight（）;
if（node.parent！= null）
（（AVLNode< T>）node.parent）.updateHeight（）;
} else {
rotateLeft（node.lesser）;
rotateRight（node）;
AVLNode< T> p =（AVLNode< T>）node.parent;
if（p.lesser！= null）
（（AVLNode< T））p.lesser）.updateHeight（）;
if（p.greater！= null）
（（AVLNode< T>）p.greater）.updateHeight（）;
p.updateHeight（）;
}
} else if（balanceFactor == 2）{
AVLNode< T> rr =（AVLNode< T>）node.greater.greater;
int greater =（rr！= null）？ rr.height：0;
AVLNode< T> rl =（AVLNode< T>）node.greater.lesser;
int lower =（rl！= null）？ rl.height：0;
if（greater> = lower）{
rotateLeft（node）;
node.updateHeight（）;
if（node.parent！= null）
（（AVLNode< T>）node.parent）.updateHeight（）;
} else {
rotateRight（node.greater）;
rotateLeft（node）;
AVLNode< T> p =（AVLNode< T>）node.parent;
if（p.lesser！= null）
（（AVLNode< T））p.lesser）.updateHeight（）;
if（p.greater！= null）
（（AVLNode< T>）p.greater）.updateHeight（）;
p.updateHeight（）;
}
}
}
}
/ **
* {@inheritDoc}
* /
@Override
protected boolean validateNode（Node< T>节点）{
boolean bst = super.validateNode（node）;
if（！bst）
return false;
AVLNode< T> avlNode =（AVLNode< T>）节点;
int balanceFactor = avlNode.getBalanceFactor（）;
if（balanceFactor> 1 || balanceFactor< -1）{
return false;
}
if（avlNode.isLeaf（））{
if（avlNode.height！= 1）
return false;
} else {
AVLNode< T> avlNodeLesser =（AVLNode< T>）avlNode.lesser;
int lowerHeight = 1;
if（avlNodeLesser！= null）
smallerHeight = avlNodeLesser.height;
AVLNode< T> avlNodeGreater =（AVLNode< T>）avlNode.greater;
int greaterHeight = 1;
if（avlNodeGreater！= null）
greaterHeight = avlNodeGreater.height;
if（avlNode.height ==（lowerHeight + 1）|| avlNode.height ==（greaterHeight + 1））{
return true;
} else {
return false;
}
}
返回true;
}
/ **
* {@inheritDoc}
* /
@Override
public String toString（）{
return AVLTreePrinter.getString（this）;
}
/ **
* {@inheritDoc}
* /
@Override
public Node< T> createNewNode（Node< T> parent，T id）{
return（new AVLNode< T>（parent，id））;
}
protected static class AVLNode< T extends Comparable< T>>扩展Node< T> {
protected int height = 1;
/ **
* AVL节点的构造方法
*
* @param parent
*树中的节点的父节点可以为NULL 。
* @param value
*树中节点的值。
* /
protected AVLNode（Node< T> parent，T value）{
super（parent，value）;
}
/ **
*确定这个节点是叶子（没有孩子）。
*
* @return如果此节点是叶子，则为真。
* /
protected boolean isLeaf（）{
return（（lower == null）&&（greater == null））;
}
/ **
*根据子节点更新此节点的高度。
* /
protected void updateHeight（）{
int smallerHeight = 0;
int greaterHeight = 0;
if（less！= null）{
AVLNode< T> lessAVLNode =（AVLNode< T>）较小;
smallerHeight = lessAVLNode.height;
}
if（greater！= null）{
AVLNode< T> greaterAVLNode =（AVLNode ）更大;
greaterHeight = greaterAVLNode.height;
}
if（lowerHeight> greaterHeight）{
height = minorHeight + 1;
} else {
height = greaterHeight + 1;
}
}
/ **
*获取此节点的平衡因子。
*
* @return表示此节点的平衡因子的整数。如果较小的分支长于
*更大的分支，则
*将为负数。
* /
protected int getBalanceFactor（）{
int smallerHeight = 0;
int greaterHeight = 0;
if（less！= null）{
AVLNode< T> lessAVLNode =（AVLNode< T>）较小;
smallerHeight = lessAVLNode.height;
}
if（greater！= null）{
AVLNode< T> greaterAVLNode =（AVLNode ）更大;
greaterHeight = greaterAVLNode.height;
}
return greaterHeight - smallerHeight;
}
/ **
* {@inheritDoc}
* /
@Override
public String toString（）{
返回value =+ id +height =+ height +parent =+（（parent！= null）？parent.id：NULL）
+lower =+ ！= null）？less.id：NULL）+greater =
+（（greater！= null）？greater.id：NULL）;
}
}
保护静态类AVLTreePrinter {
public static< T extends Comparable< T>> String getString（AVLTree< T> tree）{
if（tree.root == null）
返回Tree没有节点。
return getString（（AVLNode< T>）tree.root，，true）;
}
public static< T extends Comparable< T>> String getString（AVLNode< T>节点）{
if（node == null）
返回子树没有节点。
return getString（node，，true）;
}
private static< T extends Comparable< T>> String getString（AVLNode< T> node，String prefix，boolean isTail）{
StringBuilder builder = new StringBuilder（）;
builder.append（前缀+（isTail？└──：├──）+（+ node.height +）+ node.id +\\\
）;
列表< Node< T>> children = null;
if（node.lesser！= null || node.greater！= null）{
children = new ArrayList< Node>（2）;
if（node.lesser！= null）
children.add（node.lesser）;
if（node.greater！= null）
children.add（node.greater）;
}
if（children！= null）{
for（int i = 0; i< children.size（） - 1; i ++）{
builder.append getString（（AVLNode< T>）children.get（i），前缀+（isTail？：│），false））;
}
if（children.size（）> = 1）{
builder.append（getString（（AVLNode< T>）children.get（children.size（） ，前缀
+（isTail？：│），true））;
}
}
return builder.toString（）;
}
}
}
I want to implement an AVL Tree in Java, here is what I have so far:
public class AVLNode {
private int size; /** The size of the tree. */
private int height; /** The height of the tree. */
private Object key;/** The key of the current node. */
private Object data;/** The data of the current node. */
private Comparator comp;/** The {@link Comparator} used by the node. */
/* All the nodes pointed by the current node.*/
private AVLNode left,right,parent,succ,pred;
/* Instantiates a new AVL node.
*
* @param key the key of the node
* @param data the data that the node should keep
* @param comp the comparator to be used in the tree
*/
public AVLNode(Object key, Object data, Comparator comp) {
this(key,data,comp,null);
}
/* Instantiates a new AVL node.
*
* @param key the key of the node
* @param data the data that the node should keep
* @param comp the comparator to be used in the tree
* @param parent the parent of the created node
*/
public AVLNode(Object key, Object data, Comparator comp, AVLNode parent) {
this.data = data;
this.key = key;
this.comp = comp;
this.parent = parent;
this.left = null;
this.right = null;
this.succ = null;
this.pred = null;
this.size = 1;
this.height = 0;
}
/* Adds the given data to the tree.
*
* @param key the key
* @param data the data
* @return the root of the tree after insertion and rotations
* @author <b>students</b>
*/
public AVLNode add(Object key,Object data) {
return null;
}
/* Removes a Node which key is equal
* (by {@link Comparator}) to the given argument.
*
* @param key the key
* @return the root after deletion and rotations
* @author <b>students</b>
*/
public AVLNode remove(Object key) {
return null;
}
I need to implement the add and remove functions. Here is what I have so far, both should run in O(log(n)) time. Both should return the root of the whole tree:
/* Adds a new Node into the tree.
* @param key the key of the new node
* @param data the data of the new node
*/
public void add(Object key,Object data){
if (isEmpty()){
this.root = new AVLNode(key,data,comp);
}
else{
root = this.root.add(key,data);
}
}
/**
* Removes a node n from the tree where
* n.key is equal (by {@link Comparator}) to the given key.
*
* @param key the key
*/
public void remove(Object key){
if (isEmpty()){
return;
}
else
root = this.root.remove(key);
}
I need help on making the add and remove functions.
Is there any guide to describe how the add and remove operations work? A library to copy or something where I can figure out how/why AVL Trees work?
解决方案
You can try my AVL Tree which is linked here. Let me know if you have any additional questions.
Source in case the link goes down
package com.jwetherell.algorithms.data_structures;
import java.util.ArrayList;
import java.util.List;
/**
* An AVL tree is a self-balancing binary search tree, and it was the first such
* data structure to be invented. In an AVL tree, the heights of the two child
* subtrees of any node differ by at most one. AVL trees are often compared with
* red-black trees because they support the same set of operations and because
* red-black trees also take O(log n) time for the basic operations. Because AVL
* trees are more rigidly balanced, they are faster than red-black trees for
* lookup intensive applications. However, red-black trees are faster for
* insertion and removal.
*
* http://en.wikipedia.org/wiki/AVL_tree
*
* @author Justin Wetherell <phishman3579@gmail.com>
*/
public class AVLTree<T extends Comparable<T>> extends BinarySearchTree<T> implements BinarySearchTree.INodeCreator<T> {
private enum Balance {
LEFT_LEFT, LEFT_RIGHT, RIGHT_LEFT, RIGHT_RIGHT
};
/**
* Default constructor.
*/
public AVLTree() {
this.creator = this;
}
/**
* Constructor with external Node creator.
*/
public AVLTree(INodeCreator<T> creator) {
super(creator);
}
/**
* {@inheritDoc}
*/
@Override
protected Node<T> addValue(T id) {
Node<T> nodeToReturn = super.addValue(id);
AVLNode<T> nodeAdded = (AVLNode<T>) nodeToReturn;
while (nodeAdded != null) {
nodeAdded.updateHeight();
balanceAfterInsert(nodeAdded);
nodeAdded = (AVLNode<T>) nodeAdded.parent;
}
return nodeToReturn;
}
/**
* Balance the tree according to the AVL post-insert algorithm.
*
* @param node
* Root of tree to balance.
*/
private void balanceAfterInsert(AVLNode<T> node) {
int balanceFactor = node.getBalanceFactor();
if (balanceFactor > 1 || balanceFactor < -1) {
AVLNode<T> parent = null;
AVLNode<T> child = null;
Balance balance = null;
if (balanceFactor < 0) {
parent = (AVLNode<T>) node.lesser;
balanceFactor = parent.getBalanceFactor();
if (balanceFactor < 0) {
child = (AVLNode<T>) parent.lesser;
balance = Balance.LEFT_LEFT;
} else {
child = (AVLNode<T>) parent.greater;
balance = Balance.LEFT_RIGHT;
}
} else {
parent = (AVLNode<T>) node.greater;
balanceFactor = parent.getBalanceFactor();
if (balanceFactor < 0) {
child = (AVLNode<T>) parent.lesser;
balance = Balance.RIGHT_LEFT;
} else {
child = (AVLNode<T>) parent.greater;
balance = Balance.RIGHT_RIGHT;
}
}
if (balance == Balance.LEFT_RIGHT) {
// Left-Right (Left rotation, right rotation)
rotateLeft(parent);
rotateRight(node);
} else if (balance == Balance.RIGHT_LEFT) {
// Right-Left (Right rotation, left rotation)
rotateRight(parent);
rotateLeft(node);
} else if (balance == Balance.LEFT_LEFT) {
// Left-Left (Right rotation)
rotateRight(node);
} else {
// Right-Right (Left rotation)
rotateLeft(node);
}
node.updateHeight(); // New child node
child.updateHeight(); // New child node
parent.updateHeight(); // New Parent node
}
}
/**
* {@inheritDoc}
*/
@Override
protected Node<T> removeValue(T value) {
// Find node to remove
Node<T> nodeToRemoved = this.getNode(value);
if (nodeToRemoved != null) {
// Find the replacement node
Node<T> replacementNode = this.getReplacementNode(nodeToRemoved);
// Find the parent of the replacement node to re-factor the
// height/balance of the tree
AVLNode<T> nodeToRefactor = null;
if (replacementNode != null)
nodeToRefactor = (AVLNode<T>) replacementNode.parent;
if (nodeToRefactor == null)
nodeToRefactor = (AVLNode<T>) nodeToRemoved.parent;
if (nodeToRefactor != null && nodeToRefactor.equals(nodeToRemoved))
nodeToRefactor = (AVLNode<T>) replacementNode;
// Replace the node
replaceNodeWithNode(nodeToRemoved, replacementNode);
// Re-balance the tree all the way up the tree
if (nodeToRefactor != null) {
while (nodeToRefactor != null) {
nodeToRefactor.updateHeight();
balanceAfterDelete(nodeToRefactor);
nodeToRefactor = (AVLNode<T>) nodeToRefactor.parent;
}
}
}
return nodeToRemoved;
}
/**
* Balance the tree according to the AVL post-delete algorithm.
*
* @param node
* Root of tree to balance.
*/
private void balanceAfterDelete(AVLNode<T> node) {
int balanceFactor = node.getBalanceFactor();
if (balanceFactor == -2 || balanceFactor == 2) {
if (balanceFactor == -2) {
AVLNode<T> ll = (AVLNode<T>) node.lesser.lesser;
int lesser = (ll != null) ? ll.height : 0;
AVLNode<T> lr = (AVLNode<T>) node.lesser.greater;
int greater = (lr != null) ? lr.height : 0;
if (lesser >= greater) {
rotateRight(node);
node.updateHeight();
if (node.parent != null)
((AVLNode<T>) node.parent).updateHeight();
} else {
rotateLeft(node.lesser);
rotateRight(node);
AVLNode<T> p = (AVLNode<T>) node.parent;
if (p.lesser != null)
((AVLNode<T>) p.lesser).updateHeight();
if (p.greater != null)
((AVLNode<T>) p.greater).updateHeight();
p.updateHeight();
}
} else if (balanceFactor == 2) {
AVLNode<T> rr = (AVLNode<T>) node.greater.greater;
int greater = (rr != null) ? rr.height : 0;
AVLNode<T> rl = (AVLNode<T>) node.greater.lesser;
int lesser = (rl != null) ? rl.height : 0;
if (greater >= lesser) {
rotateLeft(node);
node.updateHeight();
if (node.parent != null)
((AVLNode<T>) node.parent).updateHeight();
} else {
rotateRight(node.greater);
rotateLeft(node);
AVLNode<T> p = (AVLNode<T>) node.parent;
if (p.lesser != null)
((AVLNode<T>) p.lesser).updateHeight();
if (p.greater != null)
((AVLNode<T>) p.greater).updateHeight();
p.updateHeight();
}
}
}
}
/**
* {@inheritDoc}
*/
@Override
protected boolean validateNode(Node<T> node) {
boolean bst = super.validateNode(node);
if (!bst)
return false;
AVLNode<T> avlNode = (AVLNode<T>) node;
int balanceFactor = avlNode.getBalanceFactor();
if (balanceFactor > 1 || balanceFactor < -1) {
return false;
}
if (avlNode.isLeaf()) {
if (avlNode.height != 1)
return false;
} else {
AVLNode<T> avlNodeLesser = (AVLNode<T>) avlNode.lesser;
int lesserHeight = 1;
if (avlNodeLesser != null)
lesserHeight = avlNodeLesser.height;
AVLNode<T> avlNodeGreater = (AVLNode<T>) avlNode.greater;
int greaterHeight = 1;
if (avlNodeGreater != null)
greaterHeight = avlNodeGreater.height;
if (avlNode.height == (lesserHeight + 1) || avlNode.height == (greaterHeight + 1)) {
return true;
} else {
return false;
}
}
return true;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return AVLTreePrinter.getString(this);
}
/**
* {@inheritDoc}
*/
@Override
public Node<T> createNewNode(Node<T> parent, T id) {
return (new AVLNode<T>(parent, id));
}
protected static class AVLNode<T extends Comparable<T>> extends Node<T> {
protected int height = 1;
/**
* Constructor for an AVL node
*
* @param parent
* Parent of the node in the tree, can be NULL.
* @param value
* Value of the node in the tree.
*/
protected AVLNode(Node<T> parent, T value) {
super(parent, value);
}
/**
* Determines is this node is a leaf (has no children).
*
* @return True if this node is a leaf.
*/
protected boolean isLeaf() {
return ((lesser == null) && (greater == null));
}
/**
* Updates the height of this node based on it's children.
*/
protected void updateHeight() {
int lesserHeight = 0;
int greaterHeight = 0;
if (lesser != null) {
AVLNode<T> lesserAVLNode = (AVLNode<T>) lesser;
lesserHeight = lesserAVLNode.height;
}
if (greater != null) {
AVLNode<T> greaterAVLNode = (AVLNode<T>) greater;
greaterHeight = greaterAVLNode.height;
}
if (lesserHeight > greaterHeight) {
height = lesserHeight + 1;
} else {
height = greaterHeight + 1;
}
}
/**
* Get the balance factor for this node.
*
* @return An integer representing the balance factor for this node. It
* will be negative if the lesser branch is longer than the
* greater branch.
*/
protected int getBalanceFactor() {
int lesserHeight = 0;
int greaterHeight = 0;
if (lesser != null) {
AVLNode<T> lesserAVLNode = (AVLNode<T>) lesser;
lesserHeight = lesserAVLNode.height;
}
if (greater != null) {
AVLNode<T> greaterAVLNode = (AVLNode<T>) greater;
greaterHeight = greaterAVLNode.height;
}
return greaterHeight - lesserHeight;
}
/**
* {@inheritDoc}
*/
@Override
public String toString() {
return "value=" + id + " height=" + height + " parent=" + ((parent != null) ? parent.id : "NULL")
+ " lesser=" + ((lesser != null) ? lesser.id : "NULL") + " greater="
+ ((greater != null) ? greater.id : "NULL");
}
}
protected static class AVLTreePrinter {
public static <T extends Comparable<T>> String getString(AVLTree<T> tree) {
if (tree.root == null)
return "Tree has no nodes.";
return getString((AVLNode<T>) tree.root, "", true);
}
public static <T extends Comparable<T>> String getString(AVLNode<T> node) {
if (node == null)
return "Sub-tree has no nodes.";
return getString(node, "", true);
}
private static <T extends Comparable<T>> String getString(AVLNode<T> node, String prefix, boolean isTail) {
StringBuilder builder = new StringBuilder();
builder.append(prefix + (isTail ? "└── " : "├── ") + "(" + node.height + ") " + node.id + "\n");
List<Node<T>> children = null;
if (node.lesser != null || node.greater != null) {
children = new ArrayList<Node<T>>(2);
if (node.lesser != null)
children.add(node.lesser);
if (node.greater != null)
children.add(node.greater);
}
if (children != null) {
for (int i = 0; i < children.size() - 1; i++) {
builder.append(getString((AVLNode<T>) children.get(i), prefix + (isTail ? " " : "│ "), false));
}
if (children.size() >= 1) {
builder.append(getString((AVLNode<T>) children.get(children.size() - 1), prefix
+ (isTail ? " " : "│ "), true));
}
}
return builder.toString();
}
}
}
这篇关于在JAVA中实现AVL树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
