平衡二叉树AVLTree手写实现（Java）
2021-07-31 本文已影响0人
aruba
定义节点：
//平衡因子 左树深度多
public static final int LH = 1;
//平衡因子 右数深度多
public static final int RH = -1;
//平衡因子 左右树深度相同
public static final int EH = 0;
class AVLNode<T> {
T value;
AVLNode<T> leftChild;
AVLNode<T> rightChild;
AVLNode<T> parent;
int balance = EH;
}
实现左旋方法：
左旋.jpg
/**
* 节点左旋
* // 转换前：
* // |
* // a <-
* // / \
* // b c
* // / \
* // z h
* //
* // 转换后：
* //
* // |
* // c
* // / \
* // -> a h
* // / \
* // b z
*/
private void leftRotate(AVLNode<T> a) {
AVLNode<T> c = a.rightChild;
//1.a的父节点的孩子指向c，c的父节点变为a的父节点
if (a.parent == null) {//根节点,即a没有父节点
root = c;
} else if (a.parent.leftChild == a) {//a是左孩子
a.parent.leftChild = c;
} else {//a是右孩子
a.parent.rightChild = c;
}
//c的父节点变为a的父节点
c.parent = a.parent;
//2.a的右孩子变为z
AVLNode<T> z = c.leftChild;
a.rightChild = z;
//z父节点指向a
if (z != null)
z.parent = a;
//3.c的左孩子变为a，a的父节点指向c
c.leftChild = a;
//a的父节点指向c
a.parent = c;
}
实现右旋方法：
右旋.jpg
/**
* 节点右旋
* // 转换前：
* // |
* // a <-
* // / \
* // b c
* // / \
* // z h
* //
* // 转换后：
* //
* // |
* // b
* // / \
* // z a <-
* // / \
* // h c
*/
private void rightRotate(AVLNode<T> a) {
AVLNode<T> b = a.leftChild;
//1.b的父节点变为a的父节点，a的父节点的孩子变为b
b.parent = a.parent;
//a的父节点的孩子变为b
if (a.parent == null) {//根节点,即a没有父节点
root = b;
} else if (a.parent.leftChild == a) {//a是左孩子
a.parent.leftChild = b;
} else {
a.parent.rightChild = b;
}
//2.a的左孩子变为h,h父节点指向a
AVLNode<T> h = b.rightChild;
a.leftChild = b.leftChild;
if (h != null) {
h.parent = a;
}
//3.b的右孩子指向a，a的父节点变为b
b.rightChild = a;
//a的父节点变为b
a.parent = b;
}
实现左平衡和右平衡：
/**
* 右平衡
*/
public void rightBalance(AVLNode<T> t) {
AVLNode<T> tr = t.rightChild;
switch (tr.balance) {
case RH:
// 1、如果新的结点插入到t的右孩子的右子树中，则直接进行左旋操作即可
// t tr
// / \ / \
// l tr 左旋操作 t trr
// / \ -----------> / \ / \
// trl trr l trl rrl rrr
// / \
// rrl rrr <----插入rrl或rrr
leftRotate(t);
t.balance = EH;
tr.balance = EH;
//trr平衡因子不变
break;
case LH://2、如果新的结点插入到p的右孩子的左子树中，则需要进行分情况讨论
switch (tr.leftChild.balance) {
case LH: //情况a：当p的右孩子的左子树根节点的balance = LEFT_HIGH
// t t trl
// / \ / \ / \
// 2 tr tr右旋 2 trl t左旋 t tr
// / \ -------> / \ -------> / \ \
// trl 5 6 tr 2 6 5
// / \
// 6 <----插入 5
t.balance = EH;
tr.balance = RH;
tr.leftChild.balance = EH;
break;
case RH://情况b：当p的右孩子的左子树根节点的balance = RIGHT_HIGH
// t t trl
// / \ / \ / \
// 2 tr tr右旋 2 trl t左旋 t tr
// / \ -------> \ -------> / / \
// trl 5 tr 2 6 5
// \ / \
// 6 <----插入 6 5
t.balance = LH;
tr.balance = EH;
tr.leftChild.balance = EH;
break;
case EH://情况C：当p的右孩子的左子树根节点的balance = EQUAL_HIGH
// t t trl
// \ \ / \
// tr tr右旋 trl t左旋 t tr
// / -------> \ ------->
// trl <----插入 tr
t.balance = EH;
tr.balance = EH;
tr.leftChild.balance = EH;
break;
}
rightRotate(t.rightChild);
leftRotate(t);
break;
case EH:
break;
}
}
/**
* 左平衡
*/
public void leftBalance(AVLNode<T> t) {
AVLNode<T> tl = t.leftChild;
switch (tl.balance) {
case LH://1、如果新的结点插入到t的左孩子的左子树中，则直接进行右旋操作即可
// t tl
// / \ t右旋操作 / \
// tl tr -------------> tll t
// / \ / \ / \
// tll tlr lcll lclr tlr tr
// / \
// lcll lclr <----插入lcll或lclr
rightRotate(t);
t.balance = EH;
tl.balance = EH;
//tll平衡因子不变
break;
case RH://2、如果新的结点插入到t的左孩子的右子树中，则需要进行分情况讨论
switch (tl.rightChild.balance) {
case RH://情况a：当t的左孩子的右子树根节点的balance = RIGHT_HIGH
// t t tlr
// / \ / \ / \
// tl 6 tl左旋 tlr 6 t右旋 tl t
// / \ -------> / \ --------> / / \
// 3 tlr tl 5 3 5 6
// \ /
// 5 <----插入 3
t.balance = EH;
tl.balance = LH;
tl.rightChild.balance = EH;
break;
case LH://情况b：当t的左孩子的右子树根节点的balance = LEFT_HIGH
// t t tlr
// / \ / \ / \
// tl 6 tl左旋 tlr 6 t右旋 tl t
// / \ -------> / --------> / \ \
// 3 tlr tl 3 5 6
// / / \
// 5 <----插入 3 5
t.balance = RH;
tl.balance = EH;
tl.rightChild.balance = EH;
break;
case EH://情况c：当t的左孩子的右子树根节点的balance = EQUAL_HIGH
// t t tlr
// / / / \
// tl tl左旋 tlr t右旋 tl t
// \ -------> / -------->
// tlr <----插入 tl
t.balance = EH;
tl.balance = EH;
tl.rightChild.balance = EH;
break;
}
leftRotate(t.leftChild);
rightRotate(t);
break;
case EH:
break;
}
}
实现插入元素：
/**
* 插入元素
* @param value
*/
public void insertNode(T value) {
if (root == null) {//没有元素
root = new AVLNode<>(value, null, null, null);
} else {
Comparable e = value;
AVLNode<T> head = root;
AVLNode<T> parent = null;
int cmp = 0;
while (head != null) {
cmp = e.compareTo(head.value);
parent = head;
if (cmp == 0) {
return;
} else if (cmp > 0) {//往右子树偏移
head = head.rightChild;
} else {
head = head.leftChild;
}
}
if (cmp > 0) {//往右子树插入节点
parent.rightChild = new AVLNode<>(value, null, null, parent);
} else {
parent.leftChild = new AVLNode<>(value, null, null, parent);
}
//平衡因子调整
while (parent != null) {
if (e.compareTo(parent.value) > 0) {//右子树多了深度
parent.balance--;
} else {
parent.balance++;
}
if(parent.balance == 0){//插入后正好平衡了，不用处理了
break;
}
if (Math.abs(parent.balance) == 2) {//不平衡了
//根据平衡因子进行旋转操作
calcBalance(parent);
break;
} else {//继续往上找父亲，调整平衡因子
parent = parent.parent;
}
}
}
size++;
}
/**
* 处理平衡问题
* @param parent
*/
private void calcBalance(AVLNode<T> parent) {
if (parent.balance == -2) {//右子树多了
rightBalance(parent);
} else {
leftBalance(parent);
}
}
完整代码：
/**
* 平衡二叉树
*/
public static class AVLTree<T extends Comparable<T>> {
//平衡因子 左树深度多
public static final int LH = 1;
//平衡因子 右数深度多
public static final int RH = -1;
//平衡因子 左右树深度相同
public static final int EH = 0;
//根节点
AVLNode<T> root;
//元素个数
private int size = 0;
public AVLTree() {
}
public AVLTree(AVLNode<T> root) {
this.root = root;
}
/**
* 节点左旋
* // 转换前：
* // |
* // a <-
* // / \
* // b c
* // / \
* // z h
* //
* // 转换后：
* //
* // |
* // c
* // / \
* // -> a h
* // / \
* // b z
*/
private void leftRotate(AVLNode<T> a) {
AVLNode<T> c = a.rightChild;
//1.a的父节点的孩子指向c，c的父节点变为a的父节点
if (a.parent == null) {//根节点,即a没有父节点
root = c;
} else if (a.parent.leftChild == a) {//a是左孩子
a.parent.leftChild = c;
} else {//a是右孩子
a.parent.rightChild = c;
}
//c的父节点变为a的父节点
c.parent = a.parent;
//2.a的右孩子变为z
AVLNode<T> z = c.leftChild;
a.rightChild = z;
//z父节点指向a
if (z != null)
z.parent = a;
//3.c的左孩子变为a，a的父节点指向c
c.leftChild = a;
//a的父节点指向c
a.parent = c;
}
/**
* 节点右旋
* // 转换前：
* // |
* // a <-
* // / \
* // b c
* // / \
* // z h
* //
* // 转换后：
* //
* // |
* // b
* // / \
* // z a <-
* // / \
* // h c
*/
private void rightRotate(AVLNode<T> a) {
AVLNode<T> b = a.leftChild;
//1.b的父节点变为a的父节点，a的父节点的孩子变为b
b.parent = a.parent;
//a的父节点的孩子变为b
if (a.parent == null) {//根节点,即a没有父节点
root = b;
} else if (a.parent.leftChild == a) {//a是左孩子
a.parent.leftChild = b;
} else {
a.parent.rightChild = b;
}
//2.a的左孩子变为h,h父节点指向a
AVLNode<T> h = b.rightChild;
a.leftChild = b.leftChild;
if (h != null) {
h.parent = a;
}
//3.b的右孩子指向a，a的父节点变为b
b.rightChild = a;
//a的父节点变为b
a.parent = b;
}
/**
* 右平衡
*/
public void rightBalance(AVLNode<T> t) {
AVLNode<T> tr = t.rightChild;
switch (tr.balance) {
case RH:
// 1、如果新的结点插入到t的右孩子的右子树中，则直接进行左旋操作即可
// t tr
// / \ / \
// l tr 左旋操作 t trr
// / \ -----------> / \ / \
// trl trr l trl rrl rrr
// / \
// rrl rrr <----插入rrl或rrr
leftRotate(t);
t.balance = EH;
tr.balance = EH;
//trr平衡因子不变
break;
case LH://2、如果新的结点插入到p的右孩子的左子树中，则需要进行分情况讨论
switch (tr.leftChild.balance) {
case LH: //情况a：当p的右孩子的左子树根节点的balance = LEFT_HIGH
// t t trl
// / \ / \ / \
// 2 tr tr右旋 2 trl t左旋 t tr
// / \ -------> / \ -------> / \ \
// trl 5 6 tr 2 6 5
// / \
// 6 <----插入 5
t.balance = EH;
tr.balance = RH;
tr.leftChild.balance = EH;
break;
case RH://情况b：当p的右孩子的左子树根节点的balance = RIGHT_HIGH
// t t trl
// / \ / \ / \
// 2 tr tr右旋 2 trl t左旋 t tr
// / \ -------> \ -------> / / \
// trl 5 tr 2 6 5
// \ / \
// 6 <----插入 6 5
t.balance = LH;
tr.balance = EH;
tr.leftChild.balance = EH;
break;
case EH://情况C：当p的右孩子的左子树根节点的balance = EQUAL_HIGH
// t t trl
// \ \ / \
// tr tr右旋 trl t左旋 t tr
// / -------> \ ------->
// trl <----插入 tr
t.balance = EH;
tr.balance = EH;
tr.leftChild.balance = EH;
break;
}
rightRotate(t.rightChild);
leftRotate(t);
break;
case EH:
break;
}
}
/**
* 左平衡
*/
public void leftBalance(AVLNode<T> t) {
AVLNode<T> tl = t.leftChild;
switch (tl.balance) {
case LH://1、如果新的结点插入到t的左孩子的左子树中，则直接进行右旋操作即可
// t tl
// / \ t右旋操作 / \
// tl tr -------------> tll t
// / \ / \ / \
// tll tlr lcll lclr tlr tr
// / \
// lcll lclr <----插入lcll或lclr
rightRotate(t);
t.balance = EH;
tl.balance = EH;
//tll平衡因子不变
break;
case RH://2、如果新的结点插入到t的左孩子的右子树中，则需要进行分情况讨论
switch (tl.rightChild.balance) {
case RH://情况a：当t的左孩子的右子树根节点的balance = RIGHT_HIGH
// t t tlr
// / \ / \ / \
// tl 6 tl左旋 tlr 6 t右旋 tl t
// / \ -------> / \ --------> / / \
// 3 tlr tl 5 3 5 6
// \ /
// 5 <----插入 3
t.balance = EH;
tl.balance = LH;
tl.rightChild.balance = EH;
break;
case LH://情况b：当t的左孩子的右子树根节点的balance = LEFT_HIGH
// t t tlr
// / \ / \ / \
// tl 6 tl左旋 tlr 6 t右旋 tl t
// / \ -------> / --------> / \ \
// 3 tlr tl 3 5 6
// / / \
// 5 <----插入 3 5
t.balance = RH;
tl.balance = EH;
tl.rightChild.balance = EH;
break;
case EH://情况c：当t的左孩子的右子树根节点的balance = EQUAL_HIGH
// t t tlr
// / / / \
// tl tl左旋 tlr t右旋 tl t
// \ -------> / -------->
// tlr <----插入 tl
t.balance = EH;
tl.balance = EH;
tl.rightChild.balance = EH;
break;
}
leftRotate(t.leftChild);
rightRotate(t);
break;
case EH:
break;
}
}
/**
* 插入元素
* @param value
*/
public void insertNode(T value) {
if (root == null) {//没有元素
root = new AVLNode<>(value, null, null, null);
} else {
Comparable e = value;
AVLNode<T> head = root;
AVLNode<T> parent = null;
int cmp = 0;
while (head != null) {
cmp = e.compareTo(head.value);
parent = head;
if (cmp == 0) {
return;
} else if (cmp > 0) {//往右子树偏移
head = head.rightChild;
} else {
head = head.leftChild;
}
}
if (cmp > 0) {//往右子树插入节点
parent.rightChild = new AVLNode<>(value, null, null, parent);
} else {
parent.leftChild = new AVLNode<>(value, null, null, parent);
}
//平衡因子调整
while (parent != null) {
if (e.compareTo(parent.value) > 0) {//右子树多了深度
parent.balance--;
} else {
parent.balance++;
}
if(parent.balance == 0){//插入后正好平衡了，不用处理了
break;
}
if (Math.abs(parent.balance) == 2) {//不平衡了
//根据平衡因子进行旋转操作
calcBalance(parent);
break;
} else {//继续往上找父亲，调整平衡因子
parent = parent.parent;
}
}
}
size++;
}
/**
* 处理平衡问题
* @param parent
*/
private void calcBalance(AVLNode<T> parent) {
if (parent.balance == -2) {//右子树多了
rightBalance(parent);
} else {
leftBalance(parent);
}
}
class AVLNode<T> {
T value;
AVLNode<T> leftChild;
AVLNode<T> rightChild;
AVLNode<T> parent;
//平衡因子
int balance = EH;
public AVLNode(T value, AVLNode<T> leftChild, AVLNode<T> rightChild, AVLNode<T> parent) {
this.value = value;
this.leftChild = leftChild;
this.rightChild = rightChild;
this.parent = parent;
}
}
}
测试输出：
public static void main(String args[]) {
AVLTree<Integer> avlTree = new AVLTree();
avlTree.insertNode(5);
avlTree.insertNode(-1);
avlTree.insertNode(6);
avlTree.insertNode(4);
avlTree.insertNode(2);
avlTree.insertNode(7);
avlTree.insertNode(0);
dfs(avlTree);
}
private static void dfs(AVLTree<Integer> avlTree) {
Deque<AVLTree.AVLNode> deque = new LinkedList<>();
if (avlTree.root != null) {
deque.offer(avlTree.root);
}
while (!deque.isEmpty()) {
int size = deque.size();
while (size > 0) {
AVLTree.AVLNode node = deque.poll();
System.out.print(node.value + " ");
if (node.leftChild != null) {
deque.offer(node.leftChild);
}
if (node.rightChild != null) {
deque.offer(node.rightChild);
}
size--;
}
System.out.println();
}
}
结果：
5
2 6
-1 4 7
0
