org.tinygroup.binarytree.impl

Class AVLTreeImpl<T extends Comparable<T>>

java.lang.Object

org.tinygroup.binarytree.impl.AVLTreeImpl<T>

Type Parameters:

T -

All Implemented Interfaces:

AVLTree<T>

public class AVLTreeImpl<T extends Comparable<T>>
extends Object
implements AVLTree<T>

平衡二叉搜索（排序）树 此程序部分代码来自网上

Author:

luoguo

Constructor Summary

Constructors

Constructor and Description
AVLTreeImpl()

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(T elem) AVLTree类的add方法类似于BinSerrchTree类的add方法，但是沿着根向下前进到插入点时，需记录这样一个被插 入Entry对象最近的祖先：该祖先的平衡因子balanceFactor值是L或R(即不歼)，且让ancestor指向这个祖先节 点，该祖先节有什么用呢，从ancestor的子开始到新增节点路径上的所有祖先节点都是平衡，这些祖先节点会因为 新增节点而变得不平衡了，需要重新调整平衡因子，这个分界点在调整平衡因子时非常有用
boolean[]	add(T[] elem)
protected void	adjustLeftRigth(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor, org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted) 进行 左-右旋转 后平衡因子调整 分三种情况
protected void	adjustPath(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> to, org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted) 调整指定路径上的节点的平衡因子 注，指定的路径上的所有节点一定是平衡的，因此如果被插入元素小于某个祖先节点， 则这个祖先节点新的平衡因子是 L，反之为 R。
protected void	adjustRigthLeft(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor, org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted) 进行 右-左旋转 后平衡因子调整 与adjustLeftRigth方法一样，也有三种情况，这两个方法是对称的
T	contains(T o) 在平衡二叉树中获取一个元素
protected void	fixAfterDeletion(T elem, org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> pAncestor) 删除节点后平衡调整实现
protected void	fixAfterInsertion(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor, org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted) 当新增节点后，会改变某些节点的平衡因子，所以添加节点后需重新调整平衡因子 根据前人们的分析与研究，可分为6种情况
protected static <T extends Comparable<T>> int	h(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> p) 求指定节点的高度
int	height() 树的高度
int	heightIter() 树的高度非递归求法
Iterator<T>	iterator() 返回迭代器
boolean	remove(T elem) 删除指定节点
int	size() 求出平衡二叉树中元素的个数

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

AVLTreeImpl

public AVLTreeImpl()

Method Detail

add

public boolean add(T elem)

AVLTree类的add方法类似于BinSerrchTree类的add方法，但是沿着根向下前进到插入点时，需记录这样一个被插 入Entry对象最近的祖先：该祖先的平衡因子balanceFactor值是L或R(即不歼)，且让ancestor指向这个祖先节 点，该祖先节有什么用呢，从ancestor的子开始到新增节点路径上的所有祖先节点都是平衡，这些祖先节点会因为 新增节点而变得不平衡了，需要重新调整平衡因子，这个分界点在调整平衡因子时非常有用

Specified by:

add in interface AVLTree<T extends Comparable<T>>

Parameters:

elem - 要新增元素的数据域

Returns:

fixAfterInsertion

protected void fixAfterInsertion(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor,
                     org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted)

当新增节点后，会改变某些节点的平衡因子，所以添加节点后需重新调整平衡因子

根据前人们的分析与研究，可分为6种情况

Parameters:

ancestor - 新增元素的最近一个不平衡的祖先节点

inserted - 新增元素

adjustPath

protected void adjustPath(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> to,
              org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted)

调整指定路径上的节点的平衡因子

注，指定的路径上的所有节点一定是平衡的，因此如果被插入元素小于某个祖先节点， 则这个祖先节点新的平衡因子是 L，反之为 R。

Parameters:

inserted - 从哪里元素开始向上调整，但不包括该，即从父开始）

to - 直到哪个元素结束,但不包括该元素，一般传进来的为ancestor

adjustLeftRigth

protected void adjustLeftRigth(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor,
                   org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted)

进行 左-右旋转 后平衡因子调整 分三种情况

Parameters:

ancestor -

inserted -

adjustRigthLeft

protected void adjustRigthLeft(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor,
                   org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted)

进行 右-左旋转 后平衡因子调整

与adjustLeftRigth方法一样，也有三种情况，这两个方法是对称的

Parameters:

ancestor -

inserted -

remove

public boolean remove(T elem)

删除指定节点

Specified by:

remove in interface AVLTree<T extends Comparable<T>>

Parameters:

elem -

Returns:

boolean

contains

public T contains(T o)

Description copied from interface: AVLTree

在平衡二叉树中获取一个元素

Specified by:

contains in interface AVLTree<T extends Comparable<T>>

Parameters:

o - 通过compareTo比较为0即可的元素，不一定与二叉树中的元素完全相同

Returns:

返回在平衡二叉树中的与e通过compareTo比较为0的元素，如果找不到，则返回null

fixAfterDeletion

protected void fixAfterDeletion(T elem,
                    org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> pAncestor)

删除节点后平衡调整实现

Parameters:

elem - 被删除节点的数据域

ancestor - 被删除节点的祖先节点，从父节点向上迭代

h

protected static <T extends Comparable<T>> int h(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> p)

求指定节点的高度

Type Parameters:

T -

Parameters:

p -

Returns:

height

public int height()

树的高度

Specified by:

height in interface AVLTree<T extends Comparable<T>>

Returns:

heightIter

public int heightIter()

Description copied from interface: AVLTree

树的高度非递归求法

Specified by:

heightIter in interface AVLTree<T extends Comparable<T>>

Returns:

iterator

public Iterator<T> iterator()

Description copied from interface: AVLTree

返回迭代器

Specified by:

iterator in interface AVLTree<T extends Comparable<T>>

Returns:

size

public int size()

Description copied from interface: AVLTree

求出平衡二叉树中元素的个数

Specified by:

size in interface AVLTree<T extends Comparable<T>>

Returns:

add

public boolean[] add(T[] elem)

Specified by:

add in interface AVLTree<T extends Comparable<T>>