什么是二叉查找树：

根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值，这一规则适用于二叉查找树中的每一个节点。

本文章重点来讨论一下关于二叉查找树删除节点的问题。

有一下二叉查找树，如图：



在删除节点的时候我们只需考虑一下三种情况：

（1）要删除的节点是叶子结点，如图：



（2）要删除的节点有左节点但是没有右节点，或者有右节点但是没有左节点，如图：



（3）要删除的节点既有左节点又有右节点，在这种情况下，我们只需要将找到待删节点的右子树中值最小的节点，将其删除并且获取其值，并用其值替换待删节点的值即可。如图：



如上图所示，如果要删除节点7，则需寻找其右子树中节点值最小的9，并且该值一定位于该右子树的最左子节点；但是还有一种情况，如图一右子树没有左节点，但是只有右节点，这种情况就回到了前面的第二种情况。

具体代码如下：注意Node类是一个内部类，在使用时注意方法。
package com.zc.algorithm;

public class BinarySortTree {

    public class Node{
        int value;
        Node left;
        Node right;

        public Node(int  value)
        {
            this.value = value;
        }
        public void add(Node node)
        {
            if(node == null)
            {
                return;
            }
            //判断传入的节点的值比当前子树的根节点的值大还是小
            if(node.value < this.value)
            {
                //如果左节点为空
                if(this.left == null)
                {
                    this.left = node;
                }
                else
                {
                    this.left.add(node);
                }
            }
            else
            {
                if(this.right == null)
                {
                    this.right =node;
                }
                else
                {
                    this.right.add(node);
                }

            }
        }

        /**
         * 前序遍历二叉排序树
         * @param node
         */
        public void middleOder(Node node)
        {
            if(node == null)
            {
                return;
            }
            middleOder(node.left);
            System.out.println(node.value);
            middleOder(node.right);
        }

        /**
         * 查找某一节点
         * @param value
         * @return
         */
        public Node search(int value)
        {
            if(this.value == value)
            {
                return this;
            }
            else if(value < this.value)
            {
                if(this.left == null)
                {
                    return null;
                }
                 return this.left.search(value);
            }
            else
            {
                if(this.right == null)
                {
                    return null;
                }
                return  this.right.search(value);
            }

        }
        public Node searchParent(int value) {
            if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value))
            {
                return this;
            }
            else
            {
                if(this.value > value&& this.left != null)
                {
                    return this.left.searchParent(value);
                }
                else if(this.value < value && this.right !=null)
                {
                    return this.right.searchParent(value);
                }
            }
            return null;
        }
      }


    Node root;
    /**
     * 向二叉排序树中添加节点
     * @param node
     */
    public void add(Node node)
    {
        if(root == null)
        {
            root = node;
        }
      else
        {
            root.add(node);
        }
    }
    public void frontShow()
    {
        if(root != null)
        {
            this.root.middleOder(root);
        }
    }
    public Node SearchNode(int value)
    {
        if(root == null)
            return null;
        else
        {
            return root.search(value);
        }
    }

    public void delete(int value) {
        if (root == null)
            return;
        else
        {
            Node target = SearchNode(value);
            //如果没有这个节点
            if(target == null)
            {
                return;
            }
            //找到他的父节点
            Node parent = searchParent(value);
            //要删除的节点是叶子结点
            if(target.left == null && target.right == null)
            {
                //要删除的节点是节点的左子节点
                if(parent.left.value == value)
                {
                    parent.left =null;
                }
                else
                {
                    parent.right = null;
                }
            }
            //要删除的节点有两个子节点的情况
            else if(target.left != null && target.right != null)
            {
                   //删除右子树中值最小的节点，并获取到该节点的值
                int min = minDelete(target.right);
                //替换目标节点中的值
                target.value = min;
            }
            else
            {
                //需要删除的目标节点的左节点不为空
                if(target.left != null)
                {
                    //要删除的子节点是其父节点的左子节点，并且有左节点而没有有节点
                    if(parent.left.value == value)
                    {
                        parent.left = target.left;
                    }
                    //要删除的子节点是其父节点的右子节点，并且有左节点而没有有节点
                    else
                    {
                        parent.right = target.left;
                    }
                }
                //需要删除的目标节点的右节点不为空
                else
                {
                    //要删除的节点是父节点的左节点，并且有右节点儿没有左节点
                    if(parent.left.value == value)
                    {
                        parent.left = target.right;
                    }
                    //要删除的节点是其父节点的右节点，并且有右孩子没有左孩子
                    else
                    {
                        parent.right = target.right;
                    }
                }


            }

        }
    }

    /**
     * 删除一颗树中最小的节点
     * @param node
     * @return
     */
    public int minDelete(Node node)
    {
        Node target = node;
        while(target.left != null)
        {
            target = target.left;
        }
       delete(target.value);
        return target.value;

    }
    /**
     * 查找父节点
     * @param value
     * @return
     */
    public Node searchParent(int value)
    {
        if(root == null)
        {
            return null;
        }
        else
        {
            return root.searchParent(value);
        }
    }
    public static void main(String[] args)
    {
        int[] arr = new int[]{7,3,10,12,5,1,9};
        BinarySortTree binTree = new BinarySortTree();
        for(int i : arr)
        {
            binTree.add(binTree.new Node(i));
        }
        binTree.delete(7);
        //查看树中的值
        binTree.frontShow();
        //查找
      //  Node node = binTree.new Node(3);
        //Node res = binTree.SearchNode(node.value);
        //System.out.println(res.value);
       // Node temp = binTree.SearchNode(20);
        //System.out.println(temp.value);
    }
}

 

