<commit_before>---
layout: post
title:  全面剖析红黑树
date:   2017-02-18 10:08:00 +0800
categories: 文章
tag: 数据结构与算法
---

* content
{:toc}


#全面剖析红黑树

##一、红黑树简介
###1.1 定义
红黑树（Red Black Tree）是一种自平衡二叉查找树，与 AVL 树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

###1.2 性质
（1）红黑树的每个结点或是红色的，或是黑色的；<br>
（2）根结点是黑色的；<br>
（3）每个叶结点（NIL）均为黑色的；<br>
（4）如果一个结点是红色的，那么它的两个子结点都是黑色的；<br>
（5）对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。<br>

###1.3 数据结构
红黑树TNode有左子结点、右子结点、父结点、结点颜色和结点权值五个属性。
```java
class TNode {
	
	private TNode leftNode;
	private TNode rightNode;
	private TNode parentNode;
	private int colorNode;	//	RED=0,BLACK=1
	private int value;
}
```
红黑树的一个结点如下所示：<commit_msg>blog 1.03<commit_after>---
layout: post
title:  全面剖析红黑树
date:   2017-02-18 10:08:00 +0800
categories: 文章
tag: 数据结构与算法
---

* content
{:toc}


全面剖析红黑树
====================================

一、红黑树简介
------------------------------------
###1.1 定义
红黑树（Red Black Tree）是一种自平衡二叉查找树，与 AVL 树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

###1.2 性质
（1）红黑树的每个结点或是红色的，或是黑色的；<br>
（2）根结点是黑色的；<br>
（3）每个叶结点（NIL）均为黑色的；<br>
（4）如果一个结点是红色的，那么它的两个子结点都是黑色的；<br>
（5）对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。<br>

###1.3 数据结构
红黑树TNode有左子结点、右子结点、父结点、结点颜色和结点权值五个属性。
```java
class TNode {
	
	private TNode leftNode;
	private TNode rightNode;
	private TNode parentNode;
	private int colorNode;	//	RED=0,BLACK=1
	private int value;
}
```
红黑树的一个结点如下所示：
{'fraction_non_alphanumeric': 0.19490909090909092, 'fraction_numerical': 0.04727272727272727, 'mean_word_length': 5.341013824884793, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '350243', 'n_tokens_mistral': 926, 'n_tokens_neox': 1044, 'n_words': 108}