天天看點
傳回

C++面試題系列：紅黑樹

更多文章見C++面試題系列

産生背景:

紅黑樹解決了平衡二叉樹為了重新維持平衡旋轉成本太高的問題.

平衡二叉樹又稱AVLTree,平衡二叉樹最大的作用是查找,因為AVL樹的查找,插入和删除在平均和最壞情況小都是O(logn)?

紅黑樹與AVL樹比較:

1.插入删除操作,紅黑樹更容易控制;

2.旋轉操作,調整平衡時紅黑樹的旋轉次數更少.

紅黑樹性質和定義:

紅黑樹(Red-Black Tree)又稱RB Tree,它是一個二叉查找樹(二叉搜尋樹)?,每個節點包含一個存儲為來表示節點的顔色,節點的顔色可以是紅色或者黑色.一棵紅黑樹具有如下性質:

1.每個節點的顔色不是紅色就是黑色

2.根節點的顔色是黑色

3.葉子節點(NULL)的顔色是黑色

4.每個紅色節點,它的子節點必須是黑色

5.一個節點到該節點所有子孫節點的路徑包含相同的黑色節點數,該性質保證最大路徑長度不會超過最小路徑長度的2倍,進而保證紅黑樹是一顆近似平衡二叉樹.

C++面試題系列：紅黑樹

定義紅黑樹節點:

enum RBTColor{RED, BLACK};

template <class T>
class RBTNode {
public:
	RBTColor color;
	T key;
	RBTNode *left;
	RBTNode *right;
	RBTNode *parent;

	RBTNode(T val, RBTColor col, RBTNode *p, RBTNode *l,RBTNode *r):
		key(val),color(col),parent(p),left(l),right(r){}
};

紅黑樹操作:

1.左旋和右旋

對紅黑樹進行插入或删除操作後,該紅黑樹可能不再滿足紅黑樹的5個基本性質,為了保持紅黑樹的特性,需要對該樹進行旋轉操作.

常見的旋轉操作包括:左旋和右旋.

1.左旋

C++面試題系列：紅黑樹

對x節點進行左旋,就是讓X節點旋轉後成為一個左孩子,成為它右孩子的左孩子.

下面再看1個例子:

例子1:

C++面試題系列：紅黑樹

總結,左旋操作可以分三步走:

（1）移動y的左孩子，y的左孩子移動為X的右孩子。X的右孩子指向y的左孩子,y的左孩子的父節點指向X.

（2）移動y節點，y的父節點指向X的父節點，如果X不是根節點，X父節點的左孩子或右孩子指向Y.。如果X是根節點則，y設定為根節點

（3）移動X節點，y節點的左孩子指向X，X的父節點指向Y.

實作代碼:

/*
* 對紅黑樹的節點(x)進行左旋轉
*
* 左旋示意圖(對節點x進行左旋)：
*      px                              px
*     /                               /
*    x                               y
*   /  \      --(左旋)-->           / \                #
*  lx   y                          x  ry
*     /   \                       /  \
*    ly   ry                     lx  ly
*
*
*/
template<class T>
void CMyRBTree<T>::leftRotate(RBTNode<T>*& root, RBTNode<T>* x)
{
	//定義一個指針y,指向x的右孩子;
	RBTNode<T> *y = x->right;

	//1.将"y的左孩子"設為"X的右孩子"
	x->right = y->left;
	if (y->left != nullptr)
	{
		y->left->parent = x;
	}

	//2.将"X的父節點"設為"Y的父節點"
	y->parent = x->parent;
	if (x->parent == nullptr)
	{
		root = y;
	}else
	{
		if (x->parent->left == x)
		{
			x->parent->left = y;
		}
		else {
			x->parent->right = y;
		}

	}

    //3.将x作為y的左孩子
	y->left = x;
	x->parent = y;
	
}

2.右旋

C++面試題系列：紅黑樹

假設右旋節點為y,y的左孩子為x。右旋就是讓y成為它的左孩子的有孩子

1.移動y節點的左孩子的右孩子，這裡是beta,beta變為y節點的左孩子

2.移動y節點的左孩子，這裡是X,X的父親節點指向y的父親節點

     如果y的父親節點為空，則root==x

     如果y->parent->left==y,則y->parent->left=x;

     如果y->parent->right==y,則y->parent->right=x