数据结构进阶(四)二叉排序树(二叉查找树)

    注:构造一棵二叉排序树的目的，其实并不是为了排序(中序遍历)，而是为了提高查找、插入、删除关键字的速度。

定义

    二叉排序树又叫二叉查找树，英文名称是：Binary Sort Tree.BST的定义就不详细说了，我用一句话概括：左 < 中 < 右。 根据这个原理，我们可以推断：BST的中序遍历必定是严格递增的。

    二叉查找树是满足以下条件的二叉树：

    1.左子树上的所有节点值均小于根节点值；

    2.右子树上的所有节点值均不小于根节点值；

    3.左右子树也满足上述两个条件。

    二叉查找树是基于二叉树的，其结点数据结构定义为如下：

 

public class TreeNode {
  public Integer data;
    
  /*该节点的父节点*/ 
  public TreeNode parent;
    
  /*该节点的左子节点*/
  public TreeNode left;
    
  /*该节点的右子节点*/
  public TreeNode right;
    
  public TreeNode(Integer data) {
    this.data = data;
  }
  
  @Override
  public String toString() {
    return "TreeNode [data=" + data + "]";
  }
}

 

    现在明白了什么是二叉查找树，那么二叉查找树的基本操作又是如何来实现的呢？

查找

    在二叉查找树中查找x的过程如下：

    1、若二叉树是空树，则查找失败。

    2、若x等于根结点的数据，则查找成功，否则。

    3、若x小于根结点的数据，则递归查找其左子树，否则。

    4、递归查找其右子树。

   根据上述的步骤，写出其查找操作的代码：

 

  /**
   * @param data
   * @return TreeNode
   */
  public TreeNode findTreeNode(Integer data){
    if(null == root){
      return null;
    }
    TreeNode current = root;
    while(current != null){
      if(current.data > data){
        current = current.left;
      }else if(current.data < data){
        current = current.right;
      }else {
        return current;
      }
        
    }
    return null;
  }

 

