BST树与AVL树

抽象树结构定义

本文将介绍BST树与AVL树,树的数据结构是类似于链表,首先我们需要一个抽象类AbstractTree,该类里面定义了树节点的数据结构,以及完成树的先序、中序、后续遍历的代码模板,后面的BST与AVL树将继承这个抽象类;

首先我们定义树节点的数据结构,通过内部类定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* 树节点
*
* @param <k> key
* @param <v> value
*/
static class Node<k extends Comparable<k>, v> {

private k key;
private v value;
private Node left;
private Node right;
private int height;

public Node(k key, v value) {
this.key = key;
this.value = value;
}

//省略了get、set方法

@Override
public String toString() {
return "key:" + key + "," + "value:" + value;
}
}

然后完成树的先序、中序、后续遍历的模板代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* 先序遍历
*/
public void preOrder() {
preOrder(root);
}

private void preOrder(Node node) {
if (node == null)
return;
System.out.println(node);
preOrder(node.getLeft());
preOrder(node.getRight());
}

/**
* 中序遍历
*/
public void middleOrder() {
middleOrder(root);
}

private void middleOrder(Node node) {
if (node == null)
return;
middleOrder(node.getLeft());
System.out.println(node);
middleOrder(node.getRight());
}

/**
* 后序遍历
*/
public void postOrder() {
postOrder(root);
}

private void postOrder(Node node) {
if (node == null)
return;
postOrder(node.getLeft());
postOrder(node.getRight());
System.out.println(node);
}

对于树,我们需要写出它的添加节点、查找节点、删除节点方法,所以,我们在这个抽象类中添加添加节点、查找节点、删除节点的抽象方法交给子类具体的“树”去实现;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* 添加元素
*
* @param key
* @param value
*/
public abstract void add(k key, v value);

/**
* 查找元素
*
* @param key
* @return
*/
public abstract v get(k key);

/**
* 删除元素
*
* @param key
*/
public abstract void del(k key);

BST树

BST树介绍

BST全称为Binary Search Tree,即二叉搜索树;

一颗二叉树具有如下性质被称之为BST树:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 任意节点的左、右子树也分别为二叉查找树;
  • 没有键值相等的节点。

下图就是一颗典型的BST树:

BST树

BST树实现

首先需要继承之前的树的抽象类AbstractTree;

接下来实现BST树的添加节点、查找节点、删除节点方法;

添加节点

首先需要判断root节点是否已经初始化了,若没有初始化需要先初始化root节点;

当一个key-value需要被插入BST树时,首先判断key与节点的大小,若key大于节点的key值继续搜寻节点的右子树,若key小于节点的key值则继续搜寻节点的左子节点,直到找到某个节点的左子节点或者右子节点为空时,将需要插入的key-value插入;

非递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public void add(k key, v value) {
Node root = getRoot();
if (root == null) {
//root还未初始化
setRoot(new Node(key, value));
} else {
//root已经初始化
Node tmp = root;
while (tmp != null) {
//BST树插入节点都是叶子节点
int com = tmp.getKey().compareTo(key);
if (com == 0) {
//相等,替换value值并退出函数
tmp.setValue(value);
return;
}
else if (com > 0) {
//比tmp小,找左节点
if (tmp.getLeft() == null) {
//如果左节点为空,即为要插入位置
tmp.setLeft(new Node(key, value));
}
else {
//如果不为空继续找左节点
tmp = tmp.getLeft();
}
}
else if (com < 0) {
//比tmp大,找右节点
if (tmp.getRight() == null)
tmp.setRight(new Node(key, value));
else
tmp = tmp.getRight();
}
}
}
}

递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public Node add(Node node, k key, v value) {
if (node == null) {
return new Node(key, value);
}
int com = node.getKey().compareTo(key);
if (com == 0) {
node.setValue(value);
return node;
} else if (com > 0) {
node.setLeft(add(node.getLeft(), key, value));
} else if (com < 0) {
node.setRight(add(node.getRight(), key, value));
}
return node;
}

查找节点

查找结点比较容易,首先判断根节点是否为空,若为空则返回空,不为空比较key与节点的key大小,若key大于节点的key则继续查找节点的右节点,若key小于节点的key则继续查找节点的左节点,当key等于节点的key值时代表找到了,返回value即可;

