有趣的算法(八) ——红黑树插入算法

有趣的算法(八)——红黑树插入算法

(原创内容,转载请注明来源,谢谢)

一、概述

红黑树是一种二叉平衡查找树。二叉查找树是二叉树,且树的根节点会比左节点大、比右节点小。

1)二叉查找树

二叉查找树对于数字比较大小,具有重要意义。由于其左子节点都比根节点小,右子节点都比根节点大,要查找一个数是否在其中,或者在某个位置,会变得很容易。

从根节点出发,如果待查数据比根节点小,则往根节点的左子树去查找;反之从右子树查找;如果值和某个节点一样,表示找到;如果到某个节点,其没有子节点,而还没有匹配,则表示数据不存在。

二叉查找树相当于将一组数据排好序,并且实现二分查找的方式,因此速度非常快。二叉查找树详细信息不具体描述,可以上网查看。

2)红黑树

二叉查找树有个固有问题,是其有可能出现树的高度太高,则树不平衡。可能出现某些值存在于树的非常低层次的节点,导致最终效率很低。

红黑树与其不同的地方在于,其是平衡的,通过颜色来进行平衡。

现有以下规定:

1)只有左节点可以是红色。

2)如果左节点是红色,则左节点的子节点不能是红色。

3)如果左右节点都出现红色,则会都变成黑色。

当发生不平衡,红黑树就通过规定的机制左旋、右旋或改变颜色,以达到平衡,使得树的层级尽量低。

情况如下图所示:

二、红黑树详解

在红黑树中插入节点,也是通过查找的方式,在找不到节点的地方,进行插入数据。如果找到某个节点,则修改节点的值。

新插入的节点,一开始默认都是红色。为了便于清晰概念,现规定,节点颜色是红色,指的是节点与其父节点的连接是红色的。

当插入数据后,会发生几种情况 :

1)插入节点后,红黑树按照规定正常排布。

2)插入节点后,不正常排布,出现不符合红黑树的情况。

异常情况处理如下。

1、左旋

当从右侧插入节点后,节点是红色的,则需要左旋。左旋的核心在于节点互换和颜色转换,核心代码如下:

         //节点互换
    NodeleftNode = headNode.right;
    headNode.right= leftNode.left;
    leftNode.left= headNode;
    //颜色转换
    leftNode.color= headNode.color;
    headNode.color= RED;

步骤为:

1)将父节点(假设为r)的右节点(即刚插入的节点,加上为a)指向a的左节点。

2)将a的左节点指向r。

3)给a赋予r的颜色,给r赋予红色(相当于新插入节点)。

2、右旋

右旋是当节点的左子节点是红色,且左子节点的左子节点还是红色时,需要调整的情况。其核心即将左子节点调整到中心,而将中心节点变为左子节点的右子节点。

核心代码如下:

    NoderightNode = headNode.left;
    headNode.left= rightNode.right;
    rightNode.right= headNode;
    rightNode.color = headNode.color;
    headNode.color= RED;
    rightNode.N= headNode.N;

左旋和右旋如下图所示:

3、颜色调整

当出现左右节点都是红色时,则将左右节点都置为黑色。且将父节点置为红色。核心代码如下:

    headNode.color= RED;
    headNode.left.color= BLACK;
    headNode.right.color= BLACK;

4、调整顺序

插入节点后,是按照上述顺序逐步调整的。

1)当插入节点后,如果节点位于右边,则可能需要左旋;如果位于节点左边,则可能需要右旋。

2)左旋或右旋后,有可能两个节点都是红色,则还需要颜色调整。

5、获取结果

节点排好序后,通过中序遍历的方式获取结果。关于中序遍历,以前的文章中已经讲过。中序遍历的核心,在于先遍历左节点、再遍历中间节点、最后遍历右节点,则可以实现将结果从小到大进行排列。

6、插入节点详解

1)如果根节点是空,则创建根节点。

if(null ==headNode) return  new Node(key, value, 1,RED);

2)比较要插入的节点和当前节点,如果小则比较右节点,如果大则比较左节点,这是通过递归的方式进行比较。如果一致则直接更新节点。

         intcmp = key.compareTo(headNode.key);
         if(0> cmp) headNode.left = addNode(headNode.left, key, value);
   else if(0 < cmp) headNode.right = addNode(headNode.right, key,value);
elseheadNode.value = value;

3)插入节点后,根据实际情况,判断是否需要旋转或者颜色调整。

if(isRed(headNode.right)&& !isRed(headNode.left)) headNode = rotateLeft(headNode);
if(isRed(headNode.left)&& isRed(headNode.left.left)) headNode = rotateRight(headNode);
if(isRed(headNode.right)&& isRed(headNode.left)) flipColor(headNode);

调整概括如下:

7、其他功能

1)查找最小节点

递归遍历,取到最左边的节点即可。同理,最大节点即最右边节点。

2)节点子节点的数量

每次旋转、插入都会进行调整,以更新子节点数量。

三、编程实现(java)