插入

    二叉查找树的插入过程如下：

    1.若当前的二叉查找树为空，则插入的元素为根节点；

    2.若插入的元素值小于根节点值，则将元素插入到左子树中；

    3.若插入的元素值不小于根节点值，则将元素插入到右子树中。

 

  /**
   * 往树中加节点  
   * @param data
   * @return Boolean 插入成功返回true
   */
  public Boolean addTreeNode(Integer data) {
  
    if (null == root) {
      root = new TreeNode(data);
      System.out.println("数据成功插入到平衡二叉树中");
      return true;
    }
  
    TreeNode treeNode = new TreeNode(data);// 即将被插入的数据
    TreeNode currentNode = root;
    TreeNode parentNode;
  
    while (true) {
      parentNode = currentNode;// 保存父节点
      // 插入的数据比父节点小
      if (currentNode.data > data) {
        currentNode = currentNode.left;
        // 当前父节点的左子节点为空
        if (null == currentNode) {
          parentNode.left = treeNode;
          treeNode.parent = parentNode;
          System.out.println("数据成功插入到二叉查找树中");
          size++;
          return true;
        }
        // 插入的数据比父节点大
      } else if (currentNode.data < data) {
        currentNode = currentNode.right;
        // 当前父节点的右子节点为空
        if (null == currentNode) {
          parentNode.right = treeNode;
          treeNode.parent = parentNode;
          System.out.println("数据成功插入到二叉查找树中");
          size++;
          return true;
        }
      } else {
        System.out.println("输入数据与节点的数据相同");
        return false;
      }
    }     
}

 

删除

   二叉查找树的删除，分三种情况进行处理：

   1.p为叶子节点，直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点），如图a。

   2.p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可；（注意分是根节点和不是根节点）；如图b。

   3.p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。如图c。







 

美文美图



 

Algorithm：树相关算法(BBT/BST/B树/R树)简介(二叉查找树、二叉查找树的插入节点、二叉查找树的删除、二叉树的遍历、平衡二叉树)C++语言实现

 

目录

树的基础知识

1、二叉树的遍—前序、中序、后序

一、二叉树

1、CBT

2、BST—二叉查找树BST的增删改查

1、BST的查找节点

2、BST的插入节点

3、BST的删除节点

3、BBT—平衡二叉树BBT→AVL/RBT

0、RBT红黑树和AVL

1、BBT的旋转

2、BBT的插入

3、BBT的查找

4、BBT的删除

4、堆

5、哈夫曼树HT/最优二叉树

二、多路查找树：多叉树——二叉到多叉的思考

1、多叉树

1、多叉树的查找与插入

2、B树及其变种——分裂节点、合并节点

3、R树—R树在实践中的应用

树相关算法的代码实现

1、二叉树的遍历——前中后、通过前中求后

2、二叉查找树、BST的插入节点、BST的删除

3、BBT单旋转、双旋转、BBT的插入、BBT的删除

 

参考文章：Algorithm：【Algorithm算法进阶之路】之数据结构基础知识

树的基础知识

       树Tree是一种抽象数据类型ADT，或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

(1)、每个节点有零个或多个子节点；
	
(2)、没有父节点的节点称为根节点；
	
(3)、每一个非根节点有且只有一个父节点；
	
(4)、除了根节点外，每个子节点可以分为多个不相交的子树；
 

1、二叉树的遍—前序、中序、后序

二叉树的遍历，都要从先从左区域开始遍历。

1、前序遍历、中序遍历、后序遍历

注：根结点Degree、左子树L、右子树R

先(根)序遍历(根左右DLR)：

中(根)序遍历(左根右LDR)：BST的中序一定是递增有序的序列！

后(根)序遍历(左右根LRD)：

结论：

(1)、二叉树结点的DLR、LDR、LRD中，所有叶子结点的先后顺序都是一致的，因为所有的叶节点都是从左到右的！

前序遍历：先(根)序遍历，根左右DLR

			根节点→前序遍历左子树(DLR)→前序遍历右子树(DLR)
			

		
中序遍历：中(根)序遍历，左根右LDR。BST的中序一定是递增有序的序列！

			中序遍历左子树(LDR)→根节点→中序遍历右子树(LDR)

			(1)、比如35是因为3就是节点5的左子数；67是因为7是6的右子树，所以先遍历6的左子树即空→根节点6→右子树7
			

		
