AVLTreeImpl (tiny-码云(gitee.com))

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()

Constructors
Constructor and Description
`AVLTreeImpl()`

Method Summary

All Methods Static Methods Instance Methods Concrete Methods Deprecated 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`	`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)` Deprecated.
`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()` 求出平衡二叉树中元素的个数

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
  - h
```
protected static <T extends Comparable<T>> int h(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> p)
```
    求指定节点的高度
    
    Type Parameters:
    
    T -
    
    Parameters:
    
    p -
    
    Returns:
  - 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
```
@Deprecated
protected void adjustLeftRigth(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor,
                                           org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted)
```
    Deprecated.
    
    已过期推荐使用adjustLeftRight 进行左-右旋转后平衡因子调整分三种情况
    
    Parameters:
    
    ancestor -
    
    inserted -
  - adjustLeftRight
```
protected void adjustLeftRight(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)
```
    已过期推荐使用adjustRightLeft 进行右-左旋转后平衡因子调整
    与adjustLeftRight方法一样，也有三种情况，这两个方法是对称的
    
    Parameters:
    
    ancestor -
    
    inserted -
  - adjustRightLeft
```
protected void adjustRightLeft(org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> ancestor,
                               org.tinygroup.binarytree.impl.AVLTreeImpl.Entry<T> inserted)
```
    进行右-左旋转后平衡因子调整
    与adjustLeftRight方法一样，也有三种情况，这两个方法是对称的
    
    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 - 被删除节点的祖先节点，从父节点向上迭代
  - 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>>

Class AVLTreeImpl<T extends Comparable<T>>

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

AVLTreeImpl

Method Detail

h

add

fixAfterInsertion

adjustPath

adjustLeftRigth

adjustLeftRight

adjustRigthLeft

adjustRightLeft

remove

contains

fixAfterDeletion

height

heightIter

iterator

size

add