红黑树原理之添加节点

在网上看了很多写红黑树的博客，大部分写的都不是很到位，有些关于红黑树的图都是有问题的，很多都没有说清楚什么情况促发哪种 *** 作，看完之后还是不理解，在查看了很多资料之后，决定自己写关于红黑树的理解。分为添加节点篇和删除节点篇，本文为将阐述红黑树的基本原理以及在添加节点时，各种情况下对应的 *** 作。（在看本文前，需要先了解平衡二叉树的原理，因为红黑树的有些 *** 作和二叉平衡树类似）

红黑树之所以被称为红黑树，是因为红黑树的节点的颜色非红即黑，通过对节点颜色的限制和一系列的限制条件来确保红黑树没有任何一条路径是其他路径的两倍长。

红黑树需要满足以下条件：

（1）每个节点非黑即红。

（2）根节点是黑色。

（3）每个叶子节点，即空节点是黑的。

（4）红色节点的两个孩子节点都是黑的

（5）每个节点到子孙节点的所有路径上包含相同数量的黑色节点

如图1所示，就是一颗红黑树：

在插入节点时，总是插入红色节点，这样可以 尽量 避免破坏红黑树的结构，为什么说插入红节点可以 尽量 避免破坏红黑树的结构，假如现在要插入6，即插入到12节点的左孩子，如果6节点是黑色的，那么就会破坏规则（5），即图2中绿色路径上的黑色节点的数量比黄色路径上黑色节点的数量多，如果6节点是红色的，则不会破坏树结构，如图3所示。

红黑树节点的添加可分为以下3种情况

分析：因为插入的是红色节点，所以违背规则（2）根节点是黑色

解决方案：只需要把这个节点的颜色改成黑色即可。

分析：因为插入节点的颜色是红色，不会破坏任何规则。

解决方案：无。

分析：这时又可分为插入节点是父节点的左孩子还是右孩子，以及父节点是祖父节点的左孩子还是右孩子，由于对称性，我们只需要考虑其中一种即可。假设插入的节点是25，即如图4所示的位置。这时破坏了规则（4）红色节点的两个孩子节点都是黑的。

解决方案：将当前节点的父节点和叔叔节点改成黑色，祖父节点改为红色，把当前节点指向祖父节点。如图5所示。

情况4：当前节点的父节点是红色，叔叔节点是黑色，当前节点是其父节点的右孩子。

分析：这时破坏了规则（4）红色节点的两个孩子节点都是黑的。如图5所示。

解决方案：将当前节点的父节点作为新的当前节点，以新的当前节点为支点进行左旋。如图6所示。

[图片上传失败...(image-c45d5d-1594949705288)]

分析：这时破坏了规则（4）红色节点的两个孩子节点都是黑的。如图6所示。

解决方案：父节点改成黑色，祖父节点改成红色，将当前节点改为祖父节点，并以新的当前节点为支点进行右旋。如图7所示。

[图片上传失败...(image-492143-1594949705288)]

以上内容就是关于红黑树添加节点时的 *** 作，本片博客参考了 https://bbs.csdn.net/topics/350253651 。

//先选中节点才能增加节点

import java.awt.*

import java.awt.event.*

import javax.swing.*

import javax.swing.event.*

import javax.swing.tree.*

public class TreeTest implements ActionListener,TreeModelListener{

JLabel label=null

JTree tree=null

DefaultTreeModel treeModel=null

String nodeName=null//原有节点名称

public TreeTest(){

JFrame f=new JFrame("TreeTest")

Container contentPane=f.getContentPane()

DefaultMutableTreeNode root=new DefaultMutableTreeNode("资源管理器")

tree=new JTree(root)

tree.setEditable(true)

tree.addMouseListener(new MouseHandle())

treeModel=(DefaultTreeModel)tree.getModel()

treeModel.addTreeModelListener(this)

JScrollPane scrollPane=new JScrollPane()

scrollPane.setViewportView(tree)

JPanel panel=new JPanel()

JButton b=new JButton("新增节点")

b.addActionListener(this)

panel.add(b)

b=new JButton("删除节点")

b.addActionListener(this)

panel.add(b)

b=new JButton("清除所有节点")

b.addActionListener(this)

panel.add(b)

label=new JLabel("Action")

contentPane.add(panel,BorderLayout.NORTH)

contentPane.add(scrollPane,BorderLayout.CENTER)

contentPane.add(label,BorderLayout.SOUTH)

f.pack()

f.setVisible(true)

f.addWindowListener(new WindowAdapter(){

public void windowClosing(WindowEvent e){

System.exit(0)

}

})

}

//本方法运行新增、删除、清除所有节点的程序代码.

public void actionPerformed(ActionEvent ae){

if (ae.getActionCommand().equals("新增节点")){

DefaultMutableTreeNode parentNode=null

DefaultMutableTreeNode newNode=new DefaultMutableTreeNode("新节点")

newNode.setAllowsChildren(true)

TreePath parentPath=tree.getSelectionPath()

//取得新节点的父节点

parentNode=(DefaultMutableTreeNode)(parentPath.getLastPathComponent())

//由DefaultTreeModel的insertNodeInto（）方法增加新节点

treeModel.insertNodeInto(newNode,parentNode,parentNode.getChildCount())

//tree的scrollPathToVisible()方法在使Tree会自动展开文件夹以便显示所加入的新节点。若没加这行则加入的新节点

//会被 包在文件夹中，你必须自行展开文件夹才看得到。

tree.scrollPathToVisible(new TreePath(newNode.getPath()))

label.setText("新增节点成功")

}

if (ae.getActionCommand().equals("删除节点")){

TreePath treepath=tree.getSelectionPath()

if (treepath!=null){

//下面两行取得选取节点的父节点.

DefaultMutableTreeNode selectionNode=(DefaultMutableTreeNode)treepath.getLastPathComponent()

TreeNode parent=(TreeNode)selectionNode.getParent()

if (parent!=null) {

//由DefaultTreeModel的removeNodeFromParent()方法删除节点，包含它的子节点。

treeModel.removeNodeFromParent(selectionNode)

label.setText("删除节点成功")

}

}

}

if (ae.getActionCommand().equals("清除所有节点")){

//下面一行，由DefaultTreeModel的getRoot()方法取得根节点.

DefaultMutableTreeNode rootNode=(DefaultMutableTreeNode)treeModel.getRoot()

//下面一行删除所有子节点.

rootNode.removeAllChildren()

//删除完后务必运行DefaultTreeModel的reload() *** 作，整个Tree的节点才会真正被删除.

treeModel.reload()

label.setText("清除所有节点成功")

}

}

public void treeNodesChanged(TreeModelEvent e){

TreePath treePath=e.getTreePath()

DefaultMutableTreeNode node=(DefaultMutableTreeNode)treePath.getLastPathComponent()

try{

int[] index=e.getChildIndices()

node=(DefaultMutableTreeNode)node.getChildAt(index[0])

}catch(NullPointerException exc){}

label.setText(nodeName+"更改数据为:"+(String)node.getUserObject())

}

public void treeNodesInserted(TreeModelEvent e){

System.out.println("new node insered")

}

public void treeNodesRemoved(TreeModelEvent e){

System.out.println("node deleted")

}

public void treeStructureChanged(TreeModelEvent e){

System.out.println("Structrue changed")

}

public static void main(String[] args){

new TreeTest()

}

class MouseHandle extends MouseAdapter{

public void mousePressed(MouseEvent e){

try{

JTree tree=(JTree)e.getSource()

int rowLocation=tree.getRowForLocation(e.getX(),e.getY())

TreePath treepath=tree.getPathForRow(rowLocation)

TreeNode treenode=(TreeNode)treepath.getLastPathComponent()

nodeName=treenode.toString()

}catch(NullPointerException ne){}

}

}

}

