数据结构与算法-红黑树快速入门

tech2023-02-17  126

概述

《算法导论》中的红黑树的概念

每个节点只能是红色或者黑色根节点都是黑色的每一个叶子节点(还有叶子节点存放的空节点)都是黑色如果一个节点为红色,那么他的孩子节点都为黑色从任意一个节点到叶子节点,经过的黑色节点是一样的(因为红黑树是2-3树的另一种表达方式,2-3树是绝对平衡的,所以红黑树也是一种黑平衡的树)

算法4中的说法

红黑树与2-3树是等价的,同样的红黑树页满足二分搜索数的基本性质

2-3树

特点

一个节点可以存放一个或者两个元素,且可以连接两个或者三个的元素 2-3树是一棵绝对平衡的树(即任意节点的高度差都是0)

2-3树维持平衡示例

如下图所示,按照图中给定元素顺序插入元素,可以看出每当树失衡时,都会将分裂后的节点的父节点向上融合

红黑树与2-3树的关系

如下图所示,红黑树中红色节点就是表示2-3树种三节点的左边的元素

如下图所示,2-3树的树转换为红黑树的样子如下图所示

红黑树的实现

先行步骤

颜色的翻转

图解

如下所示,上图为红黑树相当于对应下方的2-3树的操作,可以看出加入66之后2-3树编程四节点需要向上融合,所以对应红黑树也需要将元素值为42的节点变为红色即与指向一个节点融合为“2节点”。

实现

// 颜色翻转 private void flipColors(Node node) { node.color = RED; node.left.color = BLACK; node.right.color = BLACK; }

右旋转

图解

如下图所示,一个添加节点后变成不平衡树的红黑树,所以我们需要向右旋转,再更新一下颜色,因为会融合成“4节点”,所以旋转后根节点和原来节点颜色一样,旧的根节点变成红色表示与根节点融合

实现代码

// node x // / \ 右旋转 / \ // x T2 -------> y node // / \ / \ // y T1 T1 T2 private Node rightRotate(Node node) { Node x = node.left; //右旋转 node.left = x.right; x.right = node; x.color = node.color; node.color = RED; return x; }

LR型的情况

图解

这种情况和avl树种lr型情况很像,解决方式也很简单,左旋转后再右旋转更新一下颜色即可。需要补充的是,下图已经包含上述先行步骤的所有情况,所以我们只需针对下图情况下三个独立的if即可完成红黑树的添加操作。

实现代码

/** * 向以node为根的红黑树中插入元素(key, value),递归算法 * * @param node * @param key * @param value * @return 返回插入新节点后红黑树树的根 */ private Node add(Node node, K key, V value) { if (node == null) { size++; return new Node(key, value);// 默认为红色 } if (key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if (key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else // key.compareTo(node.key) == 0 node.value = value; //2-3树中二节点右倾的情况 if (isRed(node.right) && !isRed(node.left)) node = leftRotate(node); if (isRed(node.left) && isRed(node.left.left)) node = rightRotate(node); if (isRed(node.left) && isRed(node.right)) flipColors(node); return node; }

完整代码

package com.study.RBTreeDemo; import java.util.ArrayList; public class RBTree<K extends Comparable<K>, V> { private static final boolean RED = true; private static final boolean BLACK = false; private class Node { public K key; public V value; public Node left, right; public boolean color; public Node(K key, V value) { this.key = key; this.value = value; left = null; right = null; color = RED; } } private Node root; private int size; public RBTree() { root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } /** * 实现为空的节点一律为黑色 * * @param node * @return */ private boolean isRed(Node node) { if (node == null) return BLACK; return node.color; } // 向二分搜索树中添加新的元素(key, value) public void add(K key, V value) { root = add(root, key, value); } /** * 向以node为根的红黑树中插入元素(key, value),递归算法 * * @param node * @param key * @param value * @return 返回插入新节点后红黑树树的根 */ private Node add(Node node, K key, V value) { if (node == null) { size++; return new Node(key, value);// 默认为红色 } if (key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if (key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else // key.compareTo(node.key) == 0 node.value = value; //2-3树中二节点右倾的情况 if (isRed(node.right) && !isRed(node.left)) node = leftRotate(node); if (isRed(node.left) && isRed(node.left.left)) node = rightRotate(node); if (isRed(node.left) && isRed(node.right)) flipColors(node); return node; } // node x // / \ 左旋转 / \ // T1 x ---------> node T3 // / \ / \ // T2 T3 T1 T2 /** * 红黑树向左旋转 * * @param node * @return 旋转后的根节点 */ private Node leftRotate(Node node) { Node x = node.right; node.right = x.left; x.left = node; x.color = node.color; node.color = RED; return x; } // 颜色翻转 private void flipColors(Node node) { node.color = RED; node.left.color = BLACK; node.right.color = BLACK; } // node x // / \ 右旋转 / \ // x T2 -------> y node // / \ / \ // y T1 T1 T2 private Node rightRotate(Node node) { Node x = node.left; //右旋转 node.left = x.right; x.right = node; x.color = node.color; node.color = RED; return x; } // 返回以node为根节点的二分搜索树中,key所在的节点 private Node getNode(Node node, K key) { if (node == null) return null; if (key.equals(node.key)) return node; else if (key.compareTo(node.key) < 0) return getNode(node.left, key); else // if(key.compareTo(node.key) > 0) return getNode(node.right, key); } public boolean contains(K key) { return getNode(root, key) != null; } public V get(K key) { Node node = getNode(root, key); return node == null ? null : node.value; } public void set(K key, V newValue) { Node node = getNode(root, key); if (node == null) throw new IllegalArgumentException(key + " doesn't exist!"); node.value = newValue; } // 返回以node为根的二分搜索树的最小值所在的节点 private Node minimum(Node node) { if (node.left == null) return node; return minimum(node.left); } // 删除掉以node为根的二分搜索树中的最小节点 // 返回删除节点后新的二分搜索树的根 private Node removeMin(Node node) { if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } node.left = removeMin(node.left); return node; } // 从二分搜索树中删除键为key的节点 public V remove(K key) { Node node = getNode(root, key); if (node != null) { root = remove(root, key); return node.value; } return null; } private Node remove(Node node, K key) { if (node == null) return null; if (key.compareTo(node.key) < 0) { node.left = remove(node.left, key); return node; } else if (key.compareTo(node.key) > 0) { node.right = remove(node.right, key); return node; } else { // key.compareTo(node.key) == 0 // 待删除节点左子树为空的情况 if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } // 待删除节点右子树为空的情况 if (node.right == null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } // 待删除节点左右子树均不为空的情况 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } } public static void main(String[] args) { System.out.println("Pride and Prejudice"); ArrayList<String> words = new ArrayList<>(); if (FileOperation.readFile("F:\\Red-Black-Tree\\src\\pride-and-prejudice.txt", words)) { System.out.println("Total words: " + words.size()); RBTree<String, Integer> map = new RBTree<>(); for (String word : words) { if (map.contains(word)) map.set(word, map.get(word) + 1); else map.add(word, 1); } System.out.println("Total different words: " + map.getSize()); System.out.println("Frequency of PRIDE: " + map.get("pride")); System.out.println("Frequency of PREJUDICE: " + map.get("prejudice")); } System.out.println(); } }

总结

若添加的节点值完全随机,二分搜索树最适合不过。若是出现极端情况,二分搜索树极有可能变成链表。

对于查询avl最合适不过。他的平衡高度为logn比红黑树的“黑平衡”那种2logn的平衡要出色很多

若需要增删改查等综合操作,建议使用红黑树,红黑树虽然不是最优但是综合上是最优的

最新回复(0)