- 1.二叉搜索树(BST)继承二叉树(BinaryTree)
- 2.平衡二叉搜索树(BBST)继承二叉搜索树(BST)
- 3.AVL树和红黑树(RBTree)都继承平衡二叉搜索树(BBST)
注：
- 红黑树的5条性质决定红黑树的平衡。
- AVL树是靠平衡因子来保持平衡的。
答案：不是，因为38的右子节点null 也是空节点，这条路径上包含的black节点和其他路径不相同。
一、添加
1.uncle不是RED情况
2.uncle 是RED情况
RBTree类
///红黑树继承平衡二叉搜索树
package com.weyan.tree;
import java.util.Comparator;
public class RBTree<E> extends BBST<E> {
private static final boolean RED = false;
private static final boolean BLACK = true;
// java 默认构造函数是无参数
public RBTree() {
this(null);
}
public RBTree(Comparator<E> comparator) {
super(comparator);
}
/* 染色 */
private Node<E> color(Node<E> node, boolean color) {
if (node == null)
return node;
((RBNode<E>) node).color = color;
return node;
}
// 染红色
private Node<E> red(Node<E> node) {
return color(node, RED);
}
// 染红色
private Node<E> black(Node<E> node) {
return color(node, BLACK);
}
/* 判断颜色 */
// 当前颜色
private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>) node).color;
}
// 是否为红色
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
// 是否为红色
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
@Override
protected void afterAdd(Node<E> node) {
Node<E> parent = node.parent;
// 添加的是根节点或者上溢到达了根节点
if (parent == null) {
black(node);
return;
}
// 如果父节点是黑色，直接返回
if (isBlack(parent)) return;
// 叔父节点
Node<E> uncle = parent.sibling();
// 祖父节点
Node<E> grand = parent.parent;
if (isRed(uncle)) {// 叔父节点是红色（节点上溢）
black(uncle);
black(parent);
// 把祖父节点当做是新添加的节点,染成红色。
red(grand);
// 递归
afterAdd(grand);
return;
}
// 叔父节点不是红色
if (parent.isLeftChild()) {// L
//grand染成红色
red(grand);
if (node.isLeftChild()) {// LL
//parent染成黑色
black(parent);
} else {// LR
//node 染成黑色
black(node);
//parent左旋转
rotateLeft(parent);
}
//grand 右旋转
rotateRight(grand);
} else {// R
//grand染成红色
red(grand);
if (node.isLeftChild()) {// RL
//node 染成黑色
black(node);
//parent右旋转
rotateRight(parent);
} else {// RR
//parent染成黑色
black(parent);
}
//grand 左旋转
rotateLeft(grand);
}
}
// @Override
// protected void afterRemove(Node<E> node) {
// // TODO Auto-generated method stub
// super.afterRemove(node);
// }
@Override
protected Node<E> createNode(E element, Node<E> parent) {
// TODO Auto-generated method stub
return new RBNode<>(element, parent);
}
private static class RBNode<E> extends Node<E> {
boolean color = RED;
public RBNode(E element, Node<E> parent) {
super(element, parent);
}
@Override
public String toString() {
String str = "";
if (color == RED) {
str = "R_";
}
return str + element.toString();
}
}
}
验证
private static void test7() {
Integer data[] = new Integer[] { 55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50};
RBTree<Integer> rbTree = new RBTree<Integer>();
for (int i = 0; i < data.length; i++) {
rbTree.add(data[i]);
}
BinaryTrees.println(rbTree);
}
二、删除
RBTree类
///红黑树继承平衡二叉搜索树
package com.weyan.tree;
import java.util.Comparator;
import com.weyan.tree.BinaryTree.Node;
public class RBTree<E> extends BBST<E> {
private static final boolean RED = false;
private static final boolean BLACK = true;
// java 默认构造函数是无参数
public RBTree() {
this(null);
}
public RBTree(Comparator<E> comparator) {
super(comparator);
}
@Override
protected void afterRemove(Node<E> node , Node<E> replacement) {
//删除的节点是红色
if (isRed(node)) return;
//用于取代node的子节点是红色
if (isRed(replacement)) {
//将替代的子节点染为黑色
black(replacement);
return;
}
//删除的是根节点
Node<E> parent = node.parent;
if(parent == null) return;
//删除的是黑色叶子节点[下溢]
//判断被删除的node是左还是右(需要注意)
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) {//被删除的节点在左边，兄弟节点在右边
if (isRed(sibling)) {//兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
//更换兄弟
sibling = parent.right;
}
//兄弟节点必然是黑色
if (isBlack(sibling.left)&&isBlack(sibling.right)) {
//兄弟节点没有一个红色子节点,父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent, null);
}
}else {//兄弟节点至少有一个红色子节点
//兄弟节点的右边是黑色，兄弟要先旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
}else {//被删除的节点在右边，兄弟节点在左边
if (isRed(sibling)) {//兄弟节点是红色
black(sibling);
red(sibling);
rotateRight(parent);
//更换兄弟
sibling = parent.left;
}
//兄弟节点必然是黑色
if (isBlack(sibling.left)&&isBlack(sibling.right)) {
//兄弟节点没有一个红色子节点,父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent, null);
}
}else {//兄弟节点至少有一个红色子节点
//兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
/* 染色 */
private Node<E> color(Node<E> node, boolean color) {
if (node == null)
return node;
((RBNode<E>) node).color = color;
return node;
}
// 染红色
private Node<E> red(Node<E> node) {
return color(node, RED);
}
// 染红色
private Node<E> black(Node<E> node) {
return color(node, BLACK);
}
/* 判断颜色 */
// 当前颜色
private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>) node).color;
}
// 是否为红色
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
// 是否为红色
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
@Override
protected void afterAdd(Node<E> node) {
Node<E> parent = node.parent;
// 添加的是根节点
if (parent == null) {
black(node);
return;
}
// 如果父节点是黑色，直接返回
if (isBlack(parent)) return;
// 叔父节点
Node<E> uncle = parent.sibling();
// 祖父节点
Node<E> grand = parent.parent;
if (isRed(uncle)) {// 叔父节点是红色
black(uncle);
black(parent);
// 把祖父节点当做是新添加的节点,染成红色。
red(grand);
// 递归
afterAdd(grand);
return;
}
// 叔父节点不是红色
if (parent.isLeftChild()) {// L
//grand染成红色
red(grand);
if (node.isLeftChild()) {// LL
//parent染成黑色
black(parent);
} else {// LR
//node 染成黑色
black(node);
//parent左旋转
rotateLeft(parent);
}
//grand 右旋转
rotateRight(grand);
} else {// R
//grand染成红色
red(grand);
if (node.isLeftChild()) {// RL
//node 染成黑色
black(node);
//parent右旋转
rotateRight(parent);
} else {// RR
//parent染成黑色
black(parent);
}
//grand 左旋转
rotateLeft(grand);
}
}
// @Override
// protected void afterRemove(Node<E> node) {
// // TODO Auto-generated method stub
// super.afterRemove(node);
// }
@Override
protected Node<E> createNode(E element, Node<E> parent) {
// TODO Auto-generated method stub
return new RBNode<>(element, parent);
}
private static class RBNode<E> extends Node<E> {
boolean color = RED;
public RBNode(E element, Node<E> parent) {
super(element, parent);
}
@Override
public String toString() {
String str = "";
if (color == RED) {
str = "R_";
}
return str + element.toString();
}
}
}
验证结果：
private static void test8() {
Integer data[] = new Integer[] { 55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50};
RBTree<Integer> rbTree = new RBTree<Integer>();
for (int i = 0; i < data.length; i++) {
rbTree.add(data[i]);
}
BinaryTrees.println(rbTree);
for (int i = 0; i < data.length; i++) {
rbTree.remove(data[i]);
System.out.println("删除：" + "[" + data[i] + "]");
BinaryTrees.println(rbTree);
System.out.println("-------------分界线------------");
BinaryTrees.println(rbTree);
}
}
1
2
3
4
5
6
7
完整代码：
二叉树（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;
// 根节点
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);
}
// 层序遍历(通过链表实现)
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);
}
}
}
/*
* 使用自定义打印器 需要实现以下几个方法
*
*/
@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 + ")";
//如果返回的是node节点本身，会调用toString
return node;
}
// 前驱节点
protected Node<E> predecessor(Node<E> node) {
if (node == null)
return null;
// 前驱节点在左子树当中（left.right.right.........）
Node<E> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 从父节点、祖父节点当中去找前驱节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
// node.parent == null && node.left == null
return node.parent;
}
// 后继节点
protected Node<E> successor(Node<E> node) {
if (node == null)
return null;
// 前驱节点在左子树当中（right.left.left.........）
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点当中去找前驱节点
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);
// }
// 节点高度
// 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;
// 存储着每一层的元素数量
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 {
// 后面遍历的节点都必须是叶子节点
leaf = true;
}
}
return true;
}
protected static class Node<E> {
E element;
// 左子节点
Node<E> left;
// 右子节点
Node<E> right;
// 父节点
Node<E> parent;
// 构造函数
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
// 是否是叶子节点
public boolean isLeaf() {
return left == null && right == null;
}
// 度为2节点
public boolean hasTwoChildrenNode() {
return left != null && right != null;
}
// 当前节点是否是父节点的左子节点
public boolean isLeftChild() {
return parent != null && this == parent.left;
}
// 当前节点是否是父节点的右子节点
public boolean isRightChild() {
return parent != null && this == parent.right;
}
//兄弟节点
public Node<E> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
}
}
二叉搜索树（BST）
//二叉搜索树
package com.weyan.tree;
import java.util.Comparator;
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
private Comparator<E> comparator;
//java 默认构造函数是无参数
public BST() {
this(null);
}
public BST(Comparator<E> comparator) {
this.comparator = comparator;
}
public void add(E element) {
elementNotNullCheck(element);
// 添加第一个节点
if (root == null) {
root = createNode(element, null);
size++;
//添加节点之后的处理
afterAdd(root);
return;
}
// 添加的不是第一个节点
// 找到父节点
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;
}
}
// 看看插入到父节点的哪个位置
Node<E> newNode = createNode(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else if (cmp < 0) {
parent.left = newNode;
}
size++;
//添加节点之后的处理
afterAdd(newNode);
}
//添加node节点之后的调整
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的节点
if (node.hasTwoChildrenNode()) {
// 找到后继节点
Node<E> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.element = s.element;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) {// node是度为1节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left/right的指向
if (node.parent == null) {// node是度为1的节点，并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
//node:删除的节点，删除之后的处理
afterRemove(node,replacement);
} else if (node.parent == null) {// node是叶子节点并且是根节点
root = null;
//node:删除的节点，删除之后的处理。
afterRemove(node,null);
} else {// node是叶子节点，但不是根节点
if (node == node.parent.right) {
node.parent.right = null;
} else {// node == node.parent.left
node.parent.left = null;
}
//node:删除的节点，删除之后的处理。
afterRemove(node,null);
}
}
//删除node节点之后的调整
protected void afterRemove(Node<E> node , Node<E> replacement) { }
// 根据元素查找对应的节点
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;
}
// 比较两个节点,返回值==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);
}
// 判断一个节点是否为空
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
}
平衡二叉搜索树（BBST）
/*1.二叉搜索树(BST)继承二叉树(BinaryTree)
*2.平衡二叉搜索树(BBST)继承二叉搜索树(BST)
*3.AVL树和红黑树(RBTree)都继承平衡二叉搜索树(BBST)
*/
package com.weyan.tree;
import java.util.Comparator;
public class BBST<E> extends BST<E> {
// java 默认构造函数是无参数
public BBST() {
this(null);
}
public BBST(Comparator<E> comparator) {
super(comparator);
}
// 统一旋转操作
protected void rotate(Node<E> r, // 子树的根节点(不平衡节点点)
Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f, Node<E> g) {
// 让d成为这棵子树的根节点
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;
}
// 处理e-f-g
f.left = e;
f.right = g;
if (e != null) {
e.parent = f;
}
if (g != null) {
g.parent = f;
}
// 处理b-d-f
d.left = b;
d.right = f;
b.parent = d;
f.parent = d;
}
// 左旋转
protected 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);
}
// 右旋转
protected 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的高度
protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
// parent称为子树的根节点,更新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;
}
}
AVL树
package com.weyan.tree;
import java.util.Comparator;
import com.weyan.tree.BinaryTree.Node;
public class AVLTree<E> extends BBST<E> {
// java 默认构造函数是无参数
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 void afterRemove(Node<E> node , Node<E> replacement) {
while ((node = node.parent) != null) {
if (isBalanced(node)) {// 平衡，更新高度
updateHeight(node);
} else {// 不平衡，恢复为平衡
rebalance2(node);
//注：跟afterAdd的区别是 不用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();
}
/*---------------第二种方法恢复平衡----------*/
// 第二种方法恢复平衡，统一旋转操作
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);
}
}
}
/*---------------第一种方法恢复平衡----------*/
// 第一种方法恢复平衡，grand 是第一个不平衡节点
// 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);
// }
// }
// }
// 更新parent/grand/child的parent和parent/grand的高度
@Override
protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
// TODO Auto-generated method stub
super.afterRotate(grand, parent, child);
updateHeight(grand);
updateHeight(parent);
}
@Override
protected void rotate(Node<E> r, Node<E> a, Node<E> b, Node<E> c, Node<E> d, Node<E> e, Node<E> f, Node<E> g) {
// TODO Auto-generated method stub
super.rotate(r, a, b, c, d, e, f, g);
updateHeight(b);
updateHeight(f);
updateHeight(d);
}
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;
}
// 更新节点高度，（左右子树节点高度的最大值）
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);
}
// 比较高的子节点，是左子节点还是右子节点
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;
}
}
}
红黑树（RBTree）
///红黑树继承平衡二叉搜索树
package com.weyan.tree;
import java.util.Comparator;
import com.weyan.tree.BinaryTree.Node;
public class RBTree<E> extends BBST<E> {
private static final boolean RED = false;
private static final boolean BLACK = true;
// java 默认构造函数是无参数
public RBTree() {
this(null);
}
public RBTree(Comparator<E> comparator) {
super(comparator);
}
@Override
protected void afterRemove(Node<E> node , Node<E> replacement) {
//删除的节点是红色
if (isRed(node)) return;
//用于取代node的子节点是红色
if (isRed(replacement)) {
//将替代的子节点染为黑色
black(replacement);
return;
}
//删除的是根节点
Node<E> parent = node.parent;
if(parent == null) return;
//删除的是黑色叶子节点[下溢]
//判断被删除的node是左还是右(需要注意)
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) {//被删除的节点在左边，兄弟节点在右边
if (isRed(sibling)) {//兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
//更换兄弟
sibling = parent.right;
}
//兄弟节点必然是黑色
if (isBlack(sibling.left)&&isBlack(sibling.right)) {
//兄弟节点没有一个红色子节点,父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent, null);
}
}else {//兄弟节点至少有一个红色子节点
//兄弟节点的右边是黑色，兄弟要先旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
}else {//被删除的节点在右边，兄弟节点在左边
if (isRed(sibling)) {//兄弟节点是红色
black(sibling);
red(sibling);
rotateRight(parent);
//更换兄弟
sibling = parent.left;
}
//兄弟节点必然是黑色
if (isBlack(sibling.left)&&isBlack(sibling.right)) {
//兄弟节点没有一个红色子节点,父节点要向下跟兄弟节点合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRemove(parent, null);
}
}else {//兄弟节点至少有一个红色子节点
//兄弟节点的左边是黑色，兄弟要先旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
/* 染色 */
private Node<E> color(Node<E> node, boolean color) {
if (node == null)
return node;
((RBNode<E>) node).color = color;
return node;
}
// 染红色
private Node<E> red(Node<E> node) {
return color(node, RED);
}
// 染红色
private Node<E> black(Node<E> node) {
return color(node, BLACK);
}
/* 判断颜色 */
// 当前颜色
private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>) node).color;
}
// 是否为红色
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
// 是否为红色
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
@Override
protected void afterAdd(Node<E> node) {
Node<E> parent = node.parent;
// 添加的是根节点
if (parent == null) {
black(node);
return;
}
// 如果父节点是黑色，直接返回
if (isBlack(parent)) return;
// 叔父节点
Node<E> uncle = parent.sibling();
// 祖父节点
Node<E> grand = parent.parent;
if (isRed(uncle)) {// 叔父节点是红色
black(uncle);
black(parent);
// 把祖父节点当做是新添加的节点,染成红色。
red(grand);
// 递归
afterAdd(grand);
return;
}
// 叔父节点不是红色
if (parent.isLeftChild()) {// L
//grand染成红色
red(grand);
if (node.isLeftChild()) {// LL
//parent染成黑色
black(parent);
} else {// LR
//node 染成黑色
black(node);
//parent左旋转
rotateLeft(parent);
}
//grand 右旋转
rotateRight(grand);
} else {// R
//grand染成红色
red(grand);
if (node.isLeftChild()) {// RL
//node 染成黑色
black(node);
//parent右旋转
rotateRight(parent);
} else {// RR
//parent染成黑色
black(parent);
}
//grand 左旋转
rotateLeft(grand);
}
}
// @Override
// protected void afterRemove(Node<E> node) {
// // TODO Auto-generated method stub
// super.afterRemove(node);
// }
@Override
protected Node<E> createNode(E element, Node<E> parent) {
// TODO Auto-generated method stub
return new RBNode<>(element, parent);
}
private static class RBNode<E> extends Node<E> {
boolean color = RED;
public RBNode(E element, Node<E> parent) {
super(element, parent);
}
@Override
public String toString() {
String str = "";
if (color == RED) {
str = "R_";
}
return str + element.toString();
}
}
}
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;
import com.weyan.tree.RBTree;
public class Main {
// 自定义类实现比较器PersonComparator
private static class PersonComparator implements Comparator<Person> {
public int compare(Person e1, Person e2) {
return e1.getAge() - e2.getAge();
}
}
// 自定义类实现比较器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);
}
private static void test6() {
Integer data[] = new Integer[] { 85, 19, 69, 3, 7, 99, 95};
AVLTree<Integer> avlTree = new AVLTree<Integer>();
for (int i = 0; i < data.length; i++) {
avlTree.add(data[i]);
}
avlTree.remove(95);
avlTree.remove(99);
avlTree.remove(7);
BinaryTrees.println(avlTree);
}
private static void test7() {
Integer data[] = new Integer[] { 55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50};
RBTree<Integer> rbTree = new RBTree<Integer>();
for (int i = 0; i < data.length; i++) {
rbTree.add(data[i]);
}
BinaryTrees.println(rbTree);
}
private static void test8() {
Integer data[] = new Integer[] { 55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50};
RBTree<Integer> rbTree = new RBTree<Integer>();
for (int i = 0; i < data.length; i++) {
rbTree.add(data[i]);
}
BinaryTrees.println(rbTree);
for (int i = 0; i < data.length; i++) {
rbTree.remove(data[i]);
System.out.println("删除：" + "[" + data[i] + "]");
BinaryTrees.println(rbTree);
System.out.println("-------------分界线------------");
BinaryTrees.println(rbTree);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// test1();
// test2();
// test3();
// test4();
// test5();
// test6();
// test7();
test8();
}
}
三、总结
