有序散列
一、介绍
有序散列（Ordered Hashing）是一种散列技术，它在传统散列的基础上增加了对键的有序性的支持。传统的散列表（无序散列）通过散列函数将键映射到索引位置，而无法保证键的顺序性。而有序散列则在此基础上引入了对键的顺序性的管理，使得在散列表中存储的键值对可以按照一定的顺序进行排列
二、原理
有序散列通常通过在散列表中引入额外的数据结构来实现键的有序性管理。常见的做法是在散列表的基础上使用平衡二叉搜索树（如红黑树、AVL树等）或者有序链表来维护键的有序性。具体来说：
- 平衡二叉搜索树：在散列表的每个槽中，维护一个平衡二叉搜索树。当需要插入新的键值对时，首先根据散列函数计算键的散列码，然后将键值对插入到对应槽中的平衡二叉搜索树中。通过保持树的平衡性，可以保证键的有序性，从而实现有序散列。
- 有序链表：在散列表的每个槽中，维护一个有序链表。当需要插入新的键值对时，根据散列函数计算键的散列码，并将键值对按照顺序插入到对应槽中的有序链表中。这样，所有键值对就可以按照链表中的顺序进行排列，实现有序散列。
三、优势与应用
有序散列相比传统散列具有一些优势：
- 顺序性访问：有序散列可以支持按照键的顺序进行遍历和访问，这对于一些需要按照顺序访问数据的场景非常有用，如范围查询、有序输出等。
- 有序性操作：有序散列支持一些额外的操作，如查找最小值、最大值、范围查询等。
有序散列在数据库、文件系统、检索引擎等需要对数据进行有序管理和操作的领域有着广泛的应用。例如，在数据库中，索引就是一种有序散列结构，它可以加速对数据的查找和检索，并支持按照键的顺序进行遍历和查询。
四、实现
4.1 基于二叉搜索树
/**
* @Description 二叉搜索树
* @Author lcy
* @Date 2020/9/22 16:18
*/
public class BinarySearchTreeMap<K,V> implements BinaryTreeInfo {
/**
* 长度
*/
protected int size = 0;
/**
* 根节点
*/
protected Node<K,V> rootNode;
/**
* 排序接口实现
*/
protected Comparator<K> comparator = (o1,o2) -> {
if (o1 != null && o2 != null) {
if (o1.hashCode() == o2.hashCode() && o1.equals(o2)) {
return 0;
} else {
return o1.hashCode() - o2.hashCode();
}
} else {
throw new ServiceException("key could not be null");
}
};
public BinarySearchTreeMap(Comparator<K> comparator){
this.comparator = comparator;
}
public BinarySearchTreeMap(){
}
/**
* 添加map
* @param key key
* @param value value
* @author lcy
* @date 2021/1/5 16:17
**/
public void put(K key,V value){
add(key,value);
}
/**
* 判断key是否存在
* @param key key
* @return boolean
* @author lcy
* @date 2021/1/5 16:17
**/
public boolean constainsKey(K key){
Node<K,V> node = node(key);
return node != null;
}
/**
* 判断value是否存在
* @param value value
* @return boolean
* @author lcy
* @date 2021/1/5 16:17
**/
public boolean constainsValue(V value){
AtomicBoolean result = new AtomicBoolean(false);
inorderTraverse(null,(collection,key,value1) -> {
if (value == null ? value1 == null : value1.equals(value)) {
result.set(true);
}
});
return result.get();
}
/**
* 提供创建节点的接口
* @param key 节点值
* @param parent 父节点
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.Node<K,V>
* @author lcy
* @date 2020/11/18 8:54
**/
protected Node<K,V> createNode(K key,V value,Node<K,V> parent){
return new Node<>(key,value,parent);
}
/**
* 返回长度
*/
public int size(){
return size;
}
/**
* 判断是否为空
* @return boolean
* @author lcy
* @date 2020/9/3 20:58
**/
public boolean isEmpty(){
return size == 0;
}
/**
* 添加对象
* @param key 对象
* @author lcy
* @date 2020/9/3 20:55
**/
protected void add(K key,V value){
checkKeyNull(key);
Node<K,V> node;
//如果根节点为空，插入根节点
if (rootNode == null) {
node = createNode(key,value,null);
rootNode = node;
} else {
//获取需要插入元素的父节点
Node<K,V> parent = getParent(key);
node = createNode(key,value,parent);
int compare = comparator.compare(key,parent.key);
if (compare > 0) {
parent.right = node;
} else if (compare < 0) {
parent.left = node;
} else {
node.key = key;
}
}
size++;
//添加以后的操作
afterAdd(node);
}
/**
* 添加节点以后的操作
* @author lcy
* @date 2020/11/17 17:24
**/
protected void afterAdd(Node<K,V> node){}
/**
* 获取对象
* @param key 元素，根据传入元素compare属性比较，得出完整的属性
* @return E
* @author lcy
* @date 2020/9/3 20:56
**/
public V get(K key){
return node(key).value;
}
/**
* 清除数二叉树
* @author lcy
* @date 2020/9/3 20:56
**/
public void clear(){
rootNode = null;
size = 0;
}
/**
* 删除指定对象
* @param key 需要删除的对象
* @author lcy
* @date 2020/9/3 21:01
**/
public V remove(K key){
//获取当前对象的节点
Node<K,V> deleteNode = node(key);
if (deleteNode == null) {
return null;
}
size--;
if (deleteNode.hasTwoChildren()) {
//获取后继节点
Node<K,V> successor = successor(deleteNode);
//替换节点值为后继节点值
deleteNode.key = successor.key;
//删除节点
deleteNode = successor;
}
Node<K,V> replaceNode = deleteNode.left != null ? deleteNode.left : deleteNode.right;
if (replaceNode != null) {
replaceNode.parent = deleteNode.parent;
if (deleteNode.parent == null) {
rootNode = replaceNode;
} else if (deleteNode.isLeftChild()) {
deleteNode.parent.left = replaceNode;
} else {
deleteNode.parent.right = replaceNode;
}
////删除节点后的操作
//afterRemove(deleteNode,replaceNode);
//删除节点后的操作
afterRemove(replaceNode);
} else if (deleteNode.parent == null) {
rootNode = null;
////删除节点后的操作
//afterRemove(deleteNode,null);
//删除节点后的操作
afterRemove(deleteNode);
} else {
if (deleteNode.isLeftChild()) {
deleteNode.parent.left = null;
} else {
deleteNode.parent.right = null;
}
////删除节点后的操作
//afterRemove(deleteNode,null);
//删除节点后的操作
afterRemove(deleteNode);
}
//if (deleteNode.hasTwoChildren()) {
// //获取前驱节点、后继节点
// Node<K,V> successor = successor(deleteNode);
// //替换节点值为后继节点值
// deleteNode.key = successor.key;
// //替换节点值为后继节点值
// deleteNode.key = successor.key;
// //替换值
// parent = successor.parent;
// deleteNode = successor;
//}
////删除结点
//changeNode(parent,deleteNode);
//afterRemove(deleteNode);
return deleteNode.value;
}
/**
* 根据删除节点的父节点（可能失衡是节点）
* @param node 删除节点
* @param replaceNode 替换的节点
* @author lcy
* @date 2020/11/20 9:03
**/
protected void afterRemove(Node<K,V> node,Node<K,V> replaceNode){
}
/**
* 根据删除节点的父节点（可能失衡是节点）
* @param node 被删除的节点或者删除以后被取代的节点（只有当被删除的节点是拥有子节点并且是度为1的时候）
* @author lcy
* @date 2020/11/20 9:03
**/
protected void afterRemove(Node<K,V> node){
}
/**
* 删除节点
* @param parent 父节点
* @param deleteNode 需要删除的节点
* @author lcy
* @date 2020/11/13 10:24
**/
void changeNode(Node<K,V> parent,Node<K,V> deleteNode){
if (parent == null) {
if (deleteNode.right != null) {
rootNode = deleteNode.right;
} else if (deleteNode.left != null) {
rootNode = deleteNode.left;
} else {
rootNode = null;
}
} else {
if (parent.left == deleteNode) {
parent.left = deleteNode.left;
} else if (parent.right == deleteNode) {
parent.right = deleteNode.right;
}
}
}
/**
* 根据对象获取节点值
* @param key 需要查找的对象
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.RedBlackNode<K,V>
* @author lcy
* @date 2020/11/12 16:18
**/
public Node<K,V> node(K key){
if (key == null) {
return null;
}
Node<K,V> node = rootNode;
while (node != null) {
//通过compare方法对比
int compare = comparator.compare(key,node.key);
if (compare > 0) {
node = node.right;
} else if (compare < 0) {
node = node.left;
} else {
return node;
}
}
return null;
}
/**
* 获取父节点的值,如果传入的元素值等于某个节点，则返回当前节点值
* @param key 元素
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.RedBlackNode<K,V>
* @author lcy
* @date 2020/9/22 17:20
**/
private Node<K,V> getParent(K key){
Node<K,V> node = rootNode;
Node<K,V> parent = null;
while (node != null) {
int compare = comparator.compare(key,node.key);
parent = node;
if (compare > 0) {
node = node.right;
} else if (compare < 0) {
node = node.left;
} else {
return node;
}
}
return parent;
}
/**
* 判断元素是否为空，如果为空抛出异常
* @param key 泛型元素
* @author lcy
* @date 2020/9/22 17:52
**/
private void checkKeyNull(K key){
if (key == null) {
throw new IllegalArgumentException("key must not be null");
}
}
/**
* 前序遍历--递归
*/
public void preorderTraverse(Node<K,V> rootNode){
if (rootNode == null) {
return;
}
System.out.println(rootNode.key);
preorderTraverse(rootNode.left);
preorderTraverse(rootNode.right);
}
/**
* 中序遍历--递归
*/
public void inorderTraverse(Node<K,V> rootNode){
if (rootNode == null) {
return;
}
inorderTraverse(rootNode.left);
System.out.println(rootNode.key);
inorderTraverse(rootNode.right);
}
/**
* 后序遍历--递归
*/
public void postorderTraverse(Node<K,V> rootNode){
if (rootNode == null) {
return;
}
postorderTraverse(rootNode.left);
postorderTraverse(rootNode.right);
System.out.println(rootNode.key);
}
/**
* 前序遍历
*/
public void preorderTraverse(ViewTree<K,V> viewTree){
if (rootNode == null || viewTree == null) {
return;
}
Node<K,V> node = rootNode;
Stack<Node<K,V>> stack = new Stack<>();
while (node != null) {
//遍历根节点
viewTree.view(node.key,node.value);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
node = node.left;
} else {
if (stack.isEmpty()) {
break;
} else {
node = stack.pop();
}
}
}
}
/**
* 中序遍历
*/
public void inorderTraverse(ViewTree<K,V> viewTree,OperateTree<K,V> operateTree){
if (rootNode == null || viewTree == null) {
return;
}
//当前节点
Node<K,V> node = rootNode;
Stack<Node<K,V>> stack = new Stack<>();
//当节点不为空时
while (node != null || !stack.isEmpty()) {
//左子树入栈
while (node != null) {
stack.push(node);
node = node.left;
}
//出栈
node = stack.pop();
//操作节点
viewTree.view(node.key,node.value);
//尾部操作
if (operateTree != null) {
operateTree.operate(stack,node.key,node.value);
}
if (node.right != null) {
node = node.right;
} else {
node = null;
}
}
}
/**
* 后序遍历
*/
public void postorderTraverse(ViewTree<K,V> viewTree,OperateTree<K,V> operateTree){
if (rootNode == null || viewTree == null) {
return;
}
//当前节点
Node<K,V> node = rootNode;
//上一节点
Node<K,V> prev = null;
Stack<Node<K,V>> stack = new Stack<>();
//当节点不为空时
while (node != null || !stack.isEmpty()) {
//把根节点和左节点全部放到栈中
while (node != null) {
stack.push(node);
node = node.left;
}
//出栈
node = stack.pop();
if (node.right == null || node.right == prev) {
//操作节点
viewTree.view(node.key,node.value);
//尾部操作
if (operateTree != null) {
operateTree.operate(stack,node.key,node.value);
}
//上个节点为当前节点，往下遍历
prev = node;
//当前节点设为null，循环时赋予队列值
node = null;
} else {
//入栈
stack.push(node);
//当前节点等于右节点
node = node.right;
}
}
//后序遍历用两个栈实现
/* Stack<RedBlackNode<K,V>> stack = new Stack<>();
stack.push(rootNode);
Stack<K,V> keyStack = new Stack<>();
//后序遍历节点到keyStack栈里
while (!stack.isEmpty()) {
node = stack.pop();
keyStack.push(node.key);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
while (!keyStack.isEmpty()) {
E pop = keyStack.pop();
System.out.println(pop);
}*/
}
/**
* 层序遍历
* @param viewTree 遍历的对象的操作接口实现
* @author lcy
* @date 2020/10/12 14:33
**/
public void levelOrderTraverse(ViewTree<K,V> viewTree){
levelOrderTraverse(viewTree,null);
}
/**
* 层序遍历
* @param viewTree 遍历的对象的操作接口实现
* @param operateTree 在入栈或者入队以后的尾部操作
* @author lcy
* @date 2020/10/12 14:33
**/
public void levelOrderTraverse(ViewTree<K,V> viewTree,OperateTree<K,V> operateTree){
if (rootNode == null || viewTree == null) {
return;
}
Queue<Node<K,V>> queue = new LinkedBlockingQueue<>();
queue.offer(rootNode);
while (!queue.isEmpty()) {
Node<K,V> node = queue.poll();
//操作树
viewTree.view(node.key,node.value);
//左节点入队
if (node.left != null) {
queue.offer(node.left);
}
//右节点入队
if (node.right != null) {
queue.offer(node.right);
}
//尾部操作
if (operateTree != null) {
operateTree.operate(queue,node.key,node.value);
}
}
}
/**
* 获取当前树的高度
* @return int
* @author lcy
* @date 2020/10/12 15:02
**/
public int height(){
return height(rootNode);
}
/**
* 获取当前节点高度
* @param node 节点对象
* @return int
* @author lcy
* @date 2020/10/12 15:01
**/
public int height(Node<K,V> node){
if (node == null) {
return 0;
}
//当前节点的高度，默认根节点，所以是1
AtomicInteger height = new AtomicInteger(1);
//当前节点在栈或队列的子节点数，默认根节点，所以是1
AtomicInteger levelSize = new AtomicInteger(1);
//层序遍历
levelOrderTraverse(
//操作遍历值，入队之前
(key,value) -> levelSize.addAndGet(-1)
//入队以后的操作
,(collection,key,value) -> {
//如果子节点数为0，说明已经到下一个节点
if (levelSize.get() == 0 && collection.size() > 0) {
height.addAndGet(1);
levelSize.set(collection.size());
}
}
);
return height.get();
}
/**
* 判断是否为完全二叉树
* @return boolean
* @author lcy
* @date 2020/10/12 16:23
**/
public boolean isCompleteTree(){
return isCompleteTree(rootNode);
}
/**
* 判断节点的子树是否为完全二叉树
* @param node 节点值
* @return boolean
* @author lcy
* @date 2020/10/12 16:23
**/
private boolean isCompleteTree(Node<K,V> node){
if (node == null) {
return false;
}
Queue<Node<K,V>> queue = new LinkedBlockingQueue<>();
queue.offer(node);
//判断是否已经到叶子节点
boolean isLeaf = false;
while (!queue.isEmpty()) {
Node<K,V> tmpNode = queue.poll();
//如果叶子节点标记为true，但是实际不是叶子节点，返回false
if (isLeaf && !tmpNode.isLeaf()) {
return false;
}
//左节点入队
if (tmpNode.left != null) {
queue.offer(tmpNode.left);
//如果左节点为空，右节点不为空直接返回
} else if (tmpNode.right != null) {
return false;
}
//右节点入队
if (tmpNode.right != null) {
queue.offer(tmpNode.right);
//如果右节点为空。不管左边为不为空，后面的遍历的都要是叶子节点。标记修改
} else {
isLeaf = true;
}
}
return true;
}
/**
* 查找当前节点的前驱节点（中序遍历的前一个节点）
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.RedBlackNode<K,V>
* @author lcy
* @date 2020/10/19 17:43
**/
public Node<K,V> predecessor(Node<K,V> node){
return getInorderNode(node).get("predecessor");
}
/**
* 查找当前节点的后继节点（中序遍历的后一个节点）
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.RedBlackNode<K,V>
* @author lcy
* @date 2020/10/19 17:43
**/
public Node<K,V> successor(Node<K,V> node){
return getInorderNode(node).get("successor");
}
/**
* 根据flag标志判断获取传入节点的前驱节点还是后继节点
* @param node 节点
* @return BaseMap<String,RedBlackNode < E>> 值：predecessor为前驱节点，successor为后继节点
* @author lcy
* @date 2020/11/13 10:54
**/
public Map<String,Node<K,V>> getInorderNode(Node<K,V> node){
Map<String,Node<K,V>> map = new HashMap<>(3);
if (rootNode == null) {
return null;
}
//当前节点
Node<K,V> tmpNode = rootNode;
Node<K,V> prev = null;
Stack<Node<K,V>> stack = new Stack<>();
//当节点不为空时
while (tmpNode != null || !stack.isEmpty()) {
//左子树入栈
while (tmpNode != null) {
stack.push(tmpNode);
tmpNode = tmpNode.left;
}
//出栈
tmpNode = stack.pop();
map.put("predecessor",prev);
if (prev == node) {
map.put("successor",tmpNode);
return map;
}
prev = tmpNode;
if (tmpNode.right != null) {
tmpNode = tmpNode.right;
} else {
tmpNode = null;
}
}
return null;
}
@Override public Object root(){
return rootNode;
}
@Override public Object left(Object node){
return ((Node)node).left;
}
@Override public Object right(Object node){
return ((Node)node).right;
}
@Override public Object string(Object node){
return node;
}
/**
* 遍历二叉树做的操作
* @author lcy
* @date 2020/9/28 9:17
**/
public interface ViewTree<K,V> {
/**
* 二叉树遍历操作
* @param key key
* @param value value
* @author lcy
* @date 2020/10/12 14:30
**/
void view(K key,V value);
}
/**
* 遍历二叉树,在尾部做操作
* @author lcy
* @date 2020/9/28 9:17
**/
public interface OperateTree<K,V> {
/**
* 操作方法
* @param collection 栈或者队列对象
* @param key key
* @param value value
* @author lcy
* @date 2020/10/12 14:49
**/
void operate(Collection<Node<K,V>> collection,K key,V value);
}
/**
* 树节点内部类
* @author lcy
* @date 2020/9/7 10:22
**/
protected static class Node<K,V> {
/**
* 当前节点key--比较值
*/
K key;
/**
* 当前节点value
*/
V value;
/**
* 左节点值
*/
Node<K,V> left;
/**
* 右节点值
*/
Node<K,V> right;
/**
* 父节点值
*/
Node<K,V> parent;
public Node(K key,V value,Node<K,V> parent){
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* 判断是否叶子节点
* @return boolean
* @author lcy
* @date 2020/10/16 15:46
**/
public boolean isLeaf(){
return left == null && right == null;
}
/**
* 判断是否有左右子树
* @return boolean
* @author lcy
* @date 2020/10/16 15:46
**/
public boolean hasTwoChildren(){
return left != null && right != null;
}
/**
* 判断是否有子节点
* @return boolean
* @author lcy
* @date 2020/10/16 15:46
**/
public boolean hasChild(){
return left != null || right != null;
}
/**
* 判断是否左子树
* @return boolean
* @author lcy
* @date 2020/11/18 15:23
**/
public boolean isLeftChild(){
return parent != null && parent.left == this;
}
/**
* 判断是否右子树
* @return boolean
* @author lcy
* @date 2020/11/18 15:23
**/
public boolean isRightChild(){
return parent != null && parent.right == this;
}
/**
* 返回兄弟节点
* @return Node<K,V>
* @author lcy
* @date 2020/11/18 15:23
**/
public Node<K,V> sibling(){
//如果是左子节点，返回父节点的右子节点
if (isLeftChild()) {
return parent.right;
}
//如果是右子节点，返回父节点的左子节点
if (isRightChild()) {
return parent.left;
}
//如果是根节点，返回null
return null;
}
@Override public String toString(){
return "key={" + key + "},value={" + value + "}";
}
}
public static void main(String[] args){
int[] ageArray = {44,31,3,2,6,88,34,13,32,77,74,35,89,1,-1,-3,-5};
int[] weightArray = {144,131,103,102,106,188,134,113,132,177,174,135,189,1,-1,-3,-5};
BinarySearchTreeMap<Integer,Person> binarySearchTree =
new BinarySearchTreeMap<>();
for (int i = 0; i < ageArray.length; i++) {
binarySearchTree.add(ageArray[i],new Person(ageArray[i],weightArray[i],String.valueOf(i)));
}
System.out.println("-------------print-------------");
BinaryTrees.print(binarySearchTree);
System.out.println();
System.out.println("---------------------------------");
binarySearchTree.remove(6);
BinaryTrees.print(binarySearchTree);
System.out.println();
binarySearchTree.remove(2);
BinaryTrees.print(binarySearchTree);
System.out.println();
binarySearchTree.remove(32);
BinaryTrees.print(binarySearchTree);
System.out.println();
binarySearchTree.add(33,new Person(33,133,"0"));
BinaryTrees.print(binarySearchTree);
System.out.println();
binarySearchTree.remove(31);
BinaryTrees.print(binarySearchTree);
System.out.println();
System.out.println("-------------print-------------");
List<Person> keyList = new ArrayList<>();
System.out.println("-------------前序遍历-------------");
binarySearchTree.preorderTraverse(binarySearchTree.rootNode);
System.out.println("---------------------------------");
binarySearchTree.preorderTraverse((key,value) -> System.out.println(String.valueOf(key) + value));
System.out.println("-------------前序遍历-------------");
System.out.println("-------------中序遍历-------------");
binarySearchTree.inorderTraverse(binarySearchTree.rootNode);
System.out.println("---------------------------------");
binarySearchTree.inorderTraverse((key,value) -> {System.out.println(String.valueOf(key) + value);},null);
System.out.println("-------------中序遍历-------------");
System.out.println("-------------后序遍历-------------");
binarySearchTree.postorderTraverse(binarySearchTree.rootNode);
System.out.println("---------------------------------");
binarySearchTree.postorderTraverse((key,value) -> {System.out.println(String.valueOf(key) + value);},null);
System.out.println("-------------后序遍历-------------");
System.out.println("-------------层序遍历-------------");
binarySearchTree.levelOrderTraverse(keyList :: add);
binarySearchTree.levelOrderTraverse((key,value) -> {System.out.println(String.valueOf(key) + value);});
System.out.println("-------------层序遍历-------------");
System.out.println(Arrays.toString(keyList.toArray()));
System.out.println(binarySearchTree.height());
System.out.println(binarySearchTree.isCompleteTree());
}
}4.2 基于平衡二叉搜索树
/**
* @Description 平衡二叉搜索树 --旋转的方法
* @Author lcy
* @Date 2020/11/25 16:58
*/
public class BalanceBinarySearchTreeMap<K,V> extends BinarySearchTreeMap<K,V> {
public BalanceBinarySearchTreeMap(Comparator<K> comparator){
super(comparator);
}
public BalanceBinarySearchTreeMap(){
super();
}
/**
* 左旋转
* @param node 需要旋转的节点
* @author lcy
* @date 2020/11/18 16:21
**/
protected void rotateLeft(Node<K,V> node){
//左旋转node节点的右节点--parentNode
Node<K,V> parentNode = node.right;
//需要node节点的右子树改为当前parentNode的左子树
node.right = parentNode.left;
//父节点值替换
if (node.right != null) {
node.right.parent = node;
}
//parent节点的左节点为node节点
parentNode.left = node;
//父节点替换
parentNode.parent = node.parent;
//node节点的父节点指向--旋转以后子树根节点变换
if (node.isLeftChild()) {
parentNode.parent.left = parentNode;
} else if (node.isRightChild()) {
parentNode.parent.right = parentNode;
} else {
//如果是根节点
rootNode = parentNode;
}
node.parent = parentNode;
}
/**
* 右旋转
* @param node 需要旋转的节点
* @author lcy
* @date 2020/11/18 16:21
**/
protected void rotateRight(Node<K,V> node){
//左旋转node节点的右节点--parentNode
Node<K,V> parentNode = node.left;
//需要node节点的右子树改为当前parentNode的左子树
node.left = parentNode.right;
//父节点值替换
if (node.left != null) {
node.left.parent = node;
}
//parent节点的左节点为node节点
parentNode.right = node;
//父节点替换
parentNode.parent = node.parent;
//node节点的父节点指向--旋转以后子树根节点变换
if (node.isLeftChild()) {
parentNode.parent.left = parentNode;
} else if (node.isRightChild()) {
parentNode.parent.right = parentNode;
} else {
//如果是根节点
rootNode = parentNode;
}
node.parent = parentNode;
}
/**
* 统一旋转，旋转以后的最后结果为：
* ┌──d──┐
* │ │
* ┌─b─┐ ┌─f─┐
* │ │ │ │
* a c e g
* @param root 原树的根节点
* @param b b节点
* @param c c节点
* @param d d节点
* @param e e节点
* @param f f节点
* @author lcy
* @date 2020/11/19 14:42
**/
protected void rotate(Node<K,V> root,Node<K,V> b,Node<K,V> c,Node<K,V> d,Node<K,V> e,Node<K,V> f){
//设置新的根节点
d.parent = root.parent;
if (root.isLeftChild()) {
root.parent.left = d;
} else if (root.isRightChild()) {
root.parent.right = d;
} else {
rootNode = d;
}
//设置d的左子树
if (c != null) {
c.parent = b;
}
b.right = c;
//设置d的右子树
if (e != null) {
e.parent = f;
}
f.left = e;
//设置b，f的父节点指向
d.left = b;
d.right = f;
b.parent = d;
f.parent = d;
}
}4.3 基于红黑树
/**
* @Description 红黑树
* @Author lcy
* @Date 2020/11/17 11:13
*/
public class RedBlackTreeMap<K,V> extends BalanceBinarySearchTreeMap<K,V> {
/**
* 红色节点
*/
private static final boolean RED = true;
/**
* 黑色节点
*/
private static final boolean BLACK = false;
public RedBlackTreeMap(Comparator<K> comparator){
super(comparator);
}
public RedBlackTreeMap(){
super();
}
@Override protected void afterAdd(Node<K,V> node){
Stack<Node<K,V>> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
node = stack.pop();
Node<K,V> parent = node.parent;
//如果是根节点
if (parent == null) {
//变成黑色
changeBlack(node);
continue;
}
//如果父节点是黑色--维持红黑树平衡，不需要操作
if (isBlack(parent)) {
continue;
}
//获取uncle节点--叔父节点
Node<K,V> uncle = parent.sibling();
//祖父节点--祖父节点一定染成红色
Node<K,V> grandParent = changeRed(parent.parent);
//叔父节点是红色
if (isRed(uncle)) {
//父节点和叔父节点染成黑色
changeBlack(parent);
changeBlack(uncle);
//将祖父节点当成新添加的节点处理
stack.push(grandParent);
continue;
}
if (parent.isLeftChild()) {
if (node.isLeftChild()) {
//LL--父节点染成黑色，祖父节点染成红色
changeBlack(parent);
} else {
//LR--当前节点和祖父节点染成黑色，父节点染成红色
//父节点左旋转，祖父节点右旋转
changeBlack(node);
rotateLeft(parent);
}
rotateRight(grandParent);
} else {
if (node.isLeftChild()) {
//RL--当前节点和祖父节点染成黑色，父节点染成红色
//父节点右旋转，祖父节点左旋转
changeBlack(node);
rotateRight(parent);
} else {
//RR--父节点染成黑色，祖父节点染成黑色,左旋转
changeBlack(parent);
}
rotateLeft(grandParent);
}
}
}
@Override protected void afterRemove(Node<K,V> node){
Stack<Node<K,V>> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
//二叉搜索树删除以后的操作，如果删除的节点是度为2的节点，即有两个子节点，node为该节点的后继节点。
node = stack.pop();
//如果替换的节点是红色
//如果是删除的节点是红色节点，直接删除。如果是用于取代删除节点的子节点是红色，进行染色。然后直接返回。
if (isRed(node)) {
//改成黑色，保持4阶B树和红黑树性质，根节点一定要有黑色，因为删除了黑色节点，必须重新生成一个黑色。
changeBlack(node);
continue;
}
Node<K,V> parent = node.parent;
//如果黑色节点是根节点--不需要处理
if (parent == null) {
continue;
}
//兄弟节点--如果是叶子节点，parent已经不指向node了。即原本指向node节点的指针已经为null。
//但是如果是下溢的情况，parent递归调用，因为parent的父节点还是它，所以要再增加一个不为空的情况判断。
boolean left = parent.left == null || node.isLeftChild();
//如果node节点是左子节点，取右子节点
Node<K,V> siblingNode = left ? parent.right : parent.left;
//如果被删除的子节点在左边
if (left) {
//如果被删除的子节点在左边
//如果兄弟节点是红色，将父节点旋转，将兄弟节点转成黑色
if (isRed(siblingNode)) {
//染色
changeBlack(siblingNode);
changeRed(parent);
//旋转
rotateLeft(parent);
//兄弟节点改变
siblingNode = parent.right;
}
} else {
//如果被删除的子节点在右边
//如果兄弟节点是红色，将父节点旋转，将兄弟节点转成黑色
if (isRed(siblingNode)) {
//染色
changeBlack(siblingNode);
changeRed(parent);
//旋转
rotateRight(parent);
//兄弟节点改变
siblingNode = parent.left;
}
}
//兄弟节点是黑色,一定是黑色
//如果兄弟节点的子节点都是黑色
if (isBlack(siblingNode.left) && isBlack(siblingNode.right)) {
//如果都不为黑色，说明没有子节点。因为没有子节点，父节点要向下合并。即染色
boolean isParentBlack = isBlack(parent);
changeBlack(parent);
changeRed(siblingNode);
//如果父节点是黑色，说明上面的节点还存在下溢
if (isParentBlack) {
//相当于二叉搜索树的叶子节点
stack.push(parent);
}
} else {
if (left) {
//兄弟节点的子节点不都为黑色
//如果兄弟节点的子节点为黑色，即不为红色，对兄弟节点进行左旋转。
if (isBlack(siblingNode.right)) {
rotateRight(siblingNode);
siblingNode = parent.right;
}
//对父节点进行右旋转
rotateLeft(parent);
} else {
//兄弟节点的子节点不都为黑色
//如果兄弟节点的子节点为黑色，即不为红色，对兄弟节点进行左旋转。
if (isBlack(siblingNode.left)) {
rotateLeft(siblingNode);
siblingNode = parent.left;
}
//对父节点进行右旋转
rotateRight(parent);
}
//旋转以后中心节点的颜色为parent的颜色，新的子节点颜色为黑色
changeColor(siblingNode,colorOf(parent));
changeBlack(siblingNode.left);
changeBlack(siblingNode.right);
}
}
}
@Override protected Node<K,V> createNode(K key,V value,Node<K,V> parent){
return new RedBlackNode<>(key,value,parent);
}
/**
* 节点染色
* @param node 传入节点值
* @param color 颜色
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.Node<K,V>
* @author lcy
* @date 2020/11/25 9:38
**/
private Node<K,V> changeColor(Node<K,V> node,boolean color){
if (node == null) {
return node;
}
//节点染色
((RedBlackNode<K,V>)node).color = color;
return node;
}
/**
* 节点染色
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.Node<K,V>
* @author lcy
* @date 2020/11/25 9:38
**/
private Node<K,V> changeRed(Node<K,V> node){
return changeColor(node,RED);
}
/**
* 节点染色
* @param node 传入节点值
* @return com.lcy.study.algoithm.tree.set.BinarySearchHashMap.Node<K,V>
* @author lcy
* @date 2020/11/25 9:38
**/
private Node<K,V> changeBlack(Node<K,V> node){
return changeColor(node,BLACK);
}
/**
* 获取当前节点的颜色
* @param node 节点对象
* @return boolean
* @author lcy
* @date 2020/11/25 14:09
**/
private boolean colorOf(Node<K,V> node){
return node != null ? ((RedBlackNode<K,V>)node).color : BLACK;
}
/**
* 判断节点是否为黑色
* @param node 节点值
* @return boolean
* @author lcy
* @date 2020/11/25 14:12
**/
private boolean isBlack(Node<K,V> node){
return colorOf(node) == BLACK;
}
/**
* 判断节点是否为黑色
* @param node 节点值
* @return boolean
* @author lcy
* @date 2020/11/25 14:12
**/
private boolean isRed(Node<K,V> node){
return colorOf(node) == RED;
}
/**
* 树节点内部类
* @author lcy
* @date 2020/9/7 10:22
**/
protected static class RedBlackNode<K,V> extends Node<K,V> {
/**
* 节点颜色，红色为true，黑色为false。新添加的默认为红色节点
*/
boolean color = RED;
public RedBlackNode(K key,V value,Node<K,V> parent){
super(key,value,parent);
}
@Override public String toString(){
return "(" + (color ? "red" : "black") + ")" + key
//+ ",value={" + value + "}"
;
}
}
public static void main(String[] args){
int[] ageArray = {44,31,3,2,6,88,34,13,32,77,74,35,89,1,78,53,12,23,67,54,34,98,78,67,78,90,97,124,266,243,4,5,7,9,45,33,8};
int[] weightArray = {144,131,103,102,106,188,134,113,132,177,174,135,189,1,78,53,12,23,67,54,34,98,78,67,78,90,97,124,266,243,4,5
,7,9,45,33,8};
RedBlackTreeMap<Integer,Person> redBlackTree = new RedBlackTreeMap<>();
for (int i = 0; i < ageArray.length; i++) {
redBlackTree.add(ageArray[i],new Person(ageArray[i],weightArray[i],String.valueOf(i)));
}
System.out.println("-------------print-------------");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(8);
System.out.println("删除8！");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(35);
System.out.println("删除35！");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(90);
System.out.println("删除90！");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(97);
System.out.println("删除97！");
BinaryTrees.print(redBlackTree);
System.out.println();
redBlackTree.remove(74);
System.out.println("删除74！");
BinaryTrees.print(redBlackTree);
System.out.println();
System.out.println("-------------print-------------");
}
}五、总结
有序散列是一种在传统散列基础上增加了对键的顺序性管理的技术。通过在散列表中引入额外的数据结构来维护键的有序性，可以实现对数据的有序管理和操作。有序散列在许多领域都有着广泛的应用，并且在某些需要对数据进行有序操作的场景中具有明显的优势。