二叉树节点的查找、插入、删除.用C语言做的，不懂的地方可以给我留言。希望对你有所帮助！

#include <stdio.h>

#include <stdlib.h>

typedef int elemtype

typedef struct Node

{

elemtype data

struct Node *Lchild

struct Node *Rchild

}TreeNode

typedef TreeNode *bt

int

Search_data(TreeNode *t,TreeNode **p,TreeNode **q, elemtype x) //查找函数

{

int flag=0

*p=NULL

*q=t

while(*q)

{

if (x>(*q)->data)

{

*p=*q

*q=(*q)->Rchild

}

else{

if (x<(*q)->data)

{

*p=*q

*q=(*q)->Lchild

}

else{

flag=1

break

}

}

}

return flag

}

int

InsertNode(TreeNode **t,elemtype x) //插入函数

{

int flag =0

TreeNode *q,*s

TreeNode *p=*t

if (!Search_data(*t,&p,&q,x))

{

s=(TreeNode *)malloc(sizeof(TreeNode))

s->data=x

s->Lchild=NULL

s->Rchild=NULL

flag=1

if(!p) t=s

else{

if(x>p->data)

p->Rchild=s

else

p->Lchild=s

}

}

return flag

}

int

DeleteNode(TreeNode **t,elemtype x) //删除函数

{

int flag=0

TreeNode *q,*s,**f

TreeNode *p=*t

if (Search_data(*t,&p,&q,x))

{

flag=1

if(p==q) f=&(*t)

else

{

f=&(p->Lchild)

if(x>p->data)

f=&(p->Rchild)

}

if(!q->Rchild)

*f=q->Lchild

else{

if(!q->Lchild)

*f=q->Rchild

else{

p=q->Rchild

s=p

while(p->Lchild){

s=p

p=q->Lchild

}

*f=p

p->Lchild=q->Lchild

if (s!=p)

{

s->Lchild=p->Rchild

p->Rchild=q->Rchild

}

}

}

free(q)

}

return flag

}

void

visit(bt t)

{

printf("%c",t->data)

}

TreeNode *

creat_Tree()

{

char ch

bt t

ch=getchar()

if(ch==' ') return (NULL)

else{

t=(TreeNode *)malloc(sizeof(TreeNode))

t->data=ch

t->Lchild=creat_Tree()

t->Rchild=creat_Tree()

printf("%x\n",&t)

return (t)

}

}

void

mid_oderTree(bt t)

{

if (t!=NULL)

{

mid_oderTree(t->Lchild)

visit(t)

mid_oderTree(t->Rchild)

}

}

int

count_leafTree(bt t)

{

int i

if(t==NULL) return 0

else

if(t->Lchild==NULL&&t->Rchild==NULL)

i=1

else i=count_leafTree(t->Lchild)+

count_leafTree(t->Rchild)

return i

}

main()

{

TreeNode *t,*p,*q

elemtype x

x='M'

printf("creat Tree:\n")

//二叉树在遍历最后一个节点之后，遇到结束符结束建立树。

t=creat_Tree()

printf("中根遍历树:\n")

mid_oderTree(t)

printf("\n中根序插入%c成功输出（是1否0）:%d\n",x,InsertNode(&t,x))

printf("插入%c后的查找成功输出（是1否0）：%d\n",x,Search_data(t,&p,&q, x))

printf("插入后的中根遍历树:\n")

mid_oderTree(t)

printf("\n删除%c成功输出（是1否0）：%d \n",x,DeleteNode(&t,x))

printf("删除后的中根遍历树:\n")

mid_oderTree(t)

printf("\n求树的叶子数:%d \n",count_leafTree(t))

}

---