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

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

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

一、概述

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

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 条评论
登录 后参与评论

相关文章

来自专栏数据和云

走在专家的路上,每天一条SQL优化(2)

? 每天坚持进步一点点,让优秀成为一种习惯。 SQL文本如下: INSERT INTO BPZONE.EI_ADDITION (EID,ROOTPIID...

2579
来自专栏BestSDK

封装、私有,一文掌握Python关键代码

首先,什么是 Python?根据 Python 创建者 Guido van Rossum 所言,Python 是一种高级编程语言,其设计的核心理念是代码的易读性...

2963
来自专栏PPV课数据科学社区

【工具】SAS数据整理的16个技巧

1、修改属性   attrib 2、根据条件删除记录   if条件 then delete; 3、分拆数据集 data mastermissing; me...

2875
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之写链表代码的正确姿势(下)

将某个变量(对象)赋值给指针(引用),实际上就是就是将这个变量(对象)的地址赋值给指针(引用)。

652
来自专栏mwangblog

背包、栈和队列

背包是一种不支持从中删除元素的集合类型,它的目的是帮助用例收集元素并迭代遍历所有收集到的元素,迭代的顺序不确定且与用例无关。

581
来自专栏desperate633

一篇文章搞懂红黑树的原理及实现2-3-4 Tree(2-3-4树)红黑树左倾红黑树的删除操作删除红黑树最小节点删除任意节点总结

二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找...

1262
来自专栏张俊红

数据结构—树与二叉树

之前谈到的线性表、栈和队列都是一对一的数据结构,但是现实中也存在很多一对多的数据结构,这篇要写的就是一种一对多的数据结构———树。全文分为如下几部分:

723
来自专栏Fundebug

如何实现JavaScript的Map和Filter函数?

1115
来自专栏技术栈大杂烩

Python源码理解: '+=' 和 'xx = xx + xx'的区别

为什么上面不同的对象执行同一个+会有不同的效果呢? 这就涉及到+的重载, 然而这不是本文要讨论的重点, 上面的只是前菜而已~~~

391
来自专栏我的技术专栏

数据结构图文解析之:AVL树详解及C++模板实现

1014

扫码关注云+社区