public class RedBlackBSTService<Keyextends Comparable<Key>, Value> {
   private static final boolean RED = true;
   private static final boolean BLACK = false;
   private class Node{
       Key key;//节点键
       Value value;//节点值
       Node left, right;//节点左右节点
       int N;//节点子节点数量
       boolean color;//节点与其父节点连接的颜色
       Node(Key key, Value value, int N, boolean color){
           this.key = key;
           this.value = value;
           this.N = N;
           this.color = color;
       }
    }
   private Node root;
   //查看节点是否是红色(空节点默认是黑色)
    privateboolean isRed(Node x) {
       return null != x && x.color == RED;
    }
   //查看节点子节点数目
   private int size() {
       return size(root);
    }
   private int size(Node h) {
       if (h == null) return 0;
       return h.N;
    }
   private int getTotalSize(Node headNode){
       return 1 + size(headNode.left) + size(headNode.right);
    }
   //获取树的最小、最大节点
   public Key getMinKey(){
       return minKey(root).key;
    }
   public Key getMaxKey(){
       return maxKey(root).key;
    }
   private Node minKey(Node node){
       if(null == node.left) return node;
       return minKey(node.left);
    }
   private Node maxKey(Node node){
       if(null == node.right) return node;
       return maxKey(node.right);
    }
   //左旋(当节点与其右子节点连接是红色时)
   private Node rotateLeft(Node headNode){
       //节点互换
       Node leftNode = headNode.right;
       headNode.right = leftNode.left;
       leftNode.left = headNode;
       //颜色转换
       leftNode.color = headNode.color;
       headNode.color = RED;
       //节点数量重新获取
       leftNode.N = headNode.N;
       headNode.N = getTotalSize(headNode);
       return leftNode;
    }
   //右旋(当节点与父节点连线是红色,且与其左子节点连线也是红色时)
   private Node rotateRight(Node headNode){
       Node rightNode = headNode.left;
       headNode.left = rightNode.right;
       rightNode.right = headNode;
       rightNode.color = headNode.color;
       headNode.color = RED;
       rightNode.N = headNode.N;
       headNode.N = getTotalSize(headNode);
        return rightNode;
    }
   //颜色调整(当节点与其左右子节点连线都是红色时)
   private void flipColor(Node headNode){
       headNode.color = RED;
       headNode.left.color = BLACK;
       headNode.right.color = BLACK;
    }
   //插入节点
   private Node addNode(Node headNode, Key key, Value value){
       //空时新建根节点
       if(null == headNode) return  newNode(key, value, 1, RED);
       //比较待插入节点和当前节点的key
       int cmp = key.compareTo(headNode.key);
       if(0 > cmp) headNode.left = addNode(headNode.left, key, value);
       else if(0 < cmp) headNode.right = addNode(headNode.right, key,value);
       else headNode.value = value;
       //根据插入后的情况判断是否需要旋转或颜色调整
       if(isRed(headNode.right) && !isRed(headNode.left)) headNode =rotateLeft(headNode);
       if(isRed(headNode.left) && isRed(headNode.left.left)) headNode =rotateRight(headNode);
       if(isRed(headNode.right) && isRed(headNode.left))flipColor(headNode);
       //节点大小重新获取
       headNode.N = getTotalSize(headNode);
       return headNode;
    }
   public void addNode(Key key, Value value){
       root = addNode(root, key, value);
       root.color = BLACK;
    }
   public Stack<Value> getSortedNodes(){
       if(null == root) return null;
       Stack<Node> nodeList = new Stack<>();
       Stack<Value> res = new Stack<>();
       Node centerNode = root;
       while(!nodeList.empty() || null != centerNode){
           while (null != centerNode){
                nodeList.push(centerNode);
                centerNode = centerNode.left;
           }
           centerNode = nodeList.pop();
           res.push(centerNode.value);
           centerNode = centerNode.right;
       }
       return res;
    }
}

四、结语

本文只实现了红黑树的查找和插入,没有实现红黑树的删除,删除功能更加复杂,后续我会继续学习并实现。

完整代码见我的github项目,路径:

https://github.com/linhxx/taskmanagement.git

另外,近期laravel环境我已经搭建好,计划这个月实现laravel+vue的小项目,届时也将发到github。

——written by linhxx 2017.10.14

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-10-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

二叉树非递归版的中序遍历算法

本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

2965
来自专栏腾讯数据库技术

如何利用红黑树实现排名?

1383
来自专栏大数据学习笔记

面试算法题

题目来源于牛客网:https://www.nowcoder.com/ta/coding-interviews 1、二维数组中的查找 在一个二维数组中,每一行都按...

7106
来自专栏青蛙要fly的专栏

Android技能树 — 树基础知识小结(一)

现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识...

653
来自专栏Vamei实验室

纸上谈兵: 左倾堆 (leftist heap)

我们之前讲解了堆(heap)的概念。堆是一个优先队列。每次从堆中取出的元素都是堆中优先级最高的元素。 在之前的文章中,我们基于完全二叉树(complete bi...

2829
来自专栏python学习路

数据结构与算法(二)

排序与搜索 排序算法(英语:Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。 排序算法的稳定性 稳定性:稳定排序算法会让原...

3068
来自专栏腾讯云数据库(TencentDB)

【腾讯云CKV缓存】cloud key value·红黑树排名实现过程解析

红黑树是一种自平衡的二叉查找树,它可以在O(logn)时间内执行查找、插入和删除。在c++ STL,linux内核中都有使用。

1811
来自专栏移动端开发

用OC和Swift一起说说二叉树

   一:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)...

845
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(四)No.52

这是本坑的第四篇,之前已经说了关于 HashSet 、BitMap 、Bloom Filter 布隆过滤器了,本篇主要讲B-树。要是还不知道前面讲了啥的,可以点...

1757
来自专栏Golang语言社区

完全二叉树判断,简单而复杂

今天有个人问我如何判断一棵树是完全二叉树。我一下子想不出怎么解决这个问题,按照定义, 严蔚敏那本教材上的说法:一个深度为k,节点个数为 2^k - 1 的二叉树...

2773

扫描关注云+社区