一、AVL樹
1.添加可能會導致失衡
2.解決失衡
(首先出現(xiàn)失衡的節(jié)點g)代表祖父節(jié)點汽绢； p 代表父節(jié)點吗跋； n代表當前節(jié)點；T0/T1/T2......代表的是一塊不確定的子節(jié)點宁昭，添加一個(紅顏色)節(jié)點后會導致從g點開始失衡
第一種情況- LL : LL代表g節(jié)點的左子節(jié)點p的左子節(jié)點
- 解決辦法：對g右旋轉
第二種情況-RR : RR代表g節(jié)點的右子節(jié)點p的右子節(jié)點n
- 解決辦法：對g左旋轉
第三種情況-LR : LR代表g節(jié)點的左子節(jié)點p的右子節(jié)點n
- 解決辦法：先對p左旋轉，然后再對g右旋轉
第四種情況-RL : RL代表g節(jié)點的右子節(jié)點p的左子節(jié)點n
- 解決辦法：先對p右旋轉积仗，然后再對g左旋轉
完整代碼如下：
- BinaryTree(二叉樹)
//二叉樹
package com.weyan.tree;
import java.util.LinkedList;
import java.util.Queue;
import com.weyan.printer.BinaryTreeInfo;
public class BinaryTree<E> implements BinaryTreeInfo {
protected int size;
// 根節(jié)點
protected Node<E> root;
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
root = null;
size = 0;
}
// 前序遍歷（遞歸方法）
public void preorderTraversal() {
preorderTraversal(root);
}
private void preorderTraversal(Node<E> node) {
if (node == null)
return;
System.out.println(node.element);
preorderTraversal(node.left);
preorderTraversal(node.right);
}
// 中序遍歷（遞歸方法）
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if (node == null)
return;
preorderTraversal(node.left);
System.out.println(node.element);
preorderTraversal(node.right);
}
// 后序遍歷（遞歸方法）
public void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<E> node) {
if (node == null)
return;
preorderTraversal(node.left);
preorderTraversal(node.right);
System.out.println(node.element);
}
// 層序遍歷(通過鏈表實現(xiàn))
public void levelorderTraversal() {
if (root == null)
return;
Queue<Node<E>> queue = new LinkedList<>();
// 入隊
queue.offer(root);
while (!queue.isEmpty()) {
// 出隊
Node<E> node = queue.poll();
System.out.println(node.element);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
/*
* 使用自定義打印器 需要實現(xiàn)以下幾個方法
*
*/
@Override
public Object root() {
// TODO Auto-generated method stub
return root;
}
@SuppressWarnings("unchecked")
@Override
public Object left(Object node) {
// TODO Auto-generated method stub
return ((Node<E>) node).left;
}
@SuppressWarnings("unchecked")
@Override
public Object right(Object node) {
// TODO Auto-generated method stub
return ((Node<E>) node).right;
}
@SuppressWarnings("unchecked")
@Override
public Object string(Object node) {
// TODO Auto-generated method stub
// 打印出parent
Node<E> myNode = (Node<E>) node;
String parentString = "null";
if (myNode.parent != null) {
parentString = myNode.parent.element.toString();
}
return myNode.element + "_(" + parentString + ")";
}
// 前驅節(jié)點
protected Node<E> predecessor(Node<E> node) {
if (node == null)
return null;
// 前驅節(jié)點在左子樹當中（left.right.right.........）
Node<E> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 從父節(jié)點疆拘、祖父節(jié)點當中去找前驅節(jié)點
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
// node.parent == null && node.left == null
return node.parent;
}
// 后繼節(jié)點
protected Node<E> successor(Node<E> node) {
if (node == null)
return null;
// 前驅節(jié)點在左子樹當中（right.left.left.........）
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 從父節(jié)點、祖父節(jié)點當中去找前驅節(jié)點
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
// node.parent == null && node.right == null
return node.parent;
}
protected Node<E> createNode(E element, Node<E> parent) {
return new Node<>(element, parent);
}
/** ---遞歸寫法--- **/
// 二叉樹的高度
// public int height() {
// return nodeHeight(root);
// }
// 節(jié)點高度
// private int nodeHeight(Node<E> node) {
// if (node == null) return 0;
// return 1 + Math.max(nodeHeight(node.left), nodeHeight(node.right));
// }
/** ---層序遍歷寫法--- **/
// 二叉樹的高度
public int height() {
if (root == null)
return 0;
int height = 0;
// 存儲著每一層的元素數(shù)量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize--;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (levelSize == 0) {// 意味著即將要訪問下一層
levelSize = queue.size();
height++;
}
}
return height;
}
/// 判斷一棵樹是否為完全二叉樹
public boolean isComplete() {
if (root == null)
return false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (leaf && !node.isLeaf())
return false;
if (node.left != null) {
queue.offer(node.left);
} else if (node.right != null) {
return false;
}
if (node.right != null) {
queue.offer(node.right);
} else {
// 后面遍歷的節(jié)點都必須是葉子節(jié)點
leaf = true;
}
}
return true;
}
protected static class Node<E> {
E element;
// 左子節(jié)點
Node<E> left;
// 右子節(jié)點
Node<E> right;
// 父節(jié)點
Node<E> parent;
// 構造函數(shù)
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
// 是否是葉子節(jié)點
public boolean isLeaf() {
return left == null && right == null;
}
// 度為2節(jié)點
public boolean hasTwoChildrenNode() {
return left != null && right != null;
}
// 當前節(jié)點是否是父節(jié)點的左子節(jié)點
public boolean isLeftChild() {
return parent != null && this == parent.left;
}
// 當前節(jié)點是否是父節(jié)點的右子節(jié)點
public boolean isRightChild() {
return parent != null && this == parent.right;
}
}
}
- BST(二叉搜索樹)
package com.weyan.tree;
import java.util.Comparator;
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
private Comparator<E> comparator;
//java 默認構造函數(shù)是無參數(shù)
public BST() {
this(null);
}
public BST(Comparator<E> comparator) {
this.comparator = comparator;
}
public void add(E element) {
elementNotNullCheck(element);
// 添加第一個節(jié)點
if (root == null) {
root = createNode(element, null);
size++;
//添加節(jié)點之后的處理
afterAdd(root);
return;
}
// 添加的不是第一個節(jié)點
// 找到父節(jié)點
Node<E> parent = root;
Node<E> node = root;
int cmp = 0;
while (node != null) {
parent = node;
cmp = compare(element, node.element);
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else {// 相等
node.element = element;
return;
}
}
// 看看插入到父節(jié)點的哪個位置
Node<E> newNode = createNode(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else if (cmp < 0) {
parent.left = newNode;
}
size++;
//添加節(jié)點之后的處理
afterAdd(newNode);
}
//添加node節(jié)點之后的調整
protected void afterAdd(Node<E> node) { }
public void remove(E element) {
remove(node(element));
}
private void remove(Node<E> node) {
if (node == null) {
return;
}
size--;
// 度為2的節(jié)點
if (node.hasTwoChildrenNode()) {
// 找到后繼節(jié)點
Node<E> s = successor(node);
// 用后繼節(jié)點的值覆蓋度為2的節(jié)點的值
node.element = s.element;
// 刪除后繼節(jié)點
node = s;
}
// 刪除node節(jié)點（node的度必然是1或0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) {// node是度為1節(jié)點
// 更改parent
replacement.parent = node.parent;
// 更改parent的left/right的指向
if (node.parent == null) {// node是度為1的節(jié)點寂曹，并且是根節(jié)點
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
} else if (node.parent == null) {// node是葉子節(jié)點并且是根節(jié)點
root = null;
} else {// node是葉子節(jié)點哎迄，但不是根節(jié)點
if (node == node.parent.right) {
node.parent.right = null;
} else {// node == node.parent.left
node.parent.left = null;
}
}
}
// 根據(jù)元素查找對應的節(jié)點
private Node<E> node(E element) {
Node<E> node = root;
while (node != null) {
int cmp = compare(element, node.element);
if (cmp == 0) {
return node;
}
if (cmp > 0) {
node = node.right;
} else {
node = node.left;
}
}
return null;
}
/// 是否包含一個元素
public boolean contains(E element) {
return node(element) != null;
}
// 比較兩個節(jié)點,返回值==0代表e1和e2相等;返回值>0代表e1>e2;返回值<0代表e1<e2
private int compare(E e1, E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<E>) e1).compareTo(e2);
}
// 判斷一個節(jié)點是否為空
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
}
- AVLTree（AVL平衡二叉搜索樹）
package com.weyan.tree;
import java.util.Comparator;
public class AVLTree<E> extends BST<E> {
// java 默認構造函數(shù)是無參數(shù)
public AVLTree() {
this(null);
}
public AVLTree(Comparator<E> comparator) {
super(comparator);
}
@Override
protected void afterAdd(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {// 平衡回右，更新高度
updateHeight(node);
} else {// 不平衡，恢復為平衡
rebalance(node);
break;
}
}
}
@Override
protected Node<E> createNode(E element, Node<E> parent) {
// TODO Auto-generated method stub
return new AVLNode<>(element, parent);
}
// 判斷是否平衡
private boolean isBalanced(Node<E> node) {
return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
}
// 更新高度
private void updateHeight(Node<E> node) {
((AVLNode<E>) node).updateHeight();
}
// 恢復平衡漱挚，grand 是第一個不平衡節(jié)點
private void rebalance(Node<E> grand) {
Node<E> parent = ((AVLNode<E>) grand).tallerChild();
Node<E> node = ((AVLNode<E>) parent).tallerChild();
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
rotateRight(grand);
} else { // LR
rotateLeft(parent);
rotateRight(grand);
}
} else { // R
if (node.isLeftChild()) { // RL
rotateRight(parent);
rotateLeft(grand);
} else { // RR
rotateLeft(grand);
}
}
}
// 左旋轉
private void rotateLeft(Node<E> grand) {
Node<E> parent = grand.right;
Node<E> child = parent.left;
grand.right = child;
parent.left = grand;
//更新parent/grand/child的parent和parent/grand的高度
afterRotate(grand, parent, child);
}
// 右旋轉
private void rotateRight(Node<E> grand) {
Node<E> parent = grand.left;
Node<E> child = parent.right;
grand.left = child;
parent.right = grand;
//更新parent/grand/child的parent和parent/grand的高度
afterRotate(grand, parent, child);
}
//更新parent/grand/child的parent和parent/grand的高度
private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
// parent稱為子樹的根節(jié)點,更新parent的parent
parent.parent = grand.parent;
if (grand.isLeftChild()) {
grand.parent.left = parent;
} else if (grand.isRightChild()) {
grand.parent.right = parent;
} else {
root = parent;
}
// 更新child的parent
if (child != null) {
child.parent = grand;
}
// 更新grand的parent
grand.parent = parent;
// 更新grand翔烁、parent高度
updateHeight(grand);
updateHeight(parent);
}
private static class AVLNode<E> extends Node<E> {
int height = 1;
public AVLNode(E element, Node<E> parent) {
super(element, parent);
}
// 平衡因子
public int balanceFactor() {
int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
return leftHeight - rightHeight;
}
// 更新節(jié)點高度，（左右子樹節(jié)點高度的最大值）
public void updateHeight() {
int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
height = 1 + Math.max(leftHeight, rightHeight);
}
// 比較高的子節(jié)點旨涝，是左子節(jié)點還是右子節(jié)點
public AVLNode<E> tallerChild() {
int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
if (leftHeight > rightHeight)
return (AVLNode<E>) left;
if (leftHeight < rightHeight)
return (AVLNode<E>) right;
return isLeftChild() ? (AVLNode<E>) left : (AVLNode<E>) right;
}
}
}
- Main
package com.weyan;
import java.util.Comparator;
import java.util.regex.Matcher;
import com.weyan.file.Files;
import com.weyan.printer.BinaryTreeInfo;
import com.weyan.printer.BinaryTrees;
import com.weyan.tree.AVLTree;
import com.weyan.tree.BST;
import com.weyan.tree.BinarySearchTree;
public class Main {
// 自定義類實現(xiàn)比較器PersonComparator
private static class PersonComparator implements Comparator<Person> {
public int compare(Person e1, Person e2) {
return e1.getAge() - e2.getAge();
}
}
// 自定義類實現(xiàn)比較器PersonComparator2
private static class PersonComparator2 implements Comparator<Person> {
public int compare(Person e1, Person e2) {
return e2.getAge() - e1.getAge();
}
}
@SuppressWarnings("unused")
private static void test1() {
// 傳入比較器PersonComparator
BinarySearchTree<Person> bst1 = new BinarySearchTree<Person>(new PersonComparator());
bst1.add(new Person(12));
bst1.add(new Person(15));
// 傳入比較器PersonComparator2
BinarySearchTree<Person> bst2 = new BinarySearchTree<Person>(new PersonComparator2());
bst2.add(new Person(12));
bst2.add(new Person(15));
// 不傳入比較器
BinarySearchTree<Person> bst3 = new BinarySearchTree<Person>();
bst3.add(new Person(12));
bst3.add(new Person(15));
/*
* java 中的匿名類 類似于iOS中的Block JS中的閉包(funciton)
*/
BinarySearchTree<Person> bst4 = new BinarySearchTree<Person>(new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge() - o2.getAge();
}
});
bst4.add(new Person(12));
bst4.add(new Person(15));
}
@SuppressWarnings("unused")
private static void test2() {
Integer data[] = new Integer[] { 7, 4, 9, 2, 5, 8, 11, 3 };
BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
}
@SuppressWarnings("unused")
private static void test3() {
BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
for (int i = 0; i < 40; i++) {
bst.add((int) (Math.random() * 100));
}
String str = BinaryTrees.printString(bst);
str += "\n";// 這一步一定得換行蹬屹，不然后面追加的圖會錯亂
Files.writeToFile("/Users/xieweiyan/Desktop/printer.txt", str);
}
private static void test4() {
Integer data[] = new Integer[] { 7, 4, 9, 2, 5, 8, 11, 3 };
BST<Integer> bst = new BST<Integer>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
}
private static void test5() {
Integer data[] = new Integer[] { 85, 19, 69, 3, 7, 99, 95, 2, 1, 70, 44, 58, 11, 21, 14, 93, 57, 4, 56 };
AVLTree<Integer> avlTree = new AVLTree<Integer>();
for (int i = 0; i < data.length; i++) {
avlTree.add(data[i]);
}
BinaryTrees.println(avlTree);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// test1();
// test2();
// test3();
// test4();
test5();
}
}
![]()
驗證結果
驗證結果
第二種回復平衡的方法：統(tǒng)一旋轉操作
AVLTree 平衡二叉搜索樹改動代碼如下
package com.weyan.tree;
import java.util.Comparator;
public class AVLTree<E> extends BST<E> {
// java 默認構造函數(shù)是無參數(shù)
public AVLTree() {
this(null);
}
public AVLTree(Comparator<E> comparator) {
super(comparator);
}
@Override
protected void afterAdd(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {// 平衡，更新高度
updateHeight(node);
} else {// 不平衡白华，恢復為平衡
rebalance2(node);
break;
}
}
}
@Override
protected Node<E> createNode(E element, Node<E> parent) {
// TODO Auto-generated method stub
return new AVLNode<>(element, parent);
}
// 判斷是否平衡
private boolean isBalanced(Node<E> node) {
return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
}
// 更新高度
private void updateHeight(Node<E> node) {
((AVLNode<E>) node).updateHeight();
}
/*---------------第二種方法恢復平衡----------*/
// 第二種方法恢復平衡慨默，統(tǒng)一旋轉操作
private void rebalance2(Node<E> grand) {
Node<E> parent = ((AVLNode<E>) grand).tallerChild();
Node<E> node = ((AVLNode<E>) parent).tallerChild();
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
rotate(grand, node.left, node, node.right, parent, parent.right, grand, grand.right);
} else { // LR
rotate(grand, parent.left, parent, node.left, node, node.right, grand, grand.right);
}
} else { // R
if (node.isLeftChild()) { // RL
rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
} else { // RR
rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
}
}
}
// 統(tǒng)一旋轉操作
private void rotate(Node<E> r, // 子樹的根節(jié)點(不平衡節(jié)點點)
Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f, Node<E> g) {
// 讓d成為這棵子樹的根節(jié)點
d.parent = r.parent;
if (r.isLeftChild()) {
r.parent.left = d;
} else if (r.isRightChild()) {
r.parent.right = d;
} else {
root = d;
}
// 處理a-b-c
b.left = a;
b.right = c;
if (a != null) {
a.parent = b;
}
if (c != null) {
c.parent = b;
}
// 更新中間b節(jié)點的高度
updateHeight(b);
// 處理e-f-g
f.left = e;
f.right = g;
if (e != null) {
e.parent = f;
}
if (g != null) {
g.parent = f;
}
// 更新中間f節(jié)點的高度
updateHeight(f);
// 處理b-d-f
d.left = b;
d.right = f;
b.parent = d;
f.parent = d;
// 更新中間d節(jié)點的高度
updateHeight(d);
}
/*---------------第一種方法恢復平衡----------*/
// 第一種方法恢復平衡，grand 是第一個不平衡節(jié)點
// private void rebalance(Node<E> grand) {
// Node<E> parent = ((AVLNode<E>) grand).tallerChild();
// Node<E> node = ((AVLNode<E>) parent).tallerChild();
// if (parent.isLeftChild()) { // L
// if (node.isLeftChild()) { // LL
// rotateRight(grand);
// } else { // LR
// rotateLeft(parent);
// rotateRight(grand);
// }
// } else { // R
// if (node.isLeftChild()) { // RL
// rotateRight(parent);
// rotateLeft(grand);
// } else { // RR
// rotateLeft(grand);
// }
// }
// }
// 左旋轉
private void rotateLeft(Node<E> grand) {
Node<E> parent = grand.right;
Node<E> child = parent.left;
grand.right = child;
parent.left = grand;
// 更新parent/grand/child的parent和parent/grand的高度
afterRotate(grand, parent, child);
}
// 右旋轉
private void rotateRight(Node<E> grand) {
Node<E> parent = grand.left;
Node<E> child = parent.right;
grand.left = child;
parent.right = grand;
// 更新parent/grand/child的parent和parent/grand的高度
afterRotate(grand, parent, child);
}
// 更新parent/grand/child的parent和parent/grand的高度
private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
// parent稱為子樹的根節(jié)點,更新parent的parent
parent.parent = grand.parent;
if (grand.isLeftChild()) {
grand.parent.left = parent;
} else if (grand.isRightChild()) {
grand.parent.right = parent;
} else {
root = parent;
}
// 更新child的parent
if (child != null) {
child.parent = grand;
}
// 更新grand的parent
grand.parent = parent;
// 更新grand弧腥、parent高度
updateHeight(grand);
updateHeight(parent);
}
private static class AVLNode<E> extends Node<E> {
int height = 1;
public AVLNode(E element, Node<E> parent) {
super(element, parent);
}
// 平衡因子
public int balanceFactor() {
int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
return leftHeight - rightHeight;
}
// 更新節(jié)點高度厦取，（左右子樹節(jié)點高度的最大值）
public void updateHeight() {
int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
height = 1 + Math.max(leftHeight, rightHeight);
}
// 比較高的子節(jié)點，是左子節(jié)點還是右子節(jié)點
public AVLNode<E> tallerChild() {
int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
if (leftHeight > rightHeight)
return (AVLNode<E>) left;
if (leftHeight < rightHeight)
return (AVLNode<E>) right;
return isLeftChild() ? (AVLNode<E>) left : (AVLNode<E>) right;
}
}
}
驗證結果
結果比對
3.刪除操作導致的失衡
- 紅色代表要刪除的節(jié)點
- 綠色代表 如果綠色節(jié)點不存在鸟赫，可能會導致更高層的祖先節(jié)點會失衡蒜胖。
平衡二叉搜索樹刪除也可能會導致父節(jié)點或祖父節(jié)點失衡
4.解決刪除操作導致的失衡方案
代碼如下：
BST:二叉搜索樹
package com.weyan.tree;
import java.util.Comparator;
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
private Comparator<E> comparator;
//java 默認構造函數(shù)是無參數(shù)
public BST() {
this(null);
}
public BST(Comparator<E> comparator) {
this.comparator = comparator;
}
public void add(E element) {
elementNotNullCheck(element);
// 添加第一個節(jié)點
if (root == null) {
root = createNode(element, null);
size++;
//添加節(jié)點之后的處理
afterAdd(root);
return;
}
// 添加的不是第一個節(jié)點
// 找到父節(jié)點
Node<E> parent = root;
Node<E> node = root;
int cmp = 0;
while (node != null) {
parent = node;
cmp = compare(element, node.element);
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else {// 相等
node.element = element;
return;
}
}
// 看看插入到父節(jié)點的哪個位置
Node<E> newNode = createNode(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else if (cmp < 0) {
parent.left = newNode;
}
size++;
//添加節(jié)點之后的處理
afterAdd(newNode);
}
//添加node節(jié)點之后的調整
protected void afterAdd(Node<E> node) { }
public void remove(E element) {
remove(node(element));
}
private void remove(Node<E> node) {
if (node == null) {
return;
}
size--;
// 度為2的節(jié)點
if (node.hasTwoChildrenNode()) {
// 找到后繼節(jié)點
Node<E> s = successor(node);
// 用后繼節(jié)點的值覆蓋度為2的節(jié)點的值
node.element = s.element;
// 刪除后繼節(jié)點
node = s;
}
// 刪除node節(jié)點（node的度必然是1或0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) {// node是度為1節(jié)點
// 更改parent
replacement.parent = node.parent;
// 更改parent的left/right的指向
if (node.parent == null) {// node是度為1的節(jié)點，并且是根節(jié)點
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
//node:刪除的節(jié)點抛蚤，刪除之后的處理
afterRemove(node);
} else if (node.parent == null) {// node是葉子節(jié)點并且是根節(jié)點
root = null;
//node:刪除的節(jié)點台谢，刪除之后的處理。
afterRemove(node);
} else {// node是葉子節(jié)點岁经，但不是根節(jié)點
if (node == node.parent.right) {
node.parent.right = null;
} else {// node == node.parent.left
node.parent.left = null;
}
//node:刪除的節(jié)點朋沮，刪除之后的處理。
afterRemove(node);
}
}
//刪除node節(jié)點之后的調整
protected void afterRemove(Node<E> node) { }
// 根據(jù)元素查找對應的節(jié)點
private Node<E> node(E element) {
Node<E> node = root;
while (node != null) {
int cmp = compare(element, node.element);
if (cmp == 0) {
return node;
}
if (cmp > 0) {
node = node.right;
} else {
node = node.left;
}
}
return null;
}
/// 是否包含一個元素
public boolean contains(E element) {
return node(element) != null;
}
// 比較兩個節(jié)點,返回值==0代表e1和e2相等;返回值>0代表e1>e2;返回值<0代表e1<e2
private int compare(E e1, E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<E>) e1).compareTo(e2);
}
// 判斷一個節(jié)點是否為空
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
}
AVLTree:平衡二叉搜索樹
package com.weyan.tree;
import java.util.Comparator;
public class AVLTree<E> extends BST<E> {
// java 默認構造函數(shù)是無參數(shù)
public AVLTree() {
this(null);
}
public AVLTree(Comparator<E> comparator) {
super(comparator);
}
//添加節(jié)點之后的操作
@Override
protected void afterAdd(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {// 平衡缀壤，更新高度
updateHeight(node);
} else {// 不平衡樊拓，恢復為平衡
rebalance2(node);
break;
}
}
}
///刪除之后的操作
@Override
protected void afterRemove(Node<E> node) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {// 平衡，更新高度
updateHeight(node);
} else {// 不平衡塘慕，恢復為平衡
rebalance2(node);
//注：跟afterAdd的區(qū)別是 不用break,因為平衡一次過后可能還會存在上層祖節(jié)點不平衡筋夏，需要多次平衡調整。
}
}
}
@Override
protected Node<E> createNode(E element, Node<E> parent) {
// TODO Auto-generated method stub
return new AVLNode<>(element, parent);
}
// 判斷是否平衡
private boolean isBalanced(Node<E> node) {
return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
}
// 更新高度
private void updateHeight(Node<E> node) {
((AVLNode<E>) node).updateHeight();
}
/*---------------第二種方法恢復平衡----------*/
// 第二種方法恢復平衡图呢，統(tǒng)一旋轉操作
private void rebalance2(Node<E> grand) {
Node<E> parent = ((AVLNode<E>) grand).tallerChild();
Node<E> node = ((AVLNode<E>) parent).tallerChild();
if (parent.isLeftChild()) { // L
if (node.isLeftChild()) { // LL
rotate(grand, node.left, node, node.right, parent, parent.right, grand, grand.right);
} else { // LR
rotate(grand, parent.left, parent, node.left, node, node.right, grand, grand.right);
}
} else { // R
if (node.isLeftChild()) { // RL
rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
} else { // RR
rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
}
}
}
// 統(tǒng)一旋轉操作
private void rotate(Node<E> r, // 子樹的根節(jié)點(不平衡節(jié)點點)
Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f, Node<E> g) {
// 讓d成為這棵子樹的根節(jié)點
d.parent = r.parent;
if (r.isLeftChild()) {
r.parent.left = d;
} else if (r.isRightChild()) {
r.parent.right = d;
} else {
root = d;
}
// 處理a-b-c
b.left = a;
b.right = c;
if (a != null) {
a.parent = b;
}
if (c != null) {
c.parent = b;
}
// 更新中間b節(jié)點的高度
updateHeight(b);
// 處理e-f-g
f.left = e;
f.right = g;
if (e != null) {
e.parent = f;
}
if (g != null) {
g.parent = f;
}
// 更新中間f節(jié)點的高度
updateHeight(f);
// 處理b-d-f
d.left = b;
d.right = f;
b.parent = d;
f.parent = d;
// 更新中間d節(jié)點的高度
updateHeight(d);
}
/*---------------第一種方法恢復平衡----------*/
// 第一種方法恢復平衡条篷，grand 是第一個不平衡節(jié)點
// private void rebalance(Node<E> grand) {
// Node<E> parent = ((AVLNode<E>) grand).tallerChild();
// Node<E> node = ((AVLNode<E>) parent).tallerChild();
// if (parent.isLeftChild()) { // L
// if (node.isLeftChild()) { // LL
// rotateRight(grand);
// } else { // LR
// rotateLeft(parent);
// rotateRight(grand);
// }
// } else { // R
// if (node.isLeftChild()) { // RL
// rotateRight(parent);
// rotateLeft(grand);
// } else { // RR
// rotateLeft(grand);
// }
// }
// }
// 左旋轉
private void rotateLeft(Node<E> grand) {
Node<E> parent = grand.right;
Node<E> child = parent.left;
grand.right = child;
parent.left = grand;
// 更新parent/grand/child的parent和parent/grand的高度
afterRotate(grand, parent, child);
}
// 右旋轉
private void rotateRight(Node<E> grand) {
Node<E> parent = grand.left;
Node<E> child = parent.right;
grand.left = child;
parent.right = grand;
// 更新parent/grand/child的parent和parent/grand的高度
afterRotate(grand, parent, child);
}
// 更新parent/grand/child的parent和parent/grand的高度
private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
// parent稱為子樹的根節(jié)點,更新parent的parent
parent.parent = grand.parent;
if (grand.isLeftChild()) {
grand.parent.left = parent;
} else if (grand.isRightChild()) {
grand.parent.right = parent;
} else {
root = parent;
}
// 更新child的parent
if (child != null) {
child.parent = grand;
}
// 更新grand的parent
grand.parent = parent;
// 更新grand、parent高度
updateHeight(grand);
updateHeight(parent);
}
private static class AVLNode<E> extends Node<E> {
int height = 1;
public AVLNode(E element, Node<E> parent) {
super(element, parent);
}
// 平衡因子
public int balanceFactor() {
int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
return leftHeight - rightHeight;
}
// 更新節(jié)點高度蛤织，（左右子樹節(jié)點高度的最大值）
public void updateHeight() {
int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
height = 1 + Math.max(leftHeight, rightHeight);
}
// 比較高的子節(jié)點赴叹，是左子節(jié)點還是右子節(jié)點
public AVLNode<E> tallerChild() {
int leftHeight = left == null ? 0 : ((AVLNode<E>) left).height;
int rightHeight = right == null ? 0 : ((AVLNode<E>) right).height;
if (leftHeight > rightHeight)
return (AVLNode<E>) left;
if (leftHeight < rightHeight)
return (AVLNode<E>) right;
return isLeftChild() ? (AVLNode<E>) left : (AVLNode<E>) right;
}
}
}
驗證結果
比對結果
總結
