精华内容
下载资源
问答
  • 平衡二叉树严格定义这样的:二叉树中任意一个节点的左右子树的高度相差不能大于 1(小于等于1)从这个定义来看,上一节我们讲的完全二叉树、满二叉树其实都平衡二叉树,但是非完全二叉树也有可能平衡二叉树...

    首先,我们要明确我们是在什么知识体系内讨论红黑树的问题:红黑树是一种平衡二叉查找树

    • 什么是平衡二叉查找树呢?

    平衡二叉树的严格定义是这样的:

    二叉树中任意一个节点的左右子树的高度相差不能大于 1(小于等于1)

    从这个定义来看,上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树,但是非完全二叉树也有可能是平衡二叉树

    叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点,这种二叉树就叫作满二叉树

    叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫作完全二叉树

    顾名思义,红黑树中的节点,一类被标记为黑色,一类被标记为红色

    除此之外,一棵红黑树还需要满足这样几个要求:

    1.根节点是黑色的;

    2.每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;

    3.任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;

    4.每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点

    • 为什么红黑树是“近似平衡”的?

    平衡二叉查找树的初衷,是为了解决二叉查找树因为动态更新导致的性能退化问题。

    所以,“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

    红黑树的高度不是很好分析,我带你一步一步来推导

    首先,我们来看,如果我们将红色节点从红黑树中去掉,那单纯包含黑色节点的红黑树的高度是多少呢?

    红色节点删除之后,有些节点就没有父节点了,它们会直接拿这些节点的祖父节点(父节点的父节点)作为父节点。所以,之前的二叉树就变成了四叉树。

    4d6dd66824105a91c51edf12869d201e.png

    前面红黑树的定义里有这么一条:从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点,放到叶节点位置,四叉树就变成了完全二叉树。

    所以,仅包含黑色节点的四叉树的高度,比包含相同节点个数的完全二叉树的高度还要小。上一节我们说,完全二叉树的高度近似 log2n,这里的四叉“黑树”的高度要低于完全二叉树,所以去掉红色节点的“黑树”的高度也不会超过 log2n。

    我们现在知道只包含黑色节点的“黑树”的高度,那我们现在把红色节点加回去,高度会变成多少呢?

    从上面我画的红黑树的例子和定义看,在红黑树中,红色节点不能相邻,也就是说,有一个红色节点就要至少有一个黑色节点,将它跟其他红色节点隔开。

    红黑树中包含最多黑色节点的路径不会超过 log2n,所以加入红色节点之后,最长路径不会超过 2log2n,也就是说,红黑树的高度近似 2log2n。

    所以,红黑树的高度只比高度平衡的 AVL 树的高度(log2n)仅仅大了一倍,在性能上,下降得并不多。这样推导出来的结果不够精确,实际上红黑树的性能更好。

    我们学习数据结构和算法,要学习它的由来、特性、适用的场景以及它能解决的问题。

    红黑树是一种平衡二叉查找树。

    它是为了解决普通二叉查找树在数据更新的过程中,复杂度退化的问题而产生的。

    红黑树的高度近似 log2n,所以它是近似平衡,插入、删除、查找操作的时间复杂度都是 O(logn)。

    因为红黑树是一种性能非常稳定的二叉查找树,所以,在工程中,但凡是用到动态插入、删除、查找数据的场景,都可以用到它。

    不过,它实现起来比较复杂,如果自己写代码实现,难度会有些高,这个时候,我们其实更倾向用跳表来替代它。

    展开全文
  • 二叉树原理及实现

    2020-07-11 10:36:00
    什么是二叉树什么是二叉树什么是完全二叉树二叉树的特点: 二叉树实现方式 二叉树的顺序存储 二叉树的二叉链表存储 二叉树的三叉链表存储 二叉树介绍 为什么会有二叉树? 对于普通树来说,除了...

    目录

    二叉树介绍

    为什么会有二叉树?

    什么是二叉树?

    什么是满二叉树?

     什么是完全二叉树?

    二叉树的特点:

    二叉树实现方式

    二叉树的顺序存储

    二叉树的二叉链表存储

    二叉树的三叉链表存储


    二叉树介绍

    为什么会有二叉树?

    对于普通树来说,除了根节点之外,其余子节点的个数并没有要求,遵循的规律太少,程序控制起来较复杂,因此限制了它在实际应用中的使用。由此,为了在实际应用中更好的使用树结构,便在普通树的基础上增加了一些限制,让每一棵树中的每个节点最多只能包含2个子节点,而且严格区左子节点、右子节点,便生成了二叉树。

    什么是二叉树?

    二叉树指的是每个节点最多只能有两个子树的有序树。通常左边的子树被称为“左子树”,右边的树被称为“右子树”,左右的次序不能颠倒。

    什么是满二叉树?

    一棵深度为k的二叉树,如果它包含了2k-1个节点,就把这棵二叉树称为满二叉树。满二叉树的特点是每一层上的节点数都是最大节点数,即各层节点数分别为1、2、4、8、16……2k-1。

     什么是完全二叉树?

    一棵有n个节点的二叉树,按满二叉树的编号方式对它进行编号,若树中所有节点和满二叉树1~n编号完全一致,则称该树为完全二叉树。也就是说,如果一棵二叉树除最后一层外,就其余层的所有节点都是满的,并且最后一层或者是满的,或者仅在右边缺少若干连续的节点,则此二叉树就是完全二叉树。

    满二叉树是一种特殊的完全二叉树。当完全二叉树最后一层的所有节点都是满的时,这棵完全二叉树就变成了满二叉树。

    二叉树的特点:

    • 二叉树第i层上的节点数目至多为2i-1(i>=1)。
    • 深度为k的二叉树至多有2k-1个节点。满二叉树的每层节点的数量依次为1、2、4、8……因此深度为k满二叉树包含的节点数为公比为2的等比数列的前k项总和,即2k-1。
    • 在任何一棵二叉树中,如果其叶子节点的数量为n0,度为2的子节点数量为n2,则n0=n2+1。
    • 具有n个节点的完全二叉树的深度为log2ⁿ+1。
    • 对一棵有n个节点的完全二叉树的节点按层自左向右编号,则对任一编号为i(n>=i>=1)的节点有下列性质。
      • 当i ==1时,节点i是二叉树的根;若i>1,则节点的父节点是i/2。
      • 若2i<=n,则节点i有左孩子,左孩子的编号是2i,否则,节点无左孩子,并且是叶子节点。
      • 若2i+1<=n,则节点i有右孩子,右孩子的编号是2i+1;否则,节点无右孩子。
    • 对一棵有n个节点的完全二叉树的节点按层自左向右编号,1~n/2范围的节点都是有孩子节点的非叶子节点,其余的节点全部都是叶子节点。编号为n/2的节点可能只有左子节点,也可能既有左子节点,又有右子节点。

    二叉树实现方式

    • 顺序存储:采用数组来记录二叉树的所有节点。
    • 二叉链表存储:每个节点保留一个left、right域,分别指向其左、右子节点。
    • 三叉链表存储:每个节点保留一个left、right、parent域,分别指向其左、右子节点和父节点。

    二叉树的顺序存储

    顺序存储指的是充分利用满二叉树的特性—每层的节点数分别为1、2、4、8……2i-1,一棵深度为i的二叉树最多只能包含2i-1个节点,因此只要定义一个长度为2i-1的数组即可存储这棵二叉树。

    当使用数组来存储二叉树的所有节点时可能会产生一定的空间浪费,如果该二叉树是完全二叉树,就不会有任何空间浪费;但如果该二叉树的所有节点都只有右子节点,那么就会产生相当大的空间浪费了

    public class ArrayBinTree<T> {
        //使用数组来记录该树的所有节点
        private Object[] datas;
        private int DEFAULT_SIZE = 8;
        //保存该树的深度
        private int deep;
        private int arraySize;
        //以默认的深度创建二叉树
        public ArrayBinTree() {
            this.deep = DEFAULT_SIZE;
            this.arraySize = (int) Math.pow(2, deep) - 1;
            datas = new Object[arraySize];
        }
        //以指定深度创建二叉树
        public ArrayBinTree(int deep) {
            this.deep = deep;
            this.arraySize = (int) Math.pow(2, deep) - 1;
            datas = new Object[arraySize];
        }
        //以指定深度、指定根节点创建二叉树
        public ArrayBinTree(int deep, T data) {
            this(deep);
            datas[0] = data;
        }
    
        /**
         * 为指定节点添加子节点
         * @param index 需要添加子节点的父节点的索引
         * @param data 新节点的数据
         * @param left 是否为左节点
         */
        public void add(int index, T data, boolean left) {
            if (datas[index] == null) {
                throw new RuntimeException(index + "处节点为空,无法添加子节点");
            }
            if (2 * index + 1 >= arraySize) {
                throw new RuntimeException("树底层的数据已满,树越界异常");
            }
            if (left) {
                datas[2 * index + 1] = data;
            } else {
                datas[2 * index + 2] = data;
            }
        }
        //判断二叉树是否为空
        public boolean empty() {
            //根据根元素判断二叉树是否为空
            return datas[0] == null;
        }
        //返回根节点
        public T root() {
            return (T) datas[0];
        }
        //返回指定节点的(非根节点)的父节点
        public T parent(int index) {
            return (T) datas[(index - 1) / 2];
        }
        //返回指定节点(非叶子)的左子节点,当左子节点不存在时返回null
        public T left(int index) {
            if (2 * index + 1 > arraySize) {
                throw new RuntimeException();
            }
            return (T) datas[index * 2 + 1];
        }
        //返回指定节点(非叶子)的右子节点,当右子节点不存在时返回null
        public T right(int index) {
            if (2 * index + 1 > arraySize) {
                throw new RuntimeException();
            }
            return (T) datas[index * 2 + 2];
        }
        //返回该二叉树的深度
        public int deep() {
            return deep;
        }
        //返回指定节点的位置
        public int pos(T data) {
            for (int i = 0; i < arraySize; i++) {
                if (datas[i].equals(data)) {
                    return i;
                }
            }
            return -1;
        }
    }

    对于这种顺序存储的二叉树,不管是遍历树中节点,还是查找树中节点,都可以非常高效地完成,唯一的缺点是空间浪费很大。

    二叉树的二叉链表存储

    二叉链表存储的思想是让每个节点都能“记住”它的左、右两个子节点。为每个节点增加left、right两个指针,分别引用该节点的左、右两个子节点,因此二叉链表存储的每个节点有以下的结构。

    public class TwoLinkBinTree<E> {
        public static class TreeNode {
            Object data;
            TreeNode left;
            TreeNode right;
    
            public TreeNode() {
            }
    
            public TreeNode(Object data) {
                this.data = data;
            }
    
            public TreeNode(Object data, TreeNode left, TreeNode right) {
                this.data = data;
                this.left = left;
                this.right = right;
            }
        }
        private TreeNode root;
        public TwoLinkBinTree() {
            this.root = new TreeNode();
        }
        public TwoLinkBinTree(E data) {
            this.root = new TreeNode(data);
        }
    
        /**
         * 为指定节点添加子节点
         * @param parent 需要添加子节点的父节点
         * @param data 新子节点的数据
         * @param isLeft 是否为左节点
         * @return 新增的节点
         */
        public TreeNode addNode(TreeNode parent, E data, boolean isLeft) {
            if (parent == null) {
                throw new RuntimeException(parent + "节点为null,无法添加子节点");
            }
            if (isLeft && parent.left != null) {
                throw new RuntimeException(parent + "节点已有左子节点,无法添加左子节点");
            }
            if (!isLeft && parent.right != null) {
                throw new RuntimeException(parent + "节点已有右子节点,无法添加右子节点");
            }
            TreeNode newNode = new TreeNode(data);
            if (isLeft) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
            return newNode;
        }
        //判断二叉树是否为空
        public boolean empty() {
            return root.data == null;
        }
        //返回根节点
        public TreeNode root() {
            if (empty()){
                throw new RuntimeException("树为空,无法访问根节点");
            }
            return root;
        }
        public E leftChild(TreeNode parent) {
            if (parent == null) {
                throw new RuntimeException("节点为null,无法添加子节点");
            }
            return parent.left == null ? null : (E) parent.left.data;
        }
        public E rightChild(TreeNode parent) {
            if (parent == null) {
                throw new RuntimeException("节点为null,无法添加子节点");
            }
            return parent.right == null ? null : (E) parent.right.data;
        }
        //返回该二叉树的深度
        public int deep() {
            return deep(root);
        }
        //递归遍历该二叉树的深度
        private int deep(TreeNode node) {
            if (node == null) {
                return 0;
            }
            if (node.left == null && node.right == null) {
                return 1;
            } else {
                int leftDeep = deep(node.left);
                int rightDeep = deep(node.right);
                int max = leftDeep > rightDeep ? leftDeep : rightDeep;
                return max + 1;
            }
        }
    }

    对于这种二叉链表的二叉树,因为程序采用链表来记录树中所有节点,所以添加节点没有限制,而且不会像顺序存储那样产生大量的空间浪费。当然,这种二叉链表的存储方式在遍历树节点时效率不高,指定节点访问其父节点时也比较困难,程序必须采用遍历二叉树的方式来搜索其父节点。

    二叉树的三叉链表存储

    三叉链表存储的思想是让每个节点不仅“记住”它的左、右两个子节点,还“记住”它的父节点,因此需要为每个节点增加left、right和parent 3个指针,分别引用该节点的左、右两个子节点和父节点。

    public class ThreeLinkBinTree<E> {
        public static class TreeNode {
            Object data;
            TreeNode parent;
            TreeNode left;
            TreeNode right;
            public TreeNode() {
            }
    
            public TreeNode(Object data) {
                this.data = data;
            }
    
            public TreeNode(Object data, TreeNode parent, TreeNode left, TreeNode right) {
                this.data = data;
                this.parent = parent;
                this.left = left;
                this.right = right;
            }
        }
        private TreeNode root;
        //以默认的构造器创建二叉树
        public ThreeLinkBinTree() {
            this.root = new TreeNode();
        }
        //以指定根元素创建二叉树
        public ThreeLinkBinTree(E data) {
            this.root = new TreeNode(data);
        }
    
        /**
         * 为指定父节点添加子节点
         * @param parent 需要添加子节点的父节点
         * @param data 新子节点的数据
         * @param isLeft 是否为左节点
         * @return 新增的节点
         */
        public TreeNode addNode(TreeNode parent, E data, boolean isLeft) {
            if (parent == null) {
                throw new RuntimeException(parent + "节点为null,无法添加子节点");
            }
            if (isLeft && parent.left != null) {
                throw new RuntimeException(parent + "节点已有左子节点,无法添加左子节点");
            }
            if (!isLeft && parent.right != null) {
                throw new RuntimeException(parent + "节点已有右子节点,无法添加右子节点");
            }
            TreeNode newNode = new TreeNode(data);
            if (isLeft) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
            newNode.parent = parent;
            return newNode;
        }
        //判断二叉树是否为空
        public boolean empty() {
            return root.data == null;
        }
        //返回根节点
        public TreeNode root() {
            if (empty()) {
                throw new RuntimeException("树为空,无法访问根节点");
            }
            return root;
        }
        //返回指定节点(非根节点)的父节点
        public E parent(TreeNode node) {
            if (node == null) {
                throw new RuntimeException(node + "节点为null,无法访问其父节点");
            }
            return (E) node.parent.data;
        }
        //返回指定节点(非叶子)的左子节点,当左子节点不存在时返回null
        public E LeftChild(TreeNode parent) {
            if (parent == null) {
                throw new RuntimeException(parent + "节点为null,无法访问其左子节点");
            }
            return parent.left == null ? null : (E) parent.left.data;
        }
        //返回指定节点(非叶子)的右子节点,当右子节点不存在时返回null
        public E LeftRight(TreeNode parent) {
            if (parent == null) {
                throw new RuntimeException(parent + "节点为null,无法访问其右子节点");
            }
            return parent.right == null ? null : (E) parent.right.data;
        }
        //返回该二叉树的深度
        public int deep() {
            return deep(root);
        }
    
        private int deep(TreeNode root) {
            if (root == null) {
                return 0;
            }
            if (root.left == null && root.right == null) {
                return 1;
            } else {
                int leftDeep = deep(root.left);
                int rightDeep = deep(root.right);
                int max = leftDeep > rightDeep ? leftDeep : rightDeep;
                return max + 1;
            }
        }
    }

     

    展开全文
  • 平衡二叉树严格定义这样的:二叉树中任意一个节点的左右子树的高度相差不能大于 1(小于等于1)从这个定义来看,上一节我们讲的完全二叉树、满二叉树其实都平衡二叉树,但是非完全二叉树也有可能平衡二叉树...

    首先,我们要明确我们是在什么知识体系内讨论红黑树的问题:红黑树是一种平衡二叉查找树

    • 什么是平衡二叉查找树呢?

    平衡二叉树的严格定义是这样的:

    二叉树中任意一个节点的左右子树的高度相差不能大于 1(小于等于1)

    从这个定义来看,上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树,但是非完全二叉树也有可能是平衡二叉树

    叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点,这种二叉树就叫作满二叉树

    叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫作完全二叉树

    顾名思义,红黑树中的节点,一类被标记为黑色,一类被标记为红色

    除此之外,一棵红黑树还需要满足这样几个要求:

    1.根节点是黑色的;

    2.每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;

    3.任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;

    4.每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点

    • 为什么红黑树是“近似平衡”的?

    平衡二叉查找树的初衷,是为了解决二叉查找树因为动态更新导致的性能退化问题。

    所以,“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

    红黑树的高度不是很好分析,我带你一步一步来推导

    首先,我们来看,如果我们将红色节点从红黑树中去掉,那单纯包含黑色节点的红黑树的高度是多少呢?

    红色节点删除之后,有些节点就没有父节点了,它们会直接拿这些节点的祖父节点(父节点的父节点)作为父节点。所以,之前的二叉树就变成了四叉树。

    2d373ab94f1ebe0198779f3e6d682f85.png

    前面红黑树的定义里有这么一条:从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点,放到叶节点位置,四叉树就变成了完全二叉树。

    所以,仅包含黑色节点的四叉树的高度,比包含相同节点个数的完全二叉树的高度还要小。上一节我们说,完全二叉树的高度近似 log2n,这里的四叉“黑树”的高度要低于完全二叉树,所以去掉红色节点的“黑树”的高度也不会超过 log2n。

    我们现在知道只包含黑色节点的“黑树”的高度,那我们现在把红色节点加回去,高度会变成多少呢?

    从上面我画的红黑树的例子和定义看,在红黑树中,红色节点不能相邻,也就是说,有一个红色节点就要至少有一个黑色节点,将它跟其他红色节点隔开。

    红黑树中包含最多黑色节点的路径不会超过 log2n,所以加入红色节点之后,最长路径不会超过 2log2n,也就是说,红黑树的高度近似 2log2n。

    所以,红黑树的高度只比高度平衡的 AVL 树的高度(log2n)仅仅大了一倍,在性能上,下降得并不多。这样推导出来的结果不够精确,实际上红黑树的性能更好。

    我们学习数据结构和算法,要学习它的由来、特性、适用的场景以及它能解决的问题。

    红黑树是一种平衡二叉查找树。

    它是为了解决普通二叉查找树在数据更新的过程中,复杂度退化的问题而产生的。

    红黑树的高度近似 log2n,所以它是近似平衡,插入、删除、查找操作的时间复杂度都是 O(logn)。

    因为红黑树是一种性能非常稳定的二叉查找树,所以,在工程中,但凡是用到动态插入、删除、查找数据的场景,都可以用到它。

    不过,它实现起来比较复杂,如果自己写代码实现,难度会有些高,这个时候,我们其实更倾向用跳表来替代它。

    展开全文
  • 二叉树的子树有左右之分,其次序不能任意颠倒。这什么呢? 要求次序,非要整的特别严格干嘛。。感觉二叉树结点就是以一个个离散的结点组合的,根本看不出来哪个左子树,哪个右子树
  • 红黑树(上):为什么工程中都用红黑树这种二叉树? 为了解决复杂度退化的问题,设计了一种平衡二叉树 平衡二叉查找树 二叉树中任意一个节点的左右子树的高度相差不能大于1,完全二叉树和满二叉树平衡二叉树,...

    红黑树(上):为什么工程中都用红黑树这种二叉树?

    为了解决复杂度退化的问题,设计了一种平衡二叉树

    平衡二叉查找树

    二叉树中任意一个节点的左右子树的高度相差不能大于1,完全二叉树和满二叉树都是平衡二叉树,但是非完全二叉树有可能是平衡二叉树

    很多平衡二叉查找树其实并没有严格符合定义(树中任意一个节点的左右子树的高度相差不能大于1),比如红黑树,它从根节点到各个叶子节点的最长路径,有可能比最短路径大一倍

    发明平衡二叉查找树的初衷是解决普通二叉查找树在频繁的插入、删除等动态更新的情况下,出现时间复杂度退化的问题,所以“平衡”的意思就是让整棵树看起来“对称”,不要出现左子树很高、右子树很矮的情况,高度相应低一些,相应的插入、删除等操作的效率高一些,只要树的高度不比log2n大很多,仍然可以说是一个合格的平衡二叉树

    定义一棵“红黑树” (Red-Black Tree R-B Tree)

    提到平衡二叉树,就是红黑树

    是一种不严格的平衡二叉查找树,其中的节点,一类被标记为红色,另一类被标记为黑色,还得满足几个要求:

    • 根节点是黑色的
    • 每个叶子节点都是黑色的空节点null,也就是说叶子节点不存储数据
    • 任何相邻的节点都不能同时为红色,即红色节点被黑色节点隔开
    • 每个节点,从该节点到达其可达叶子节点的所有路径都包含相同数目的黑色节点

    分析红黑树的性能是否平衡

    只需要分析高度是否稳定趋近log2n即可

    首先,如果我们将红色节点从红黑树中去掉,那单纯包含黑色节点的红色书的高度是多少?红色节点删除之后,有些节点没有父节点,直接拿父节点的父节点作为父节点,有可能直接变成四叉树。前面的定义有:从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点,从四叉树中取出某些节点,放到叶节点位置,四叉树就变成完全二叉树,所以,仅包含黑色节点的四叉树的高度,比包含相同节点个数的完全二叉树的高度要小,所以去掉红色节点的黑树的高度不超过log2n

    现在知道只包含黑色节点的黑树高度,把红节点加回去,高度为?

    有一个红色节点就必须至少有一个黑色节点,所以加入红色节点之后,最长路径不会超过2log2n

    为啥工程中喜欢用红黑树?

    AVL树是最先发现的平衡二叉查找树,是一种高度平衡的二叉树,查找效率非常高,但是每次插入、删除都要调整,所以对于频繁的插入、删除的数据集合,代价比较大

    红黑树的高度近似log2n,所以插入、删除、查找操作的时间复杂度都是O(logn)

    补充:2-3树

    2-3树是二叉查找树的变种,2和3代表的是两种节点

    2-节点即普通节点:包含一个元素,两条子链接

    3-节点包含2个元素和3条子链接,两个元素A,B,左边的链接小于A节点,中间的链接指向介于A,B之间的值,右边的大于B节点

    在插入过程中,从根节点开始比较,小于节点值往左继续与左子节点比,大于的继续与右子节点比,直到某结点左或右子节点为空,把值插入进去,如果将值插入一个2-节点,将2-节点扩充为3-节点,如是3-节点(1)3-节点没有父节点,即整棵树只有一个3-结点,将扩充为一个4-结点,将其分解为一个二叉树,依然平衡 (2)3-节点有一个2-节点的父节点,将3-节点扩充为4-节点,分解4-节点,将分解后的新树的父节点融入到2-节点的父节点中去 (3)3-节点有一个3-节点的父节点,将3节点扩充为4-节点,然后分解这个4-节点,新树父节点向上融合,上面的3-节点继续扩充,融合,分解,新树继续向上融合,直到父节点是2-节点为止,如果向上到根节点都是3-节点,将根节点扩充为4-节点,分解,整个树加一层,仍然平衡

    2-3树用代码实现不方便,红黑树出现了

    红黑树中红色黑色啥意思?

    红黑树中,所有节点都是2-节点,为了体现出3-节点,将3-节点的两个元素用左斜红色的链接连接起来,即连接了两个2-节点来表示一个3-节点,红色节点标记代表指向其的链接是红链接,黑色表示就是普通的节点

    红色节点是可以与其父节点合并为一个3-节点的

    将红色链接放平,所有的叶子节点到根节点的距离都一样,且红链接只能是左链接,且a<b,b在上,为a的父节点

    所以,红黑树满足:

    • 红链接均为左链接
    • 没有任何一个节点同时和两个红链接相连
    • 完美黑色平衡即任意空链接到根节点的路径上黑链接数量相同

    https://www.cnblogs.com/tiancai/p/9072813.html

    展开全文
  • 问题引入 二叉查找树在频繁的动态更新过程中,可能会出现树的高度远大于 ...平衡二叉树严格定义这样的:二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看,上一节我们讲的完全二叉树、满二叉
  • ------ 本文学习算法的笔记,《数据结构与算法之美》,极客时间的课程 ------ 上节讲到二叉查找树在频繁的动态更新的过程中,可能会出现树的高度远大于log2n的情况,从而导致操作的效率...平衡二叉树严格定义...
  • 小Y在学树论时看到了有关二叉树的介绍:在计算机科学中,二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树...
  • 目录 一、什么是“平衡二叉查找树”? 二、如何定义一棵“红黑树”? ...3.AVL 树严格符合平衡二叉查找树的定义,即任何节点的左右子树高度相差不超过 1,一种高度平衡的二叉查找树。 4.红...
  • 源于生活,抽象生活。欠下的债总是要还的,我们讨论堆排序,用到的就是二叉堆,聊起二叉堆,我们又要反过来倒回到之间介绍的二叉树系列。生活中的堆排序一提二叉树,我总是想起来挂在老家的家谱,可惜...那什么...
  • 二叉树--红黑树

    千次阅读 2016-05-27 19:20:06
    红黑树定义红黑树,顾名思义,就是树的节点只有红色和黑色两种状态,通过这两种...因为红黑树不满足严格的平衡二叉树的定义,从严格意义上来讲,红黑树并不是平衡二叉树;但是,红黑树在建立的时候,也有平衡调整的
  • 统计完全二叉树的节点数

    千次阅读 2018-07-23 01:03:11
     统计一个二叉树的节点最简单的方法当然遍历一次,但是这样的时间复杂度是严格的O(n),不满足要求。要更快,自然要在完全二叉树的性质上下功夫。  完全二叉树的最后一层,节点一定从左向右紧密排列的。由此...
  • 二叉树遍历

    千次阅读 2005-08-30 21:27:00
    如何用栈实现递归与非递归的转换 一.为什么要学习递归与非递归的转换的实现方法? 1)并不每一门语言都支持递归的....需要说明的, 这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子
  • 什么是二叉树? 二叉树(Binary Tree)n(n≥0)个节点的有限集合,它或者空集(n=0),或者由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同,二叉树严格区分左...
  • 什么是平衡二叉树?平衡二叉树(AVL, Self-balancing binary search tree)一棵所有节点的左右子树深度差不超过1的二叉搜索树。 这表明AVL首先一个二叉搜索树,在节点的数值上有约束,同时对树形有严格要求,...
  • 其次弄明白什么样的树二叉查找树,以及二叉查找树的性能分析和其不能成为工业级别使用的树的原因。再引出平衡二叉查找树以及构建平衡二叉查找树的初衷,分析AVL树(最先被发明的严格的平衡二叉树)的优越点,...
  • RB-Tree和AVL树作为BBST,其实现的算法时间复杂度相同,AVL作为最先提出的BBST,貌似RB-tree实现的功能都可以用AVL树代替,那么为什么还需要引入RB-Tree呢? 红黑树不追求"完全平衡",即不像AVL那样要求节点的|...
  • 一:背景 平衡二叉树(又称AVL树)是二叉查找树的一个进化体...那么平衡是什么意思?我们要求对于一棵二叉查找树 ,它的每一个节点的左右子树高度之差不超过1。(对于树的高度的约定:空节点高度是0;叶子节点高度是1。
  • 二叉搜索树之所以有不错的搜索效率,因为在往树中插入数值时,始终严格的遵守左子节点值比父节点值小,右子节点值比父节点大的准则。以搜索 12 为例:从根节点开始,12 比 9 大,所以转向右节点;12 比 29 小,...
  • 一、什么是平衡二叉查找树 发明平衡二叉查找树这类数据结构的初衷,解决普通二叉查找树在频繁的插入、删除等动态更新的情况下,出现时间复杂度退化的问题。所以,平衡二叉查找树中“平衡”的意思,其实就是让整棵...
  • 跳表一种可以用来代替平衡树的数据结构,跳表使用概率平衡而不是严格执行的平衡,因此,与等效树的等效算法相比,跳表中插入和删除的算法要简单得多,并且速度要快得多。 为什么需要?性能比...
  • 什么是跳跃表跳表由William Pugh发明。他在论文 《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作。跳表一种可以用来代替平衡树的数据结构,跳表使用...
  • 1、什么是红黑树上一篇文章中我们学习了什么是平衡二叉树以及它的用法,今天我们将来学习红黑树。红黑树一种特殊的平衡二叉树严格来说它不属于平衡二叉树,但是它和平衡二叉树的目的一样的,都为了减少查找...
  • 它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1,但红黑树高度依然平均log(n),且最坏情况高度不会超过2log(n)。红黑树(red-black tree)一棵满足下述性质的二叉查找树:1. 每一个结点要么...
  • 平衡二叉查找树什么是平衡二叉查找树二叉树中任意一个节点的左右子树的高度相差不能大于 1,这一种较为严格的定义,但是实际工程中使用,不会要求这么严格,只要实际的高度不比 log2(n)大很多,能达到平衡的效果,...
  • 它不严格是因为它不是严格控制左、右子树高度或节点数之差小于等于1,但红黑树高度依然平均log(n),且最坏情况高度不会超过2log(n)。红黑树(red-black tree)一棵满足下述性质的二叉查找树:1. 每一个结点要么...
  • MySQL为什么选择B+树作为索引...AVL树是严格的平衡二叉树,所有节点的左右子树高度差不能超过1;AVL树查找、插入和删除在平均和最坏情况下都O(lgn)。 AVL实现平衡的关键在于旋转操作:插入和删除可能破坏二叉树...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 131
精华内容 52
关键字:

严格二叉树是什么