非递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public v get(k key) {
Node root = getRoot();
Node tmp = root;
if (root == null) {
return null;
} else {
while (tmp != null) {
int com = tmp.getKey().compareTo(key);
if (com == 0) {
//相等,找到并返回
return (v) tmp.getValue();
}
else if (com > 0) {
//比tmp小,找左节点
tmp = tmp.getLeft();
}
else if (com < 0) {
//比tmp大,找右节点
tmp = tmp.getRight();
}
}
//未找到
return null;
}
}

递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
public Node get(Node node, k key) {
if (node == null) {
return null;
}
int com = node.getKey().compareTo(key);
if (com == 0) {
return node;
} else if (com > 0) {
return get(node.getLeft(), key);
} else {
return get(node.getRight(), key);
}
}

删除节点

删除节点相对较复杂,可分为如下几步:

  1. 首先找打需要删除节点和其父节点;
  2. 如果该节点为叶子节点,直接删除;
  3. 如果该节点只有左节点或者右节点,用该节点左节点或者右节点替代该节点;
  4. 如果该节点既有左节点又有右节点,用该节点右节点最小节点替代该节点并删除该节点右节点最小节点;

非递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public void del(k key) {
//1. 首先找打需要删除节点和其父节点
Node parent = getRoot();
Node delNode = parent;
//记录删除节点是父节点的左子节点还是右子节点
boolean left = false;
while (delNode != null) {
int com = delNode.getKey().compareTo(key);
if (com == 0) {
//找到要删除节点,跳出循环
break;
} else if (com > 0) {
//比tmp小,找左节点
parent = delNode;
delNode = delNode.getLeft();
left = true;
} else if (com < 0) {
//比tmp大找右节点
parent = delNode;
delNode = delNode.getRight();
left = false;
}
}
//跳出循环:1)找到要删除节点;2)没有找到,需要抛出异常
if (delNode == null || delNode.getKey().compareTo(key) != 0)
throw new RuntimeException("要删除节点不存在!");

//2. 如果该节点为叶子节点,直接删除
//3. 如果该节点只有左节点或者右节点,用该节点左节点或者右节点替代该节点
if (delNode.getRight() == null) {
if (left)
parent.setLeft(delNode.getLeft());
else
parent.setRight(delNode.getLeft());
} else if (delNode.getLeft() == null) {
if (left)
parent.setLeft(delNode.getRight());
else
parent.setRight(delNode.getRight());
} else {
//4. 如果该节点既有左节点又有右节点,用该节点右节点最小节点替代该节点并删除该节点右节点最小节点
Node min = getMin(delNode.getRight());
delNode.setKey(min.getKey());
delNode.setValue(min.getValue());
delNode.setRight(del(delNode.getRight(), (k) min.getKey()));
}
}

这里把查找某个节点的最小子节点封装起来了:

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 查找某个节点下的最小子节点
*
* @param node
* @return
*/
private Node getMin(Node node) {
if (node.getLeft() == null) {
return node;
}
return getMin(node.getLeft());
}

递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public Node del(Node node, k key) {
if (node == null) {
return null;
}
int com = node.getKey().compareTo(key);
if (com == 0) {
//找到要删除的节点
//如果该节点为叶子节点,直接删除
//如果该节点只有左节点或者右节点,用该节点左节点或者右节点替代该节点
if (node.getLeft() == null)
return node.getRight();
if (node.getRight() == null)
return node.getLeft();
Node min = getMin(node.getRight());
node.setKey(min.getKey());
node.setValue(min.getValue());
node.setRight(del(node.getRight(), (k) min.getKey()));
return node;
} else if (com > 0) {
//找左节点
node.setLeft(del(node.getLeft(), key));
} else {
//找右节点
node.setRight(del(node.getRight(), key));
}
return node;
}

AVL树

AVL树介绍

AVL树是一种自平衡二叉查找树,在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。

AVL树的平衡性与旋转

如下图所示的一棵树任何节点的两个子树的高度最大差别不超过1,是一颗AVL树:

AVL树

而对于这颗树而言,它的跟节点的左右子节点的高度差超过了1,所以不是一颗AVL树:

非AVL树

对于一个节点,当其为叶子节点时,其高度为0,当且为null时,高度为-1,所以我们可以封装一个获取节点高度的函数:

1
2
3
4
5
6
7
8
9
/**
* 获取节点高度
*
* @param node
* @return
*/
private int height(Node node) {
return node == null ? -1 : node.getHeight();
}

对于一个节点,其父节点的高度总是等于其左子节点与其右子节点最高高度加1;

而我们在插入和删除元素的时候总是会破坏一颗AVL树的平衡性的,对于被破坏了平衡性的AVL树需要通过旋转来维持它的平衡;

