关键词：
1. 排序二叉树
排序二叉树是一种特殊结构的二叉树，可以非常方便地对树中所有节点进行排序和检索。
排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 它的左、右子树也分别为排序二叉树。
图 1 显示了一棵排序二叉树：
图 1. 排序二叉树
对排序二叉树，若按中序遍历就可以得到由小到大的有序序列。如图 1 所示二叉树，中序遍历得：
{2，3，4，8，9，9，10，13，15，18}
1.1 创建排序二叉树
创建排序二叉树的步骤，也就是不断地向排序二叉树添加节点的过程，向排序二叉树添加节点的步骤如下：
- 以根节点当前节点开始搜索。
- 拿新节点的值和当前节点的值比较。
- 如果新节点的值更大，则以当前节点的右子节点作为新的当前节点；如果新节点的值更小，则以当前节点的左子节点作为新的当前节点。
- 重复 2、3 两个步骤，直到搜索到合适的叶子节点为止。
- 将新节点添加为第 4 步找到的叶子节点的子节点；如果新节点更大，则添加为右子节点；否则添加为左子节点。
当程序从排序二叉树中删除一个节点之后，为了让它依然保持为排序二叉树，程序必须对该排序二叉树进行维护。维护可分为如下几种情况：
（1）被删除的节点是叶子节点，则只需将它从其父节点中删除即可。
（2）被删除节点 p 只有左子树，将 p 的左子树 pL 添加成 p 的父节点的左子树即可；被删除节点 p 只有右子树，将 p 的右子树 pR 添加成 p 的父节点的右子树即可。
（3）若被删除节点 p 的左、右子树均非空，有两种做法：
- 将 pL 设为 p 的父节点 q 的左或右子节点（取决于 p 是其父节点 q 的左、右子节点），将 pR 设为 p 节点的中序前趋节点 s 的右子节点（s 是 pL 最右下的节点，也就是 pL 子树中最大的节点）。
- 以 p 节点的中序前趋或后继替代 p 所指节点，然后再从原排序二叉树中删去中序前趋或后继节点即可。（也就是用大于 p 的最小节点或小于 p 的最大节点代替 p 节点即可）。
2.平衡二叉树
平衡二叉树：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、Treap等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
3.红黑树
3.1红黑树的性质
红黑树在原有的排序二叉树增加了如下几个要求：
- 性质 1：每个节点要么是红色，要么是黑色。
- 性质 2：根节点永远是黑色的。
- 性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。
- 性质 4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
- 性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
Java 中实现的红黑树可能有如图 6 所示结构：
备注：本文中所有关于红黑树中的示意图采用白色代表红色。黑色节点还是采用了黑色表示。
根据性质 5：红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶子节点的路径中包含的黑色节点数被称为树的“黑色高度（black-height）”。
性质 4 则保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍。假如有一棵黑色高度为 3 的红黑树：从根节点到叶节点的最短路径长度是 2，该路径上全是黑色节点（黑节点 - 黑节点 - 黑节点）。最长路径也只可能为 4，在每个黑色节点之间插入一个红色节点（黑节点 - 红节点 - 黑节点 - 红节点 - 黑节点），性质 4 保证绝不可能插入更多的红色节点。由此可见，红黑树中最长路径就是一条红黑交替的路径。
由此我们可以得出结论：对于给定的黑色高度为 N 的红黑树，从根到叶子节点的最短路径长度为 N-1，最长路径长度为 2 * (N-1)。
提示：排序二叉树的深度直接影响了检索的性能，正如前面指出，当插入节点本身就是由小到大排列时，排序二叉树将变成一个链表，这种排序二叉树的检索性能最低：N 个节点的二叉树深度就是 N-1。
红黑树通过上面这种限制来保证它大致是平衡的——因为红黑树的高度不会无限增高，这样保证红黑树在最坏情况下都是高效的，不会出现普通排序二叉树的情况。
由于红黑树只是一个特殊的排序二叉树，因此对红黑树上的只读操作与普通排序二叉树上的只读操作完全相同，只是红黑树保持了大致平衡，因此检索性能比排序二叉树要好很多。
但在红黑树上进行插入操作和删除操作会导致树不再符合红黑树的特征，因此插入操作和删除操作都需要进行一定的维护，以保证插入节点、删除节点后的树依然是红黑树
答案是：ABCD
avl树和红黑树的模拟实现
...,我尽量和大家分享的接地气一点.AVL树这种树也叫做平衡二叉树.这个是前面二叉搜索树的变种.我们前面谈过,对于比较有序元素,那么搜索二叉树就有点深了,甚至转换成了单只树,那么这样查找的效率就有点低了.所以我们提出的AVL... 查看详情
9.6-全栈java笔记:二叉树和红黑二叉树
二叉树的定义二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉... 查看详情
排序二叉树平衡二叉树红黑树
1、排序二叉树 排序二叉树是一种特殊的二叉树，可以非常方便的进行检索，它具有如下特点：若它的左子树不为空，则左子树上所有节点值都小于根节点的值若它的右子树不为空，则右子树上所有节点值都大于根节点的值... 查看详情
treemap源码分析之一——排序二叉树平衡二叉树红黑树
一、排序二叉树(BST树)1.排序二叉树的定义排序二叉树，BinarySortTree排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树： (1)若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； (2)若它的右子... 查看详情
数据结构红黑树hashmap(jdk8)(代码片段)
...叉树的缺点3.二叉查找树(BinarySearchTree)(二叉搜索树,二叉排序树)二叉查找树的优点二叉查找树的复杂度4.自平衡二叉树(AVL树、平衡二叉查找树，继承 查看详情
最容易懂得红黑树
介绍红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束，但是这样在动态插入中保持树的完美平衡代价太高，所以，我们稍微放松逛一下限制，希望找到一个能在对... 查看详情
c++基础语法梳理：数据结构丨树（二叉树和红黑树）(代码片段)
本期是C++基础语法分享的第十四节，今天给大家来梳理一下树！ 二叉树BinaryTree.cpp：#include<stdio.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineSU 查看详情
c++红黑树(代码片段)
...与AVL树的比较十一、红黑树的应用一、红黑树的引入有了二叉搜索树，为什么还需要平衡二叉树？在学习二叉搜索树、平衡二叉树时，我们不止一次提到，二叉搜索树容易退化成一条链这时，查找的时间复杂... 查看详情
红黑树
红黑树的来历红黑树（Cormen,2001）是一个平衡二叉树的高效实现。是一种特殊的二叉查找树，自平衡二叉查找树，为了防止二叉查找树退化成链表的情况。相对于AVL树（完美平衡二叉树），是一种平衡二叉树，它追求极致的平衡... 查看详情
javase——数据结构二叉树红黑树
...构图二叉查找树二叉查找树的特点二叉查找树,又称二叉排序树或者二叉搜索树每一个节点上最多有两个子节点左子树上所有节点的值都小于根节点的值右子树上所有节点的值都大于根节点的值二叉查找树结构图 二叉查找树... 查看详情
平衡二叉树（avl）与红黑树
...是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。如果在AVL树中插入或删除节点后，使得高度之差大于1。此时，AVL树的平衡状态就被破坏... 查看详情
红黑树与avl（平衡二叉树）的区别
关于红黑树和AVL树，来自网络：1好处及用途 红黑树 并不追求“完全平衡 ”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以 O(log2 ... 查看详情
二叉树的建立以及相关操作，平衡二叉树
二叉树的一些属性：intdatdID;doubledata;TreeNodeleftTree;TreeNoderightTree;TreeNodeparent; //构建一个二叉树，将数据都放入了一个LIST里面 intselfID=0; publicTreeNodecreatTree 查看详情
红黑树与平衡二叉树
红黑树的性质性质1.节点是红色或黑色。性质2.根节点是黑色。性质3.每个叶子节点都是黑色的空节点（NIL节点）。性质4每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)性质5.从任... 查看详情
经典结构搜索二叉树
内容：1、搜索二叉树2、典型搜索二叉树原理(AVL树、红黑树、SB树)3、旋转--Rebalance4、Java中红黑树的使用 1、搜索二叉树搜索二叉树的定义：对于一棵二叉树中的任意子树，其左子树上的所有数值小于头结点的数值，... 查看详情
二叉树1.二叉树的基本概念
...比前面一个专题的还多。为此，我们不得不将其分为二叉树和其他树两个大模块来分析。二叉树模块自然是分析二叉树的构造、特征、遍历、线索化和各类变来变去的问题。其他树则是平衡树与AVL树、红黑树、堆与优先级队... 查看详情
红黑树
红黑树是一个平衡的二叉树，但不是一个完美的平衡二叉树。 红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。 在C++STL中，很多部分(包括set,multiset,map,multimap)应用了红... 查看详情
算法红黑树-二叉树-算法
红黑树-二叉树-算法 红黑树查找_百度搜索(5条消息)AVL树，红黑树，B树，B+树，Trie树都分别应用在哪些现实场景中？-知乎查找(二)：彻底理解红黑树和平衡查找树-@瞪着太阳的乌鸦-博客园平衡查找树之红黑树(动画演示)-大数... 查看详情