后序遍历：后(根)序遍历，左右根LRD

			后序遍历左子树(LRD)→后序遍历右子树(LRD)→根节点
			

		
2、相关结论

(1)、二叉树结点的DLR、LDR、LRD中，所有叶子结点的先后顺序都是一致的，因为所有的叶节点都是从左区域到右区域的！

3、问题类型

(1)、通过前序中序求后序

Algorithm：【Algorithm算法进阶之路】之数据结构(数组、字符串、链表、栈、队列、树、图、哈希、堆)相关习题

 

一、二叉树

1、CBT—FBT一定是CBT

参考文章：Algorithm：【Algorithm算法进阶之路】之数据结构基础知识

 

 

2、BST—二叉查找树BST的增删改查

1、BST的查找节点



查找某节点p的过程如下：

n 将当前节点cur赋值为根节点root；
	
n 若p的值小于当前节点cur的值，查找cur的左子树；
	
n 若p的值不小于当前节点cur的值，查找cur的右子树；
	
n 递归上述过程，直到cur的值等于p的值或者cur为空；
	
o 当然，若节点是结构体，注意定义“小于”“不小于”“等于”的具体函数。
 

2、BST的插入节点



原理要符合二叉树的建立。

n若当前的二叉查找树为空，则插入的元素为根节点，
	
n若插入的元素值小于根节点值，则将元素插入到左子树中，
	
n若插入的元素值不小于根节点值，则将元素插入到右子树中，
	
n递归上述过程，直到找到插入点为叶子节点。
 

3、BST的删除节点

记待删除的节点为p，分三种情况进行处理

待删除点为叶子节点：p为叶子节点，直接删除该节点，再修改p的父节点的指针
	
待删除点只有一个孩子：若p为单支节点（即只有左子树或右子树），则将p的子树与p的父亲节点相连，删除p即可。
	
待删除点只有一个孩子：若p的左子树和右子树均不空，则找到p的直接后继d(p的右孩子的最左子孙)，因为d一定没有左子树，所以使用删除单支节点的方法：删除d，并让d的父亲节点dp成为d的右子树的父亲节点；同时，用d的值代替p的值；
(1)、对偶的，可以找到p的直接前驱x(p的左孩子的最右子孙)，x一定没有右子树，所以可以删除x，并让x的父亲节点成为x的左子树的父亲节点。

     

 

3、BBT—平衡二叉树BBT→AVL/RBT



        平衡二叉树（Balanced Binary Tree）是二叉查找树的一个变体，也是第一个引入平衡概念的二叉树。1962年，G.M. Adelson-Velsky 和E.M. Landis发明了这棵树，所以它又叫AVL树。

        平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找BST树退化成链表的问题，把插入、查找、删除的时间复杂度最好情况和最坏情况都维持在O(logN)。

1、BBT的动机

        对一棵查找树（search tree）进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree（平衡树）。

2、BBT的特点：

BBT是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
	
BBT常用算法有红黑树、AVL、Treap、伸展树、SBT等。
	
最小BBT的节点的公式： F(n)=F(n-1)+F(n-2)+1，这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
 

0、AVL和RBT红黑树

0、AVL和红黑树对比

两者都属于自平衡二叉树。
	
两者查找,插入，删除的时间复杂度相同。
1、AVL树—可理解为BBT

          AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。

AVL树是平衡二叉搜索树的鼻祖：AVL树是最先发明的自平衡二叉查 找树。
AVL树有两个性质
			

			
它或者是一颗空二叉树，或者是具有下列性质的二叉树：

			
(1)、其根的左右子树，高度之差的绝对值不能超过1；

			
(2)、其根的左右子树，都是二叉平衡树。
			
		
AVL应用
			
1、Windows NT内核中广泛存在。
		
2、红黑树





        红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。

红黑树 并不追求“完全平衡 ”：它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
	