3.移動y節點，y->parent=x;x->right=y;

/* 
 * 對紅黑樹的節點(y)進行右旋轉
 *
 * 右旋示意圖(對節點y進行左旋)：
 *            py                               py
 *           /                                /
 *          y                                x                  
 *         /  \      --(右旋)-->            /  \                     #
 *        x   ry                           lx   y  
 *       / \                                   / \                   #
 *      lx  rx                                rx  ry
 * 
 */
template <class T>
void RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y)
{
    // 設定x是目前節點的左孩子。
    RBTNode<T> *x = y->left;

    // 将 “x的右孩子” 設為 “y的左孩子”；
    // 如果"x的右孩子"不為空的話，将 “y” 設為 “x的右孩子的父親”
    y->left = x->right;
    if (x->right != NULL)
        x->right->parent = y;

    // 将 “y的父親” 設為 “x的父親”
    x->parent = y->parent;

    if (y->parent == NULL) 
    {
        root = x;            // 如果 “y的父親” 是空節點，則将x設為根節點
    }
    else
    {
        if (y == y->parent->right)
            y->parent->right = x;    // 如果 y是它父節點的右孩子，則将x設為“y的父節點的右孩子”
        else
            y->parent->left = x;    // (y是它父節點的左孩子) 将x設為“x的父節點的左孩子”
    }

    // 将 “y” 設為 “x的右孩子”
    x->right = y;

    // 将 “y的父節點” 設為 “x”
    y->parent = x;
}

牛客網：C++校招面試題合集

269：請問紅黑樹了解嗎

270：請你說一說紅黑樹的性質還有左右旋轉

271：請你說一說紅黑樹的原理以及erase以後疊代器的具體分布情況？

https://bbs.csdn.net/topics/350253651/

參考文獻：

紅黑樹原理

紅黑樹C++實作

附件:源代碼

.h

#pragma once

enum RBTColor{RED, BLACK};

template <class T>
class RBTNode {
public:
	RBTColor color;
	T key;
	RBTNode *left;
	RBTNode *right;
	RBTNode *parent;

	RBTNode(T val, RBTColor col, RBTNode *p, RBTNode *l,RBTNode *r):
		key(val),color(col),parent(p),left(l),right(r){}
};

template <class T>
class CMyRBTree
{
private:
	//跟節點
	RBTNode<T> *mRoot;
public:
	CMyRBTree();
	~CMyRBTree();

	// 前序周遊"紅黑樹"
	void preOrder();
	// 中序周遊"紅黑樹"
	void inOrder();
	// 後序周遊"紅黑樹"
	void postOrder();

	// (遞歸實作)查找"紅黑樹"中鍵值為key的節點
	RBTNode<T>* search(T key);
	// (非遞歸實作)查找"紅黑樹"中鍵值為key的節點
	RBTNode<T>* iterativeSearch(T key);

	// 查找最小結點：傳回最小結點的鍵值。
	T minimum();
	// 查找最大結點：傳回最大結點的鍵值。
	T maximum();

	// 找結點(x)的後繼結點。即，查找"紅黑樹中資料值大于該結點"的"最小結點"。
	RBTNode<T>* successor(RBTNode<T> *x);
	// 找結點(x)的前驅結點。即，查找"紅黑樹中資料值小于該結點"的"最大結點"。
	RBTNode<T>* predecessor(RBTNode<T> *x);

	// 将結點(key為節點鍵值)插入到紅黑樹中
	void insert(T key);

	// 删除結點(key為節點鍵值)
	void remove(T key);

	// 銷毀紅黑樹
	void destroy();

	// 列印紅黑樹
	void print();
private:
	// 前序周遊"紅黑樹"
	void preOrder(RBTNode<T>* tree) const;
	// 中序周遊"紅黑樹"
	void inOrder(RBTNode<T>* tree) const;
	// 後序周遊"紅黑樹"
	void postOrder(RBTNode<T>* tree) const;

	// (遞歸實作)查找"紅黑樹x"中鍵值為key的節點
	RBTNode<T>* search(RBTNode<T>* x, T key) const;
	// (非遞歸實作)查找"紅黑樹x"中鍵值為key的節點
	RBTNode<T>* iterativeSearch(RBTNode<T>* x, T key) const;