对于一个被破坏了平衡性的节点α而言,有四种旋转的方式:

符号描述 描述 旋转方式
LL 对α的左儿子的左子树进行一次插入 右旋
LR 对α的左儿子的右子树进行一次插入 先左旋再右旋
RL 对α的右儿子的左子树进行一次插入 先右旋再左旋
RR 对α的右儿子的右子树进行一次插入 左旋

LL右旋:

右旋

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 右旋
*
* @param node
*/
private Node rightRotate(Node node) {
Node left = node.getLeft();
node.setLeft(left.getRight());
left.setRight(node);
//旋转完需要重新计算node的高度
node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
left.setHeight(Math.max(height(left.getLeft()), height(left.getRight())) + 1);
return left;
}

RR左旋:

左旋

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* 左旋
*
* @param node
*/
private Node leftRotate(Node node) {
Node right = node.getRight();
node.setRight(right.getLeft());
right.setLeft(node);
//旋转完需要重新计算node的高度
node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
right.setHeight(Math.max(height(right.getLeft()), height(right.getLeft())) + 1);
return right;
}

LR先左旋再右旋:

先左旋再右旋

代码实现:

1
2
3
4
5
6
7
8
9
/**
* 先左旋再右旋
*
* @param node
*/
private Node leftAndRightRotate(Node node) {
node.setLeft(leftRotate(node.getLeft()));
return rightRotate(node);
}

RL先右旋再左旋:

先右旋再左旋

代码实现:

1
2
3
4
5
6
7
8
9
/**
* 先右旋再左旋
*
* @param node
*/
private Node rightAndLeftRotate(Node node) {
node.setRight(rightRotate(node.getRight()));
return leftRotate(node);
}

所以对于这四种情况,我们可以通过一个函数来解决:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 调整节点
*
* @param node
* @param key
* @return
*/
private Node adjust(Node node, k key) {
int balance = height(node.getLeft()) - height(node.getRight());
//LL
if (balance > 1 && node.getKey().compareTo(key) > 0) {
return rightRotate(node);
//LR
} else if (balance > 1 && node.getLeft().getKey().compareTo(key) < 0) {
return leftAndRightRotate(node);
//RR
} else if (balance < -1 && node.getKey().compareTo(key) < 0) {
return leftRotate(node);
//RL
} else if (balance < -1 && node.getLeft().getKey().compareTo(key) > 0) {
return rightAndLeftRotate(node);

}
return node;
}

AVL树实现

添加节点

添加节点可以再BST树递归实现的添加节点的代码基础上增加上旋转调整的代码来实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void add(k key, v value) {
setRoot(add(getRoot(), key, value));
}

private Node add(Node node, k key, v value) {
if (node == null) {
return new Node(key, value);
}
int com = node.getKey().compareTo(key);
if (com == 0) {
node.setValue(value);
return node;
} else if (com > 0) {
//左子树
node.setLeft(add(node.getLeft(), key, value));
} else if (com < 0) {
//右子树
node.setRight(add(node.getRight(), key, value));
}
//调整高度
node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
return adjust(node, key);
}

查找节点

查找节点的实现方式与BST树的查找方式完全一致,这里就不放代码了;

删除节点

删除节点的思路与BST树删除节点思路一致,不同的是,在删除一个节点后,需要重新计算其高度,并且判断其是否平衡,当其不平衡时,需要重新调整,使其平衡;值得注意的是,在删除完该节点右节点最小节点后,也需要重新计算这个最小节点的高度以及判断是否平衡,若不平衡也需要重新调整,使其平衡;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void del(k key) {
setRoot(del(getRoot(), key));
}

private Node del(Node node, k key) {
if (node == null) {
return null;
}
int com = node.getKey().compareTo(key);
if (com == 0) {
//找到要删除节点,删除
if (node.getLeft() == null)
return node.getRight();
if (node.getRight() == null)
return node.getLeft();
Node min = getMin(node.getRight());
node.setKey(min.getKey());
node.setValue(min.getValue());
node.setRight(del(node.getRight(), (k) min.getKey()));
} else if (com > 0) {
//在左子树上
node.setLeft(del(node.getLeft(), key));
} else {
//在右子树上
node.setRight(del(node.getRight(), key));
}
//调整高度
node.setHeight(Math.max(height(node.getLeft()), height(node.getRight())) + 1);
return adjust(node, key);
}

本文图片素材源自网络,如有侵权请告知,本人删除。

本文首发于我在万达摆地摊's blog,转载请注明来源