AVL（平衡二叉樹(shù)）樹(shù)
平衡二叉樹(shù)是一種特殊的二叉搜索樹(shù)，他的左子樹(shù)與右子樹(shù)的高度差不超過(guò)1。并且左右兩個(gè)子樹(shù)都是一顆平衡二叉樹(shù)。保持平衡的特性使得平衡二叉樹(shù)的查詢(xún)、插入和刪除操作在平均和最壞情況下的時(shí)間復(fù)雜度都是
O(logn)，其中n是樹(shù)中節(jié)點(diǎn)的數(shù)量。 相比于普通的二叉搜索樹(shù)，平衡二叉樹(shù)更加適合處理動(dòng)態(tài)變化的數(shù)據(jù)集。 常見(jiàn)的平衡二叉樹(shù)有AVL樹(shù)、紅黑樹(shù)以及B樹(shù)等。這些樹(shù)結(jié)構(gòu)通過(guò)在插入或刪除節(jié)點(diǎn)時(shí)進(jìn)行特定的平衡操作來(lái)保持樹(shù)的平衡。
性質(zhì)
- 它的左右子樹(shù)都是AVL樹(shù)
- 左右子樹(shù)高度差不超過(guò)1
- 完全二叉樹(shù)是AVL樹(shù)，如果一棵樹(shù)是AVL樹(shù)，那么其高度可保持在
O(log2n)，搜索時(shí)間復(fù)雜度為O(log2n)
AVL樹(shù)的操作（Java）
首先創(chuàng)建節(jié)點(diǎn)用來(lái)保存樹(shù)中的節(jié)點(diǎn)的數(shù)據(jù)，其次和二叉搜索樹(shù)不同的是，AVL樹(shù)需要平衡因子來(lái)控制二叉樹(shù)的平衡。
節(jié)點(diǎn)的創(chuàng)建
private class Node {
int val;
Node left;
Node right;
int height;
public Node(int val) {
this.val = val;
this.left = this.right = null;
this.height = 1;
}
}
AVL樹(shù)的插入
插入操作和二叉搜索樹(shù)是相同的，但是在插入結(jié)束時(shí)會(huì)判斷AVL樹(shù)是否平衡。
// 向樹(shù)中添加節(jié)點(diǎn)
public void add(int val) {
if (contains(val)) {
return;
}
this.root = add(this.root, val);
this.size++;
}
// 向AVL樹(shù)中添加節(jié)點(diǎn)
private Node add(Node node, int val) {
// 遞歸到底的情況
if (node == null) {
return new Node(val);
}
if (node.val > val) {
node.left = add(node.left, val);
} else {
node.right = add(node.right, val);
}
// 更新節(jié)點(diǎn)高度
node.height = Math.max(getNodeHeight(node.left), getNodeHeight(node.right)) + 1;
// 維護(hù)平衡
int balance = getBalance(node);
if (balance > 1 && getBalance(node.left) >= 0) {
// 右旋
return rightRotate(node);
} else if (balance > 1 && getBalance(node.left) <= 0) {
// 左旋右旋
node.left = leftRotate(node.left);
return rightRotate(node);
} else if (balance < -1 && getBalance(node.right) >= 0) {
// 右旋左旋
node.right = rightRotate(node.right);
return leftRotate(node);
} else if (balance < -1 && getBalance(node.right) <= 0) {
// 左旋
return leftRotate(node);
}
return node;
}
1.判斷平衡
一個(gè)二叉樹(shù)是否是平衡的，根絕二叉樹(shù)的性質(zhì)可以知道，當(dāng)其左右子樹(shù)節(jié)點(diǎn)的高度差的絕對(duì)值不超過(guò)1時(shí)，這個(gè)二叉樹(shù)就是平衡二叉樹(shù)，當(dāng)其高度差絕對(duì)值超過(guò)1時(shí)，那么就是不平衡的二叉樹(shù)，就需要對(duì)二叉樹(shù)進(jìn)行平衡調(diào)整。
// 獲取當(dāng)前節(jié)點(diǎn)的平衡因子（左右子樹(shù)高度差）
private int getBalance(Node node) {
if (node == null) {
return 0;
}
return getNodeHeight(node.left) - getNodeHeight(node.right);
}
2.保持樹(shù)的平衡
當(dāng)判斷出一棵樹(shù)不平衡時(shí)，需要進(jìn)行平衡調(diào)整。
二叉樹(shù)一般出現(xiàn)不平衡的時(shí)候有四種狀態(tài)：
1. 左旋
根據(jù)上圖，我們可以直到，當(dāng)二叉樹(shù)的右樹(shù)的高度超過(guò)平衡時(shí)需要進(jìn)行左旋，左旋的方式是先將x節(jié)點(diǎn)的左子樹(shù)單獨(dú)定義出來(lái)為t2，然后將y節(jié)點(diǎn)連接到x的左子樹(shù)，將t2連接到y(tǒng)的右子樹(shù)上，這時(shí)就完成了左旋。
// 左旋轉(zhuǎn)
private Node leftRotate(Node y) {
Node x = y.right;
Node leftX = x.left;
x.left = y;
y.right = leftX;
y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
return x;
}
2. 右旋
右旋轉(zhuǎn)和左旋轉(zhuǎn)類(lèi)似，右旋的方式是先將x節(jié)點(diǎn)的右子樹(shù)單獨(dú)定義出來(lái)為t2，然后將y節(jié)點(diǎn)連接到x的右子樹(shù)，將t2連接到y(tǒng)的左子樹(shù)上，這時(shí)就完成了右旋。
// 右旋轉(zhuǎn)
private Node rightRotate(Node y) {
Node x = y.left;
Node rightX = x.right;
x.right = y;
y.left = rightX;
y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
return x;
}
3. 右旋+左旋
所謂右旋+左旋就是將右旋和左旋進(jìn)行連接，將這類(lèi)不平衡的樹(shù)進(jìn)行平衡
4. 左旋+右旋
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-522807.html
3.判斷是否AVL樹(shù)
判斷是否AVL樹(shù)就是判斷二叉樹(shù)的各個(gè)節(jié)點(diǎn)的平衡因子是否都是小于等于1或者大于等于-1。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-522807.html
// 判斷是否為平衡二叉樹(shù)
public boolean isBalanceTree() {
return isBalanceTree(this.root);
}
private boolean isBalanceTree(Node node) {
if (node == null) {
return true;
}
if (Math.abs(getBalance(node)) > 1) {
return false;
}
return isBalanceTree(node.left) && isBalanceTree(node.right);
}
// 獲取當(dāng)前節(jié)點(diǎn)的平衡因子（左右子樹(shù)高度差）
private int getBalance(Node node) {
if (node == null) {
return 0;
}
return getNodeHeight(node.left) - getNodeHeight(node.right);
}
4.刪除節(jié)點(diǎn)
// 刪除任意節(jié)點(diǎn)
public void remove(int val) {
boolean isExist = contains(val);
if (isExist) {
this.root = remove(this.root, val);
}
}
// 從以node為根的二分搜索樹(shù)中刪除值為val的結(jié)點(diǎn)
private Node remove(Node node, int val) {
Node resultNode = null;
if (node.val == val) {
// 葉子節(jié)點(diǎn)
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
this.size--;
resultNode = rightNode;
} else if (node.right == null) {
Node leftNode = node.left;
node.left = null;
this.size--;
resultNode = leftNode;
} else {
// 找出刪除節(jié)點(diǎn)的后繼
Node nextNode = getMinNode(node.right);
// 從右樹(shù)中刪除最小節(jié)點(diǎn)
nextNode.right = removeMinNode(node.right);
// 開(kāi)始連接
nextNode.left = node.left;
// 讓node失去關(guān)聯(lián)關(guān)系
node.left = node.right = null;
resultNode = nextNode;
}
} else if (node.val > val) {
node.left = remove(node.left, val);
resultNode = node;
} else {
node.right = remove(node.right, val);
resultNode = node;
}
// 刪除的是葉子節(jié)點(diǎn)
if (resultNode == null) {
return null;
}
// 刪除之后，可能改變了樹(shù)的平衡，因此需要進(jìn)行調(diào)整
resultNode.height = Math.max(getNodeHeight(resultNode.left), getNodeHeight(resultNode.right)) + 1;
Node result = resultNode;
if (getBalance(resultNode) > 1 && getBalance(resultNode.left) >= 0) {
result = rightRotate(resultNode);
} else if (getBalance(resultNode) < -1 && getBalance(resultNode.right) <= 0) {
result = leftRotate(resultNode);
} else if (getBalance(resultNode) > 1 && getBalance(resultNode.left) < 0) {
resultNode.left = leftRotate(resultNode.left);
result = rightRotate(resultNode);
} else if (getBalance(resultNode) < -1 && getBalance(resultNode.right) > 0) {
resultNode.right = rightRotate(resultNode.right);
result = leftRotate(resultNode);
}
return result;
}
全部代碼
import java.util.*;
public class AVLTree {
private Node root;
private int size;
public AVLTree() {
this.root = null;
this.size = 0;
}
// 判斷是否為空
public boolean isEmpty() {
return this.size == 0;
}
// 獲取樹(shù)中節(jié)點(diǎn)個(gè)數(shù)
public int getSize() {
return this.size;
}
// 獲取節(jié)點(diǎn)高度
public int getNodeHeight(Node node) {
if (node == null) {
return 0;
}
return node.height;
}
// 獲取當(dāng)前節(jié)點(diǎn)的平衡因子（左右子樹(shù)高度差）
private int getBalance(Node node) {
if (node == null) {
return 0;
}
return getNodeHeight(node.left) - getNodeHeight(node.right);
}
// 查找最小節(jié)點(diǎn)
public Node getMinNode() {
if (this.root == null) {
return null;
}
return getMinNode(this.root);
}
private Node getMinNode(Node node) {
if (node.left == null) {
return node;
}
return getMinNode(node.left);
}
// 判斷是否重復(fù)
public boolean contains(int val) {
return contains(this.root, val);
}
private boolean contains(Node node, int val) {
if (node == null) {
return false;
}
if (node.val == val) {
return true;
} else if (node.val > val) {
return contains(node.left, val);
} else {
return contains(node.right, val);
}
}
// 向樹(shù)中添加節(jié)點(diǎn)
public void add(int val) {
if (contains(val)) {
return;
}
this.root = add(this.root, val);
this.size++;
}
// 向AVL樹(shù)中添加節(jié)點(diǎn)
private Node add(Node node, int val) {
// 遞歸到底的情況
if (node == null) {
return new Node(val);
}
if (node.val > val) {
node.left = add(node.left, val);
} else {
node.right = add(node.right, val);
}
// 更新節(jié)點(diǎn)高度
node.height = Math.max(getNodeHeight(node.left), getNodeHeight(node.right)) + 1;
// 維護(hù)平衡
int balance = getBalance(node);
if (balance > 1 && getBalance(node.left) >= 0) {
// 右旋
return rightRotate(node);
} else if (balance > 1 && getBalance(node.left) <= 0) {
// 左旋右旋
node.left = leftRotate(node.left);
return rightRotate(node);
} else if (balance < -1 && getBalance(node.right) >= 0) {
// 右旋左旋
node.right = rightRotate(node.right);
return leftRotate(node);
} else if (balance < -1 && getBalance(node.right) <= 0) {
// 左旋
return leftRotate(node);
}
return node;
}
// 從二分搜索樹(shù)中刪除最小節(jié)點(diǎn)
public Node removeMinNode() {
if (this.root == null) {
return null;
}
Node result = getMinNode();
if (result != null) {
this.root = removeMinNode(this.root);
this.size--;
}
return result;
}
private Node removeMinNode(Node node) {
if (node.left == null) {
return node.right;
}
node.left = removeMinNode(node.left);
return node;
}
// 刪除任意節(jié)點(diǎn)
public void remove(int val) {
boolean isExist = contains(val);
if (isExist) {
this.root = remove(this.root, val);
}
}
// 從以node為根的二分搜索樹(shù)中刪除值為val的結(jié)點(diǎn)
private Node remove(Node node, int val) {
Node resultNode = null;
if (node.val == val) {
// 葉子節(jié)點(diǎn)
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
this.size--;
resultNode = rightNode;
} else if (node.right == null) {
Node leftNode = node.left;
node.left = null;
this.size--;
resultNode = leftNode;
} else {
// 找出刪除節(jié)點(diǎn)的后繼
Node nextNode = getMinNode(node.right);
// 從右樹(shù)中刪除最小節(jié)點(diǎn)
nextNode.right = removeMinNode(node.right);
// 開(kāi)始連接
nextNode.left = node.left;
// 讓node失去關(guān)聯(lián)關(guān)系
node.left = node.right = null;
resultNode = nextNode;
}
} else if (node.val > val) {
node.left = remove(node.left, val);
resultNode = node;
} else {
node.right = remove(node.right, val);
resultNode = node;
}
// 刪除的是葉子節(jié)點(diǎn)
if (resultNode == null) {
return null;
}
// 刪除之后，可能改變了樹(shù)的平衡，因此需要進(jìn)行調(diào)整
resultNode.height = Math.max(getNodeHeight(resultNode.left), getNodeHeight(resultNode.right)) + 1;
Node result = resultNode;
if (getBalance(resultNode) > 1 && getBalance(resultNode.left) >= 0) {
result = rightRotate(resultNode);
} else if (getBalance(resultNode) < -1 && getBalance(resultNode.right) <= 0) {
result = leftRotate(resultNode);
} else if (getBalance(resultNode) > 1 && getBalance(resultNode.left) < 0) {
resultNode.left = leftRotate(resultNode.left);
result = rightRotate(resultNode);
} else if (getBalance(resultNode) < -1 && getBalance(resultNode.right) > 0) {
resultNode.right = rightRotate(resultNode.right);
result = leftRotate(resultNode);
}
return result;
}
// 中序遍歷
public List<Integer> middleTravel() {
List<Integer> list = new ArrayList<>();
middleTravel(this.root, list);
return list;
}
private void middleTravel(Node node, List<Integer> list) {
if (node == null) {
return;
}
middleTravel(node.left, list);
list.add(node.val);
middleTravel(node.right, list);
}
// 層序遍歷
private List<Node> levelTravel() {
List<Node> list = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
if (this.root == null) {
return list;
}
queue.offer(this.root);
while (!queue.isEmpty()) {
Node node = queue.poll();
list.add(node);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return list;
}
// 判斷是否是二分搜索樹(shù)
public boolean isBinearySearchTree() {
List<Integer> list = middleTravel();
for (int i = 1; i < list.size(); i++) {
if (list.get(i - 1) > list.get(i)) {
return false;
}
}
return true;
}
// 判斷是否為平衡二叉樹(shù)
public boolean isBalanceTree() {
return isBalanceTree(this.root);
}
private boolean isBalanceTree(Node node) {
if (node == null) {
return true;
}
if (Math.abs(getBalance(node)) > 1) {
return false;
}
return isBalanceTree(node.left) && isBalanceTree(node.right);
}
// 右旋轉(zhuǎn)
private Node rightRotate(Node y) {
Node x = y.left;
Node rightX = x.right;
x.right = y;
y.left = rightX;
y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
return x;
}
// 左旋轉(zhuǎn)
private Node leftRotate(Node y) {
Node x = y.right;
Node leftX = x.left;
x.left = y;
y.right = leftX;
y.height = 1 + Math.max(getNodeHeight(y.left), getNodeHeight(y.right));
x.height = 1 + Math.max(getNodeHeight(x.left), getNodeHeight(x.right));
return x;
}
public String show() {
// 按層遍歷樹(shù)
List<Node> list = levelTravel();
String s = "";
for (int i = 0; i < list.size(); i++) {
s += "size = " + list.get(i).val + ", height = " + list.get(i).height + ", balance = " + getBalance(list.get(i)) + ";\n";
}
return s;
}
@Override
public String toString() {
// 按層遍歷樹(shù)
List<Node> list = levelTravel();
String s = "["+list.get(0).val;
for (int i = 1; i < list.size(); i++) {
s += "," + list.get(i).val;
}
s += "]";
return s;
}
private class Node {
int val;
Node left;
Node right;
int height;
public Node(int val) {
this.val = val;
this.left = this.right = null;
this.height = 1;
}
}
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
Random random = new Random();
for (int i = 0; i < 10; i++) {
avlTree.add(i);
avlTree.add(random.nextInt(100));
}
System.out.println(avlTree.toString());
// 判斷是否為平衡二叉樹(shù)
System.out.println(avlTree.isBalanceTree());
avlTree.removeMinNode();
System.out.println(avlTree.toString());
avlTree.remove(9);
System.out.println(avlTree.toString());
}
}
到了這里，關(guān)于計(jì)算機(jī)基礎(chǔ)---＞數(shù)據(jù)結(jié)構(gòu)（6）【AVL樹(shù)（平衡二叉樹(shù)）】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
