org.tinygroup.binarytree.impl
类 AVLTreeImpl<T extends Comparable<T>>

java.lang.Object
  org.tinygroup.binarytree.impl.AVLTreeImpl<T>

类型参数：

T -

所有已实现的接口：

AVLTree<T>

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

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

作者：

luoguo

构造方法摘要

AVLTreeImpl()

方法摘要

boolean	add(T elem) AVLTree类的add方法类似于BinSerrchTree类的add方法，但是沿着根向下前进到插入点时，需记录这样一个被插 入Entry对象最近的祖先：该祖先的平衡因子balanceFactor值是L或R(即不歼)，且让ancestor指向这个祖先节 点，该祖先节有什么用呢，从ancestor的子开始到新增节点路径上的所有祖先节点都是平衡，这些祖先节点会因为 新增节点而变得不平衡了，需要重新调整平衡因子，这个分界点在调整平衡因子时非常有用
boolean[]	add(T[] elem)
protected void	adjustLeftRight(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor, org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted) 进行 左-右旋转 后平衡因子调整 分三种情况
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	adjustRightLeft(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor, org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted) 进行 右-左旋转 后平衡因子调整 与adjustLeftRight方法一样，也有三种情况，这两个方法是对称的
protected void	adjustRigthLeft(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor, org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted) 已过期 推荐使用adjustRightLeft 进行 右-左旋转 后平衡因子调整 与adjustLeftRight方法一样，也有三种情况，这两个方法是对称的
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() 求出平衡二叉树中元素的个数

从类 java.lang.Object 继承的方法

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

构造方法详细信息

AVLTreeImpl

public AVLTreeImpl()

方法详细信息

add

public boolean add(T elem)

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

指定者：

接口 AVLTree<T extends Comparable<T>> 中的 add

参数：

elem - 要新增元素的数据域

返回：

fixAfterInsertion

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

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

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

参数：

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

inserted - 新增元素

adjustPath

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

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

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

参数：

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

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

adjustLeftRigth

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

已过时。

已过期 推荐使用adjustLeftRight 进行 左-右旋转 后平衡因子调整 分三种情况

参数：

ancestor -

inserted -

adjustLeftRight

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

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

参数：

ancestor -

inserted -

adjustRigthLeft

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

已过期 推荐使用adjustRightLeft 进行 右-左旋转 后平衡因子调整

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

参数：

ancestor -

inserted -

adjustRightLeft

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

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

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

参数：

ancestor -

inserted -

remove

public boolean remove(T elem)

删除指定节点

指定者：

接口 AVLTree<T extends Comparable<T>> 中的 remove

参数：

elem -

返回：

boolean

contains

public T contains(T o)

从接口 AVLTree 复制的描述

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

指定者：

接口 AVLTree<T extends Comparable<T>> 中的 contains

参数：

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

返回：

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

fixAfterDeletion

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

删除节点后平衡调整实现

参数：

elem - 被删除节点的数据域

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

h

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

求指定节点的高度

类型参数：

T -

参数：

p -

返回：

height

public int height()

树的高度

指定者：

接口 AVLTree<T extends Comparable<T>> 中的 height

返回：

heightIter

public int heightIter()

从接口 AVLTree 复制的描述

树的高度非递归求法

指定者：

接口 AVLTree<T extends Comparable<T>> 中的 heightIter

返回：

iterator

public Iterator<T> iterator()

从接口 AVLTree 复制的描述

返回迭代器

指定者：

接口 AVLTree<T extends Comparable<T>> 中的 iterator

返回：

size

public int size()

从接口 AVLTree 复制的描述

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

指定者：

接口 AVLTree<T extends Comparable<T>> 中的 size

返回：

add

public boolean[] add(T[] elem)

指定者：

接口 AVLTree<T extends Comparable<T>> 中的 add