产品
实现了算法导论中几个平衡搜索树的Java代码
二叉搜索树抽象类
/*
* 二叉搜索数树的抽象父类
* 以element的哈希值为基准
* N 当前类的节点类型
* E 节点保存的元素类型
* Node<N,E> 二叉树节点的抽象父类
* parent 当前节点的父节点
* element 当前节点保存的元素
* left 当前节点的左孩子
* right 当前节点的右孩子
* root 当前树的根节点
* sentinel 当前树的哨兵 根节点的父母，叶子结点的孩子的引用 一般情况下是null
* */
public abstract class AbstractBinarySearchTree<N extends AbstractBinarySearchTree.Node<N, E>, E> {
/*
*Node<N,E> 二叉树节点的抽象父类
* parent 当前节点的父节点
* element 当前节点保存的元素
* left 当前节点的左孩子
* right 当前节点的右孩子
* */
static class Node<N, E> {
N parent;
E element;
N left;
N right;
public Node(N parent, E element, N left, N right) {
this.parent = parent;
this.element = element;
this.left = left;
this.right = right;
}
public Node() {
}
}
public N root;
public N sentinel;
/*
* 遍历搜索，搜索以node为根节点的树中是否有element元素
* 如果有，返回element所在的节点
* 如果没有，返回sentinel
* */
private N iterativeSearch(N node, E element) {
N result = null;
if (node != sentinel) {
int targetHash = element.hashCode();
int currentHash = node.element.hashCode();
if (targetHash == currentHash) {
if (node.element.equals(element)) {
result = node;
} else {
N rightResult = iterativeSearch(node.right, element);
N leftResult = iterativeSearch(node.left, element);
result = rightResult != sentinel ? rightResult : leftResult;
}
}
if (targetHash > currentHash) result = iterativeSearch(node.right, element);
if (targetHash < currentHash) result = iterativeSearch(node.left, element);
}
return result;
}
protected void leftRotate(N node){
N right = node.right;
N parent = node.parent;
if (right == sentinel) throw new RuntimeException("左旋节点的右孩子为空");
node.right = right.left;
if (right.left != sentinel) {
right.left.parent = node;
}
node.parent = right;
right.left = node;
right.parent = parent;
if (parent == sentinel) {
root = right;
} else if (node == parent.right) {
parent.right = right;
} else {
parent.left = right;
}
}
protected void rightRotate(N node){
N left = node.left;
N parent = node.parent;
if (left == sentinel) throw new RuntimeException("右旋节点的左孩子为空");
node.left = left.right;
if (left.right != sentinel) {
left.right.parent = node;
}
node.parent = left;
left.right = node;
left.parent = parent;
if (parent == sentinel) {
root = left;
} else if (node == parent.right) {
parent.right = left;
} else {
parent.left = left;
}
}
protected void baseInsert(N insertNode){
if(insertNode.element == null ) throw new RuntimeException("插入的元素值不能为空");
N prev = sentinel;
N curr = root;
int targetHash = insertNode.element.hashCode();
//值相等时，如果是随机左右，那么必须保存最后一次随机的选择，否则可能会出现覆盖
int randomFlag =0;
while( curr != sentinel){
prev = curr;
int currentHash= curr.element.hashCode();
if(targetHash > currentHash){
curr = curr.right;
}else if (targetHash < currentHash){
curr = curr.left;
}else{
if(new Random().nextBoolean()){
curr = curr.left;
randomFlag = 0;
}else{
curr = curr.right;
randomFlag = 1;
}
}
}
insertNode.parent = prev;
if(prev == sentinel){
root = insertNode;
}else{
int prevHash= prev.element.hashCode();
if(targetHash >prevHash){
prev.right = insertNode;
}else if (targetHash < prevHash){
prev.left = insertNode;
}else{
if(randomFlag == 1){
prev.right = insertNode;
}else{
prev.left = insertNode;
}
}
}
}
protected void DFS(N node, Consumer<N> consumer){
if(node != sentinel){
consumer.accept(node);
DFS(node.left,consumer);
DFS(node.right,consumer);
}
}
/*
* 替换树
* 把以node为根节点的树，替换到target的位置
* */
protected void transplant(N target, N node) {
if (target.parent == sentinel) {
root = node;
} else if (target.parent.left != sentinel && target == target.parent.left) {
target.parent.left = node;
} else {
target.parent.right = node;
}
if(node != sentinel) node.parent = target.parent;
}
/*
* 寻找以node为根节点的树的最小hash值所在的节点
* */
protected N minimum(N node) {
while (node.left != sentinel) node = node.left;
return node;
}
/*
* 根据给定元素搜索当前树
* 返回第一个搜索到的元素所在节点
* 如果没有搜索到，返回sentinel
* */
public N search(E element) {
return iterativeSearch(root, element);
}
/*
* 判断当前树是否存在给定元素
* */
public boolean isExist(E element) {
return search(element) != sentinel;
}
/*
* 获取当前树的大小，即节点个数
* */
public int size(){
AtomicInteger size = new AtomicInteger();
DFS(root,node-> size.getAndIncrement());
return size.get();
}
/*
* 获取指定索引的节点
* index通过二进制字符串描述节点
* 0表示左孩子，1表示右孩子
* 示例:
* 1 : 根节点
* 10 : 根节点的左孩子
* 101 : 根节点的左孩子的右孩子
* */
public N getNode(String index) {
N node = root;
char[] indexChar = index.toCharArray();
if (index.length() != 1) {
for (int i = 1; i < indexChar.length; i++) {
if (node == sentinel) {
node = null;
break;
}
if (indexChar[i] == '0') {
node = node.left;
} else {
node = node.right;
}
}
}
return node;
}
/*
* 根据给定元素，创建节点并插入树中
* 并保证树的数据结构
* */
public abstract void insert(E element);
/*
* 删除给定元素所在的查找到的第一个元素
* 并保证树的数据结构
* */
public abstract void remove(E element);
}
/*
* 红黑树
*
* */
public class RedBlackTree<E> extends AbstractBinarySearchTree<RedBlackTree.Node<E>, E> {
static class Node<E> extends AbstractBinarySearchTree.Node<Node<E>, E> {
char color;
public Node(Node<E> parent, E element, Node<E> left, Node<E> right, char color) {
super(parent, element, left, right);
this.color = color;
}
public Node(){};
}
{
root = sentinel =new Node<>(null,null,null,null,'b');
}
public RedBlackTree(Iterable<E> container) {
for (E element : container) {
insert(element);
}
}
public RedBlackTree(E[] elements) {
for (E element : elements) {
insert(element);
}
}
public RedBlackTree(){}
//修复插入操作对红黑树结构的破坏
private void insertFixup(Node<E> node){
Node<E> curr = node;
Node<E> parent;
Node<E> uncle;
int parentLocation;
while(curr.parent.color == 'r'){
parent =curr.parent;
if(parent.parent.left == parent){
//parent是其父母的左孩子
uncle = parent.parent.right;
parentLocation = 0;
}else{
//parent是其父母的右孩子
uncle = parent.parent.left;
parentLocation = 1;
}
if(uncle.color == 'r'){
//叔节点为红
uncle.color = 'b';
parent.color = 'b';
parent.parent.color = 'r';
curr = parent.parent;
}else if(parentLocation == 0?parent.right == curr:parent.left == curr){
//叔节点为黑，且curr为其父母的右孩子
curr = parent;
if(parentLocation == 0){
leftRotate(curr);
}else{
rightRotate(curr);
}
}else{
//叔节点为黑，且curr为其父母的左孩子
parent.parent.color = 'r';
parent.color = 'b';
if(parentLocation == 0){
rightRotate(parent.parent);
}else{
leftRotate(parent.parent);
}
}
}
root.color = 'b';
}
//修复删除操作对红黑树结构的破坏
private void deleteFixup(Node<E> toDeFixed){
Node<E> curr = toDeFixed;
Node<E> parent ;
Node<E> brother;
int location ;
while (curr != root && curr.color !='b'){
parent = curr.parent;
if(parent.left == curr){
location = 0;
brother = parent.right;
}else{
location = 1;
brother = parent.left;
}
if(brother.color == 'r'){
//兄弟节点是红色，则父母必为黑色
parent.color = 'r';
brother.color = 'b';
if(location == 0){
leftRotate(parent);
}else{
rightRotate(parent);
}
}else if(brother.left.color == 'b' && brother.right.color == 'b'){
//兄弟节点是黑色，且兄弟节点的孩子都是黑色的
brother.color = 'r';
curr = parent;
}else if(location == 0? brother.right.color == 'b' :brother.left.color == 'b'){
brother.color = 'r';
if(location == 0){
//兄弟节点是黑色，且兄弟节点的右孩子为黑色,左孩子为红色(curr是左孩子时)
brother.left.color = 'b';
rightRotate(brother);
}else{
//兄弟节点是黑色，且兄弟节点的左孩子为黑色,右孩子为红色(curr是右孩子时)
brother.right.color = 'b';
leftRotate(brother);
}
}else{
//兄弟节点是黑色，且兄弟节点的右孩子为红色(curr是左孩子时)
brother.color = parent.color;
parent.color = 'b';
if(location == 0){
brother.right.color = 'b';
leftRotate(parent);
}else{
brother.left.color = 'b';
rightRotate(parent);
}
curr = root;
}
curr.color = 'b';
}
curr.color = 'b';
}
@Override
public void insert(E element) {
Node<E> node = new Node<>(null,element,sentinel,sentinel,'r');
baseInsert(node);
insertFixup(node);
}
@Override
public void remove(E element) {
Node<E> node = search(element);
Node<E> left = node.left;
Node<E> right = node.right;
Node<E> toDeFixed = node;
char originalColor = toDeFixed.color;
if (left == sentinel ) {
toDeFixed = right;
transplant(node,right);
}else if(right == sentinel){
toDeFixed = left;
transplant(node,left);
}else{
Node<E> successor = minimum(right);
originalColor = successor.color;
toDeFixed = successor.right;
if(successor != right){
transplant(successor,successor.right);
successor.right = right;
right.parent = successor;
}
transplant(node,successor);
successor.left = left;
left.parent = successor;
successor.color = node.color;
}
if(originalColor == 'b') deleteFixup(toDeFixed);
}
}
AVL树
public class AVLTree<E> extends AbstractBinarySearchTree<AVLTree.Node<E>, E> {
static class Node<E> extends AbstractBinarySearchTree.Node<AVLTree.Node<E>, E> {
int height;
public Node(Node<E> parent, E element, Node<E> left, Node<E> right, int height) {
super(parent, element, left, right);
this.height = height;
}
public Node() {
}
;
}
{
root = sentinel = new Node<E>(null, null, null, null, -1);
}
public AVLTree(Iterable<E> container) {
for (E element : container) {
insert(element);
}
}
public AVLTree(E[] elements) {
for (E element : elements) {
insert(element);
}
}
public AVLTree(Node<E> node) {
root = node;
node.parent = sentinel;
}
public AVLTree() {
}
//插入、删除、旋转节点后维护节点的祖先节点的高度的正确性
private void maintainHeight(Node<E> node) {
while (node != sentinel) {
Node<E> right = node.right;
Node<E> left = node.left;
node.height = Math.max(right.height,left.height)+1;
node = node.parent;
}
}
//左旋
protected void leftRotate(Node<E> node) {
super.rightRotate(node);
maintainHeight(node);
}
//右旋
protected void rightRotate(Node<E> node) {
super.rightRotate(node);
maintainHeight(node);
}
//插入、删除节点后维护AVL树的性质
private void balance(Node<E> node) {
Node<E> curr = node;
Node<E> right;
Node<E> left;
Node<E> parent;
while (curr != sentinel){
right = curr.right;
left = curr.left;
parent = curr.parent;
int BF = left.height - right.height;
if(BF == -2){
int rBF = right.left.height - right.right.height;
if(rBF == 1){
rightRotate(right);
}
leftRotate(curr);
}else if(BF == 2){
int lBF = left.left.height - left.right.height;
if(lBF == -1){
leftRotate(left);
}
rightRotate(curr);
}
curr = parent;
}
}
//确认AVL树的性质和树节点高度属性的正确性
public boolean confirm() {
AtomicBoolean result = new AtomicBoolean(true);
DFS(root, node -> {
int rightHeight = node.right.height;
int leftHeight = node.left.height;
int BF = leftHeight - rightHeight;
int currentHeight = Math.max(rightHeight, leftHeight) + 1;
if (BF >= 2 || BF <= -2 || currentHeight != node.height) result.set(false);
});
return result.get();
}
@Override
public void insert(E element) {
Node<E> node = new Node<>(null,element,sentinel,sentinel,0);
baseInsert(node);
maintainHeight(node);
balance(node);
}
@Override
public void remove(E element) {
Node<E> node = search(element);
if(node == null) throw new RuntimeException("删除不存在的数据element"+element);
Node<E> left = node.left;
Node<E> right = node.right;
Node<E> balanceBegan ;
if (left == sentinel) {
balanceBegan = node.parent;
transplant(node, right);
} else if (right == sentinel) {
balanceBegan = node.parent;
transplant(node, left);
} else {
Node<E> successor = minimum(right);
if (successor.parent != node) {
if(successor.right != sentinel){
balanceBegan = successor.right;
}else{
balanceBegan = successor.parent;
}
transplant(successor, successor.right);
successor.right = right;
right.parent = successor;
}else{
balanceBegan = successor;
}
transplant(node, successor);
successor.left = left;
left.parent = successor;
}
maintainHeight(balanceBegan);
balance(balanceBegan);
}
}
Treap树
public class TreapTree<E> extends AbstractBinarySearchTree<TreapTree.Node<E>,E> {
static class Node<E> extends AbstractBinarySearchTree.Node<TreapTree.Node<E>,E>{
//节点的优先级
Long priority;
public Node(Node<E> parent, E element, Node<E> left, Node<E> right, Long priority) {
super(parent, element, left, right);
this.priority = priority;
}
public Node(Node<E> parent, E element, Node<E> left, Node<E> right) {
super(parent, element, left, right);
}
public Node() {}
}
private final HashSet<Long> priorityPool = new HashSet<>();
private final Random random = new Random();
{
root = sentinel = new Node<E>(null,null,null,null,Long.MAX_VALUE);
}
public TreapTree(E[] elements) {
for (E element : elements) {
insert(element);
}
}
public TreapTree(Node<E> node) {
root = node;
node.parent = sentinel;
}
public TreapTree() {}
private Long generatePriority(){
long priority = random.nextLong();
while ( !priorityPool.add(priority)){
priority = random.nextLong();
}
return priority;
}
public boolean confirm(){
AtomicBoolean result = new AtomicBoolean(true);
DFS(root,node->{
if(node != root && node.parent.priority > node.priority){
System.out.println("当前节点不满足性质：");
System.out.println(" 当前节点:"+node.element+"--"+node.priority);
System.out.println(" 其父节点:"+node.parent.element+"--"+node.parent.priority);
result.set(false);
}
});
return result.get();
}
private void insertFixup(Node<E> node){
//在修复的循环中，除了当前节点curr，其他所有节点都满足treap的性质
Node<E> parent = node.parent;
while (node != root && node.priority < parent.priority){
if(node == parent.left){
rightRotate(parent);
}else{
leftRotate(parent);
}
parent = node.parent;
}
}
private void removeFixup(Node<E> node){
Node<E> left = node.left;
Node<E> right = node.right;
while (node.priority > left.priority || node.priority > right.priority){
if(left.priority >right.priority){
leftRotate(node);
}else{
rightRotate(node);
}
left = node.left;
right = node.right;
}
}
@Override
public void insert(E element) {
Node<E> node = new Node<>(null, element, sentinel, sentinel, generatePriority());
baseInsert(node);
insertFixup(node);
}
public void insert(E element ,Long priority){
Node<E> node = new Node<>(null, element, sentinel, sentinel, priority);
baseInsert(node);
insertFixup(node);
}
@Override
public void remove(E element) {
Node<E> node = search(element);
Node<E> left = node.left;
Node<E> right = node.right;
Node<E> originalNode = null;
if (left == sentinel) {
transplant(node, right);
} else if (right == sentinel) {
transplant(node, left);
} else {
Node<E> successor = minimum(right);
originalNode = successor;
if (successor.parent != node) {
transplant(successor, successor.right);
successor.right = right;
right.parent = successor;
}
transplant(node, successor);
successor.left = left;
left.parent = successor;
}
if(originalNode != null)
removeFixup(originalNode);
}
}免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删
155-2731-8020