	// 查找最小結點：傳回tree為根結點的紅黑樹的最小結點。
	RBTNode<T>* minimum(RBTNode<T>* tree);
	// 查找最大結點：傳回tree為根結點的紅黑樹的最大結點。
	RBTNode<T>* maximum(RBTNode<T>* tree);

	// 左旋
	void leftRotate(RBTNode<T>* &root, RBTNode<T>* x);
	// 右旋
	void rightRotate(RBTNode<T>* &root, RBTNode<T>* y);
	// 插入函數
	void insert(RBTNode<T>* &root, RBTNode<T>* node);
	// 插入修正函數
	void insertFixUp(RBTNode<T>* &root, RBTNode<T>* node);
	// 删除函數
	void remove(RBTNode<T>* &root, RBTNode<T> *node);
	// 删除修正函數
	void removeFixUp(RBTNode<T>* &root, RBTNode<T> *node, RBTNode<T> *parent);

	// 銷毀紅黑樹
	void destroy(RBTNode<T>* &tree);

	// 列印紅黑樹
	void print(RBTNode<T>* tree, T key, int direction);
#define rb_parent(r) ((r)->parent)
#define rb_color(r) ((r)->color)
#define rb_is_red(r) ((r)->color==RED)
#define rb_is_black(r) ((r)->color==BLACK)
#define rb_set_black(r) do { (r)->color = BLACK;}while(0)
#define rb_set_red(r)  do { (r)->color = RED; } while (0)
#define rb_set_parent(r,p)  do { (r)->parent = (p); } while (0)
#define rb_set_color(r,c)  do { (r)->color = (c); } while (0)

};

.cpp

#include "stdafx.h"
#include "MyRBTree.h"


template<class T>
CMyRBTree<T>::CMyRBTree()
{
}

template<class T>
CMyRBTree<T>::~CMyRBTree()
{
}

/*
* 對紅黑樹的節點(x)進行左旋轉
*
* 左旋示意圖(對節點x進行左旋)：
*      px                              px
*     /                               /
*    x                               y
*   /  \      --(左旋)-->           / \                #
*  lx   y                          x  ry
*     /   \                       /  \
*    ly   ry                     lx  ly
*
*
*/
template<class T>
void CMyRBTree<T>::leftRotate(RBTNode<T>*& root, RBTNode<T>* x)
{
	//定義一個指針y,指向x的右孩子;
	RBTNode<T> *y = x->right;

	//将"y的左孩子"設為"X的右孩子"
	x->right = y->left;
	if (y->left != nullptr)
	{
		y->left->parent = x;
	}

	//将"X的父節點"設為"Y的父節點"
	y->parent = x->parent;
	if (x->parent == nullptr)
	{
		root = y;
	}else
	{
		if (x->parent->left == x)
		{
			x->parent->left = y;
		}
		else {
			x->parent->right = y;
		}

	}

	y->left = x;
	x->parent = y;
	
}

/*
* 對紅黑樹的節點(y)進行右旋轉
*
* 右旋示意圖(對節點y進行左旋)：
*            py                               py
*           /                                /
*          y                                x
*         /  \      --(右旋)-->            /  \                     #
*        x   ry                           lx   y
*       / \                                   / \                   #
*      lx  rx                                rx  ry
*
*/
template<class T>
void CMyRBTree<T>::rightRotate(RBTNode<T>*& root, RBTNode<T>* y)
{
	//定義一個指針,指向Y的左孩子
	RBTNode *x = y->left;

	//1.X的右孩子設定為y的左孩子
	y->left = x->right;
	if (x->right != nullptr)
	{
		x->right->parent = y;
	}

	//2.y的父親節點設定為X的父親節點
	x->parent = y->parent;
	if (y->parent == nullptr)
	{
		root = x;
	}
	else {
		if (y->parent->left == y)
		{
			y->parent->left = x;
		}
		else {
			y->parent->right = x;
		}
	}

	x->right = y;
	y->parent = x;
}

參考文獻

https://www.cnblogs.com/skywang12345/archive/2004/01/13/3245399.html 

C++開發面試題
上一篇: python面試題之Python 的特點和優點是什麼
下一篇: openstack pike安裝swift 對象存儲--centos 7.4 （十）

繼續閱讀