红黑树能够以 O(log2 n)  的时间复杂度进行搜索、插入、删除操作。
	
任何不平衡都会在三次旋转之内解决。
红黑树有两个特征
			

			
1、节点都有颜色

			
2、在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。
			
		
红黑规则
			
1、每一个节点不是红色的就是黑色的。

			2、根总是黑色的

			3、如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）。

			4、从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。

			   （空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置）
		
红黑树的应用
			

			
1、广泛用于C++的STL中,map和set都是用红黑树实现的。

			(1)、JDK的TreeMap是一个红黑树的实现，能保证插入的值保证排序。

			
2、IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查。
			
		
 

1、BBT的旋转

高度不平衡节点的两颗子树的高度差2，只考虑该不平衡节点本身，分四种情况分别讨论。

(1)、四种分类：左左、左右、右左、右右；

(2)、四种旋转：对称与旋转，左左和右右对称；左右和右左对称

左左和右右两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，称之为单旋转。

左右和右左两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，称之为双旋转。


			
a、高度不平衡之左左

			
6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。

			
 

			


			
 

			
 
			
			

			
b、高度不平衡之左右

			
6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。

			


			
 

			
 
			
			

			
c、高度不平衡之右左

			
2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。

			


			
 

			
 
			
			

			
d、高度不平衡4之右右

			
2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。

			


			
 
			
		

			
(1)、BBT的左左—单旋转

			
如图，假设K2不平衡：为使树恢复平衡，把K1变成根节点。K2大于K1，所以，把K2置于K1的右子树上。K1右子树Y大于K1，小于K2，所以，把Y置于k2的左子树上。

			
 

			
左旋：就是让左边的孩子K1去提到上边，升级作为爸爸，自己K2变成儿子。

			

			
			

			
(2)、BBT的左右双旋转

			
对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。

			
以左右为例：节点K3不满足平衡特性，它的左子树K1比右子树D深2层，且K1子树更深的是右子树K2。

			


			
 
			
		
2、BBT的插入

       BBT插入的方法和BST基本一致。区别是，插入完成后需要从插入的节点开始，维护一个到根节点的路径，每经过一个节点都要维持树的平衡。维持树的平衡要根据高度差的特点选择不同的旋转算法。

 

3、BBT的查找

       BBT查找的方法和BST完全一样。不过根据高度基本平衡存储的特性，BBT能保持O(logN)的稳定时间复杂度，而BST则相当不稳定。

 

4、BBT的删除

       BBT删除的方法和BST基本一致。区别是，删除完成后，需要从删除节点的父亲开始，向上维护树的平衡一直到根节点。

 

 

4、堆

 

 

5、哈夫曼树HT/最优二叉树

 

 

二、多路查找树：多叉树——二叉到多叉的思考

1、多叉树

一个节点存一个值，则有2个孩子：W

一个节点存两个值，则有3个孩子：MO

一个节点存三个值，则有4个孩子：MO



1、多叉树的查找与插入



 

2、B树及其变种——分裂节点、合并节点

1、B树的定义——m阶B树需要满足的条件

(1)、每个结点至多有m个孩子；
	
(2)、除根结点外，其他结点至少有m/2个孩子；
	
(3)、根结点至少有2个孩子；
	
(4)、所有叶结点在同一层；
	
(5)、有α个孩子的非叶结点有α-1个关键字；结点内部，关键字递增排列。




2、B树的变种



 

3、R树—R树在实践中的应用



 

 

 

树相关算法的代码实现

1、二叉树的遍历——前中后、通过前中求后

(1)、前序遍



(2)、中序遍历



(3)、后序遍历



(4)、T2、通过前序中序求后序



 

2、二叉查找树、BST的插入节点、BST的删除



(2)、二叉查找树插入节点



(3)、二叉查找树BST的删除



 

3、BBT单旋转、双旋转、BBT的插入、BBT的删除

(1)、左左单旋转



(2)、双旋转



(3)、平衡二叉树的插入



(4)、平衡二叉树的删除