資訊專欄INFORMATION COLUMN
摘要：如果用數(shù)組存儲(chǔ)二叉樹，假設(shè)父節(jié)點(diǎn)下標(biāo)為，則其左孩子的下標(biāo)是，右孩子的下標(biāo)是。算法基本思路創(chuàng)建一個(gè)水平數(shù)組，水平數(shù)組的長(zhǎng)度為滿二叉樹中的節(jié)點(diǎn)總數(shù)，將二叉樹的所有節(jié)點(diǎn)，按滿二叉樹的樣子，投影到水平數(shù)組上，每個(gè)節(jié)點(diǎn)在水平數(shù)組中都對(duì)就一個(gè)位置。
一、結(jié)點(diǎn)
package com.company.RedBlackTree;
/**
* Created by jiayi on 2016/10/29.
*/
enum colors{
red,black;
};
public class RedBlackTreeNode implements Cloneable {
colors color;
int key;
RedBlackTreeNode left;
RedBlackTreeNode right;
RedBlackTreeNode p;
int depth;
public RedBlackTreeNode clone() throws CloneNotSupportedException{ //淺拷貝
RedBlackTreeNode cloned = (RedBlackTreeNode) super.clone();
return cloned;
}
RedBlackTreeNode(){
color = colors.black;
key = 0;
left = null;
right = null;
p = null;
depth = 0;
}
RedBlackTreeNode(int key){
color = colors.black;
this.key = key;
left = null;
right = null;
p = null;
depth = 0;
}
public boolean equals(RedBlackTreeNode x){
if(x.key == key && x.color == color && x.left == left && x.right == right){
return true;
}else {
return false;
}
}
}
二、紅黑樹的插入（RBInsert）、刪除（RBDelete）、連接（RBJoin）
package com.company.RedBlackTree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Map;
import java.util.HashMap;
/**
* Created by jiayi on 2016/10/29.
*/
public class RedBlackTree implements Cloneable{
public RedBlackTreeNode nil;
public RedBlackTreeNode root;
public int N;
public RedBlackTree(){
nil = new RedBlackTreeNode();
root = nil;
}
public RedBlackTree(RedBlackTreeNode root){
this.root = root;
nil = new RedBlackTreeNode();
}
public void test(int[] a){
for( int i = 0 ; i < a.length ; i++ ){
RedBlackTreeNode temp = new RedBlackTreeNode(a[i]);
RBInsert(temp);
bfsTree();
//Print();
}
/*bfsTree();
RedBlackTreeNode temp = RBSearch(root,a[5]);
RBDelete(temp);
bfsTree();*/
//Print();
}
// 計(jì)算某節(jié)點(diǎn)在整棵樹的第幾層(ROOT為第1層)
public int getLevelOfFullTree(RedBlackTreeNode node) {
int depth = 0;
RedBlackTreeNode t = node;
while (t != nil) {
depth++;
t = t.p;
}
return depth;
}
// 樹形本層節(jié)點(diǎn)打印
private void printTreeLevel(String[] nodes) {
System.out.print("
|");
for (int j = 0; j < nodes.length; j++) {
if (nodes[j] == null||nodes[j].length() == 0) {
// 打印兩位數(shù)字的占位符
System.out.printf("---");
} else {
// 打印節(jié)點(diǎn)
System.out.printf("%3s", nodes[j]);
// 重置數(shù)組
nodes[j] = "";
}
}
System.out.print("|");
}
public void bfsTree() {
System.out.print("
------------------ 樹形打印開始 ------------------");
if (this.root.equals( nil)) {
System.out.print("
樹為pw");
return;
}
// 二叉樹的高度
int maxLevel = getDepth(root);
// 滿二叉樹時(shí)的總結(jié)點(diǎn)數(shù)
int fullTotal = (int) Math.pow(2, maxLevel) - 1;
// 水平數(shù)組
//int[] nodes = new int[fullTotal];
String[] nodes = new String[fullTotal];
// 上一個(gè)節(jié)點(diǎn)的層次
int prevLevel = 1;
// 每層的起始下標(biāo)
int start = 0;
// 每一層的元素的間距
int stepSize = 0;
// 廣度優(yōu)先遍歷
Queue queue = new LinkedList<>();
queue.offer(root);
RedBlackTreeNode node = nil;
// 如果用數(shù)組存儲(chǔ)二叉樹，indexMap中存儲(chǔ)各節(jié)點(diǎn)對(duì)應(yīng)數(shù)組的下標(biāo)
Map indexMap = new HashMap();
while (!queue.isEmpty()) {
// 刪除隊(duì)列頭結(jié)點(diǎn)
node = queue.poll();
// 某節(jié)點(diǎn)在整棵樹的第幾層(ROOT為第1層)
int levelOfFullTree = getLevelOfFullTree(node);
// 如果當(dāng)前深度比前一個(gè)節(jié)點(diǎn)的嘗試大,則開始的新一層的節(jié)點(diǎn)訪問
if (levelOfFullTree > prevLevel) {
// 打印層次的節(jié)點(diǎn)
printTreeLevel(nodes);
}
// 計(jì)算新的層次的開始下標(biāo)與步長(zhǎng)
start = (int) Math.pow(2, maxLevel - levelOfFullTree) - 1;
stepSize = (int) Math.pow(2, maxLevel - levelOfFullTree + 1);
// System.out.print("
" + "start:" + start + ",stepSize:" + stepSize);
// 記錄節(jié)點(diǎn)的下標(biāo)
int idx = -1;
if (node == root) {
indexMap.put(node.key, 1);
idx = 1;
} else{
if (node == node.p.left) {
idx = 2 * indexMap.get(node.p.key) - 1;
} else if (node == node.p.right) {
idx = 2 * indexMap.get(node.p.key);
}
indexMap.put(node.key, idx);
}
// 計(jì)算映射到水平數(shù)組的位置
int y = start + (idx - 1) * stepSize;
String c;
if(node.color == colors.black){
c = "b";
}else {
c = "r";
}
nodes[y] = String.valueOf(node.key) + c ;
// System.out.print("
" + "node.value:" + node.value + ",y:" + y);
// 將節(jié)點(diǎn)的左孩子加入隊(duì)列
if (!node.left.equals( nil)) {
queue.offer(node.left);
}
// 將節(jié)點(diǎn)的右孩子加入隊(duì)列
if (!node.right.equals( nil)) {
queue.offer(node.right);
}
// 保留層次數(shù),為下次循環(huán)使用
prevLevel = levelOfFullTree;
}
// 打印最底層的節(jié)點(diǎn)，因?yàn)閣hile的推出，最底層次的節(jié)點(diǎn)沒有打印，在這里多帶帶打印
this.printTreeLevel(nodes);
System.out.print("
------------------ 樹形打印結(jié)束 ------------------");
}
// 計(jì)算以某節(jié)點(diǎn)為根的樹的深度(從1開始)
public int getDepth(RedBlackTreeNode node) {
if (node.equals( nil)) {
return 0;
}
return 1 + Math.max(this.getDepth(node.left), this.getDepth(node.right));
}
/**
* 二叉樹的廣度優(yōu)先遍歷，按照樹形打印此樹
*
*
* 算法用到的參數(shù)：
* 1：二叉樹的最大深度。
* 2：每個(gè)節(jié)點(diǎn)在二叉樹中的層次Level，從1開始。
* 3：每個(gè)節(jié)點(diǎn)在該層中的序號(hào)indexOfLevel，從1開始。
* 注：
* (1)Level和indexOfLevel可以在廣度優(yōu)先遍歷時(shí)用計(jì)數(shù)器實(shí)現(xiàn)。
* (2)Level和indexOfLevel也可以在向樹中插入新節(jié)點(diǎn)時(shí)，初始化到節(jié)點(diǎn)中。
* 如果用數(shù)組存儲(chǔ)二叉樹，假設(shè)父節(jié)點(diǎn)下標(biāo)為i，則其左孩子的下標(biāo)是2*i-1，右孩子的下標(biāo)是2*i+1。
*
* 算法基本思路：
* (1)：創(chuàng)建一個(gè)水平數(shù)組，水平數(shù)組的長(zhǎng)度為 "滿二叉樹" 中的節(jié)點(diǎn)總數(shù)，將二叉樹的所有節(jié)點(diǎn)，按滿二叉樹的樣子，投影到水平數(shù)組上，每個(gè)節(jié)點(diǎn)在水平數(shù)組中都對(duì)就一個(gè)位置。
* (2)：我們總結(jié)一下，對(duì)于每一個(gè)層級(jí)，映射到水平數(shù)組后，第一個(gè)節(jié)點(diǎn)的開始下標(biāo)=s，本層任意相鄰節(jié)點(diǎn)的步長(zhǎng)(間距)=d，如果下所示
* 層級(jí) 起始下標(biāo) 步長(zhǎng)
* 1 2^3-1=7 2^4=16
* 2 2^2-1=3 2^3=8
* 3 2^1-1=1 2^2=4
* 4 2^0-1=0 2^1=2
* (3)：有了以上數(shù)據(jù)，我們可以計(jì)算出，任意一層，任意一節(jié)點(diǎn)在水平數(shù)組中的下標(biāo)，
* 下標(biāo)=起始下標(biāo)+(該節(jié)點(diǎn)所在層次-1)*步長(zhǎng)
* (4)：OK，每一次每個(gè)節(jié)點(diǎn)的位置確定了，樹形圖自然也確定了。
*
* 另：
* 如果想要讓輸出特別規(guī)矩，我們必須：
* 1：先確定每個(gè)節(jié)點(diǎn)的值(即輸出的內(nèi)容)最多占多少個(gè)字符寬度，假設(shè)為flength。
* 在輸出樹的過(guò)程中，不論遇到空值還是有值，都格式化輸出，長(zhǎng)度不足flength的，用空格補(bǔ)齊。
* 2：可以適當(dāng)?shù)膶⑺綌?shù)組擴(kuò)大一倍，這樣每層中的各節(jié)點(diǎn)之間的距離拉長(zhǎng)了，最終看到的結(jié)果是整個(gè)樹水平放大了。
*
*/
private RedBlackTreeNode RBSearch(RedBlackTreeNode x, int k){
while (x != nil){
if(x.key > k){
return RBSearch(x.left,k);
}else if(x.key < k){
return RBSearch(x.right,k);
}
else return x;
}
return nil;
}
private void LeftRotate(RedBlackTreeNode x){ // 假設(shè)x.right != Nil
RedBlackTreeNode y = x.right;
//將y設(shè)為新的子樹根節(jié)點(diǎn)
x.right = y.left;
if(y.left != nil){
y.left.p = x;
}
if(x.p.right == x){
x.p.right = y;
y.p = x.p;
}else if(x.p.left == x){
x.p.left = y;
y.p = x.p;
}else{
y.p = nil;
root = y;
}
//x成為y的左孩子
y.left = x;
x.p = y;
//y的左孩子成為x的右孩子
}
private void RightRotate(RedBlackTreeNode y){
//使x成為新的根節(jié)點(diǎn)
RedBlackTreeNode x = y.left;
y.left = x.right;
if(x.right != nil){
y.left.p = y;
}
if(y.p.left == y){
y.p.left = x;
x.p = y.p;
}else if(y.p.right == y){
y.p.right = x;
x.p = y.p;
}else{
root = x;
x.p = nil;
}
// y成為x的右孩子
y.p = x;
x.right = y;
//x的右孩子變成y的左孩子
//y.left = x.right;
}
private void RBInsert(RedBlackTreeNode z){
RedBlackTreeNode y = nil;
RedBlackTreeNode x = root;
while (x != nil){
y = x;
if(z.key < x.key){
x = x.left;
}else{
x = x.right;
}
}
z.p = y;
if(y == nil){
root = z;
}else if(z.key < y.key){
y.left = z;
}else{
y.right = z;
}
z.right = nil;
z.left = nil;
z.color = colors.red;
RBInsertFixup(z);
++N;
}
private void RBInsertFixup(RedBlackTreeNode z){
while (z.p.color == colors.red){
//由于z的父節(jié)點(diǎn)為紅，z也為紅，故需要調(diào)整
//首先想把z的父節(jié)點(diǎn)set為紅--> z.p的分支不滿足性質(zhì)5 --> 將z.p.p set為黑，且將z.uncle set為紅
if(z.p == z.p.p.left){//若z.p是z.p.p的左孩子
RedBlackTreeNode y = z.p.p.right;//z的叔節(jié)點(diǎn)
if(y.color == colors.red){//case 1 : 如果z的叔節(jié)點(diǎn)是紅色（與z的父節(jié)點(diǎn)顏色一樣）
z.p.color = colors.black;
y.color = colors.black;
z.p.p.color = colors.red;
z = z.p.p;
++z.depth;
}else if(z == z.p.right){ // case 2 : 如果z的叔節(jié)點(diǎn)是黑色,且z是右孩子
z = z.p;
LeftRotate(z);//左旋，使得紅色節(jié)點(diǎn)z上移
}
z.p.color = colors.black;//case 3
if(z.p != nil) {
z.p.p.color = colors.red;
RightRotate(z.p.p);
}
}else{//若z.p是z.p.p的右孩子
RedBlackTreeNode y = z.p.p.left;
if(y.color == colors.red){//case 1 : 如果z的叔節(jié)點(diǎn)是紅色（與z的父節(jié)點(diǎn)顏色一樣）
z.p.color = colors.black;
y.color = colors.black;
z.p.p.color = colors.red;
z = z.p.p;
}else {
if (z == z.p.left) { // case 2 : 如果z的叔節(jié)點(diǎn)是黑色,且z是左孩子
z = z.p;
RightRotate(z);//左旋，使得紅色節(jié)點(diǎn)z上移
}
z.p.color = colors.black;//case 3
if(z.p != nil) {
z.p.p.color = colors.red;
LeftRotate(z.p.p);
}
}
}
}
root.color = colors.black;
root.p = nil;
}
private void RBDelete(RedBlackTreeNode z){
RedBlackTreeNode y = z;
colors yOriginalColor = y.color;
RedBlackTreeNode x = nil;
if(z.left == nil){ //只有右邊節(jié)點(diǎn)
x = z.right;
RBTranlant(z,z.right);
}else if(z.right == nil){//只有左邊節(jié)點(diǎn)
x = z.left;
RBTranlant(z,z.left);
}else{//左右都有節(jié)點(diǎn)
y = TreeMinimum(z.right);//z的后繼
yOriginalColor = y.color;
x = y.right;
if(y.p == z){//z.right 就是z的后繼
x.p = y ;//為啥？
}else{
//后繼是y
//先用y.right代替y
RBTranlant(y,y.right);
//再用y代替z
y.right = z.right;
y.right.p = y;
}
RBTranlant(z,y);
y.left = z.left;
y.left.p = y;
y.color = z.color;
}
if(yOriginalColor == colors.black){
//當(dāng)z有一個(gè)兒子時(shí)，y就是z，x就是z的兒子
//已知y原為黑色，即z原來(lái)為黑色。但是
//z.child(也就是x)替換z后，可能會(huì)改變z位置（也就是現(xiàn)在的x）的黑高，故需要調(diào)整x
// 若x是紅色，那么有可能和原來(lái)z.p構(gòu)成雙紅，以及會(huì)破壞x處黑高 --> 把x設(shè)置為黑色即可
// 若x是黑色，會(huì)減小黑高，需要調(diào)整
//當(dāng)z有兩個(gè)兒子時(shí)，y是z的后繼，x是y.right
//z被y替換，已知y是黑色，則會(huì)改變z位置（現(xiàn)在y）的黑高。
//調(diào)整：
//a.若x是紅色，那么有可能和原來(lái)y.p構(gòu)成雙紅，以及會(huì)破壞x處黑高 --> 把x設(shè)置為黑色即可
//b.若x是黑色，由于y的上移，本分支黑高被破壞，需要調(diào)整
// 2.若z原來(lái)是紅色，則y被重置為紅色。x替換y后，現(xiàn)在x位置處的性質(zhì)被破壞
RBDeleteFixup(x);
}
}
private void RBDeleteFixup(RedBlackTreeNode x){
while (x != root && x.color == colors.black){
// bfsTree();
RedBlackTreeNode w = nil;
if(x == x.p.left){ //x是一個(gè)左孩子
w = x.p.right;//x的兄弟節(jié)點(diǎn)
if(w.color == colors.red) { //case 1
colors tempXP = x.p.color;
x.p.color = w.color;
w.color = tempXP;
LeftRotate(x.p);
w = x.p.right;
}else{
if(w.right.color == colors.black){
if(w.left.color == colors.black){//case 2
w.color = colors.red;
x = x.p;
--x.depth;
}else { // case 3
colors temp = w.color;
w.color = w.left.color;
w.left.color = temp;
RightRotate(w);
w = x.p.right;
}
}else{// case 4
w.color = x.p.color;
x.p.color = colors.black;
--x.p.depth;
++w.depth;
w.right.color = colors.black;
LeftRotate(x.p);
x =root;
}
}
}else{
w = x.p.left;//x的兄弟節(jié)點(diǎn)
if(w.color == colors.red) { //case 1
colors tempXP = x.p.color;
x.p.color = w.color;
w.color = tempXP;
RightRotate(x.p);
w = x.p.left;
}else{
if(w.left.color == colors.black){
if(w.right.color == colors.black){//case 2
w.color = colors.red;
x = x.p;
}else { // case 3
colors temp = w.color;
w.color = w.right.color;
w.right.color = temp;
LeftRotate(w);
w = x.p.left;
}
}else{// case 4
w.color = x.p.color;
x.p.color = colors.black;
w.left.color = colors.black;
RightRotate(x.p);
x =root;
}
}
}
}
x.color = colors.black;
}
private void RBTranlant(RedBlackTreeNode u,RedBlackTreeNode v){//用v替換u
if(u == u.p.right){//u是u.p的右孩子
u.p.right = v;
v.p = u.p;
}else if( u == u.p.left ){//u是u.p的左孩子孩子
u.p.left = v;
v.p = u.p ;
}else {//u是根節(jié)點(diǎn)
v.p = nil;
root = v;
}
}
public RedBlackTree RBJoin(RedBlackTree T1, RedBlackTree T2, int x) throws CloneNotSupportedException {
RedBlackTreeNode x_root = new RedBlackTreeNode(x);
x_root.right = T1.root;
T1.root.p = x_root;
x_root.left = T2.root;
T2.root.p = x_root;
int x_N = Math.max(T1.N,T2.N);
RedBlackTree newTree = new RedBlackTree(x_root);
newTree.N = x_N;
T1.nil = newTree.nil;
T2.nil = newTree.nil;
x_root.p = newTree.nil;
return newTree;
}
private RedBlackTreeNode TreeMinimum(RedBlackTreeNode x){//得到最小值
while (x.left != nil){
x = x.left;
}
return x;
}
private RedBlackTreeNode TreeMaximum(RedBlackTreeNode x){//得到最大值
while (x.right != nil){
x = x.right;
}
return x;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/65274.html
摘要：很多文章或書籍在介紹紅黑樹的時(shí)候直接上來(lái)就是紅黑樹的個(gè)基本性質(zhì)插入刪除操作等。這也不奇怪，算法的作者就是紅黑樹的作者之一。所以，理解樹對(duì)掌握紅黑樹是至關(guān)重要的。 本文主要包括以下內(nèi)容： 什么是2-3樹 2-3樹的插入操作 紅黑樹與2-3樹的等價(jià)關(guān)系 《算法4》和《算法導(dǎo)論》上關(guān)于紅黑樹的差異 紅黑樹的5條基本性質(zhì)的分析 紅黑樹與2-3-4樹的等價(jià)關(guān)系 紅黑樹的插入、刪除操作 JDK ...
摘要：在二叉查找樹上執(zhí)行基本操作的時(shí)間與樹的高度成正比。不同的二叉查找樹可以表示同一組值。紅黑樹樹二叉查找樹，紅黑樹，樹紅黑樹 雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 關(guān)于二叉樹的基本知識(shí)，可以參見：Java 實(shí)現(xiàn)基本數(shù)據(jù)結(jié)構(gòu) 2(樹) 以下是算法導(dǎo)論第十二章的學(xué)習(xí)筆記 二叉查找樹 BS...
摘要：源碼剖析由于紅黑樹的操作我這里不說(shuō)了，所以這里基本上也就沒什么源碼可以講了，因?yàn)檫@里面重要的算法都是，這里的是指，他們是算法導(dǎo)論的作者，也就是說(shuō)里面算法都是參照算法導(dǎo)論的偽代碼。因?yàn)榧t黑樹是平衡的二叉搜索樹，所以其包含操作的時(shí)間復(fù)雜度都為。 本文章首發(fā)于個(gè)人博客，鑒于sf博客樣式具有賞心悅目的美感，遂發(fā)表于此，供大家學(xué)習(xí)、批評(píng)。本文還在不斷更新中，最新版可移至個(gè)人博客。? 繼上篇文章...
摘要：需要執(zhí)行的操作依次是首先，將紅黑樹當(dāng)作一顆二叉查找樹，將該節(jié)點(diǎn)從二叉查找樹中刪除然后，通過(guò)旋轉(zhuǎn)和重新著色等一系列來(lái)修正該樹，使之重新成為一棵紅黑樹。 雖是讀書筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 關(guān)于二叉樹的基本知識(shí)，可以參見：Java 實(shí)現(xiàn)基本數(shù)據(jù)結(jié)構(gòu) 2(樹) 以下是算法導(dǎo)論第13章的學(xué)...
閱讀 1966·2023-04-25 16:19
閱讀 3091·2021-11-24 09:39
閱讀 829·2021-11-16 11:44
閱讀 1688·2019-08-29 12:52
閱讀 1138·2019-08-26 13:33
閱讀 1073·2019-08-26 10:26
閱讀 2200·2019-08-23 16:42
閱讀 2567·2019-08-23 14:37
