C#实现平衡查找树

目录
  • 1. 2-3查找树
    • 1.查找
    • 2.向 2- 结点中插入新键
    • 3.向一棵只含有一个 3- 结点的树中插入新键
    • 4.向一个父结点为 2- 结点的 3- 结点中插入新键
    • 5.向一个父结点为 3- 结点的 3- 结点插入新键
    • 6.分解根结点
    • 7.局部变换
    • 8.全局性质
  • 2.红黑二叉查找树
    • 1.定义
    • 2.一一对应
    • 3.颜色表示
    • 4.旋转
    • 5.在旋转后重置父结点的链接
    • 6.向单个 2- 结点中插入新键
    • 7.向树底部的 2- 结点插入新键
    • 8.向一棵双键树(即一个 3- 结点)中插入新键
    • 9.颜色变换
    • 10.根结点总是黑色
    • 11.向树底部的 3- 结点插入新键
    • 12.将红链接在树中向上传递
    • 13.实现
  • 3.删除操作
    • 1.自顶向下的 2-3-4 树
    • 2.删除最小键
    • 3.删除操作
  • 红黑树的性质

之前讲的二叉查找树在最坏情况下性能还是很低的。平衡查找树能够保证无论如何构造它,它的运行时间都是对数级别。在一棵含有 N 个结点的树中,我们希望树高为 ~lgN,这样我们就能保证所有查找都能在 ~lgN 次比较内结束,就和二分查找一样。但是,在动态插入中保证树的完美平衡的代价太高。我们稍微降低完美平衡的要求,学习一种能够保证符号表 API 中所有操作均能在对数时间内完成的数据结构。

1. 2-3查找树

为了保证查找树的平衡性,我们需要一些灵活性,因此我们允许树中的一个结点保存多个键。一棵标准的二叉查找树中的结点称为 2- 结点,含有一个键和两条连接;将含有两个键和三条连接的结点称为 3- 结点(左连接指向的 2-3 树中的键都小于该结点,中连接指向的 2-3 树种中的键都位于该结点的两个键之间,右链接指向的 2-3 树中的键都大于该结点)。

一棵完美平衡的 2-3 查找树中的所有空连接到根结点的距离都应该事相同的。简洁起见,这里用 2-3 树指代一棵完美平衡的 2-3 查找树(在其他情况下这个次表示一种更一般的结构)。

1.查找

将二叉查找树的查找算法一般化就能直接得到 2-3 树的查找算法。要判断一个键是否存在树中,先将它和根结点中的键比较。如果它和其中任意一个键相等,查找命中;否则就根据比较的结果找到指向相应区间的链接,并在其指向的子树中递归地继续查找。

2.向 2- 结点中插入新键

要在 2-3 树中插入一个新结点,我们可以和二叉查找树一样先进行一次未命中的查找,然后把新结点挂在树的底部。但这样的话树无法保持完美平衡性。我们使用 2-3 树的主要原因就在于它能够在插入后继续保持平衡。

如果未命中的查找结束于一个 2- 结点,处理就简单:我们只要把这个 2- 结点替换成一个 3- 结点,将要插入的键保存在其中即可。

但是,如果未命中的查找结束于一个 3- 结点,就要麻烦一些。

3.向一棵只含有一个 3- 结点的树中插入新键

在考虑一般情况之前,先假设我们需要向一棵只含有一个 3- 结点的树中插入一个新键。这棵树中有两个键,所以它已经没有可插入新键的空间了。为了将新键插入,我们先临时将新键存入该结点,使之称为一个 4- 结点(三个键和四条链接)。然后把这个 4- 结点转换未一棵由 3个 2- 结点组成的 2-3 树,其中一个结点(根)含有中键,一个结点含有3个键中的最小者(和根结点的左连接相连),一个结点含有3个键中的最大者。

这棵树既是一棵含有3个结点的二叉查找树,同时也是一棵完美平衡的 2-3 树,因为其中所有的空链接到根结点的距离都相等。插入树前高度为 0,插入树后高度为 1。

4.向一个父结点为 2- 结点的 3- 结点中插入新键

在这种情况下我们需要在维持树的完美平衡下为新键腾出空间。先像上面一样构造一个临时的 4- 结点将其分解成3个 2- 结点,但此时我们不会为中键创建一个新结点,而是将其移至原父结点中。

5.向一个父结点为 3- 结点的 3- 结点插入新键

对于这种情况,我们还是构造一个临时 4- 结点并将其分解,然后将它的中键插入它的父结点。但此时父结点也变成一个新的临时 4- 结点,然后继续在这个结点上进行相同的变换,直至遇到一个 2- 结点或到达根结点。

6.分解根结点

如果从插入结点到根结点都是 3- 结点,根结点最终变成一个临时的 4- 结点。此时按照向一棵只有一个 3- 结点的树中插入新键的方法,将临时 4- 结点分解成3个 2- 结点,使得树高加1。

7.局部变换

将一个 4- 结点分解成一棵 2-3 树可能有6种情况:

2-3 树插入算法的根本在于这些变换都是局部的:除了相关结点和链接之外不必修改或者检查树的其他部分。每次变换中,变更的链接树不会超过一个很小的常数。

8.全局性质

这些局部变换不会影响树的全局有序性和平衡性:任意空链接到根结点的路径长度都是相等的。和标准的二叉查找树由上向下生长不同, 2-3 树的生长是由下向上的。

在一棵大小为 N 的 2-3 树中,插入和查找操作访问的结点必然不超过 lgN 个。因此可以确定 2-3 树在最坏的情况下仍有较好的性能,任何查找或者插入的成本都肯定不会超过对数级别。例如,含有 10亿个结点的 2-3 树的高度仅在 19到30之间。

但是,我们只是实现方式的一部分。尽管有可能编写代码来对表示2节点和3节点的不同数据类型执行转换,但是我们已经描述的大多数任务在这种直接表示中都不方便实现。

2.红黑二叉查找树

我们使用红黑二叉查找树的简单数据结构来表达并实现 2-3 树。

1.定义

红黑二叉树背后的基本思想是用标准的二叉查找树(完全由 2- 结点构成)和一些额外的信息(替换 3- 结点)来表示 2-3 树。我们将树中的链接分为两种类型:红链接将两个 2- 结点链接起来构成一个 3- 结点,黑链接则是 2-3 树中的普通链接。我们将 3- 结点表示为一条左斜的红色链接(两个 2- 结点其中之一是另一个的左子结点)相连的两个 2- 结点。这种表示法的一个优点是,无需修改就可以直接使用标准二叉查找树的 Get()方法。

红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树:

  • 1.左链接均为左链接;
  • 2.没有任何一个结点同时和两条红链接相连;
  • 3.该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同。

满足这样定义的红黑树和相应的 2-3 树是一一对应的。

2.一一对应

如果我们将一棵红黑树中的红链接画平,那么所有的空链接到根结点的距离都是相同的。如果将有红链接相连的结点合并,得到的就是一棵 2-3 树。相反,如果将一棵 2-3 树中的 3- 结点画作由红色链接相连的两个 2- 结点,那么不会存在能够和两条红链接相连的结点,且树必然是完美黑色平衡的,因为黑链接即 2-3 树中的普通链接,根据定义这些链接必然是完美平衡的。无论我们用那种方式取定义它们,红黑树都既是二叉查找树,也是 2-3 树。因此如果我们能够在保持一一对应关系的基础上实现 2-3 树的插入算法,那么我们就能将两个算法的优点结合起来:二叉查找树中高效简洁的查找方法和 2-3 树中高效的平衡插入算法。

3.颜色表示

因为每个结点都只会有一条指向自己的链接(从父结点指向它),我们将链接的颜色保存在表示结点的 Node 数据类型的布尔变量中。如果指向它的链接是红色的,那么该变量为 true,黑色则为 false。我们约定空链接为黑色。我们使用 IsRed() 来测试链接的颜色。

    public class RedBlackBST<Key, Value> : BaseSymbolTables<Key, Value>
        where Key : IComparable
    {
        private Node root;
        private  const bool RED = true;
        private const bool BLACK = false;
        private class Node
        {
            public Key key;
            public Value value;
            public Node left, right;
            public int N;
            public bool color;

            Node(Key key,Value value,int N, bool color)
            {
                this.key = key;
                this.value = value;
                this.N = N;
                this.color = color;
            }
        }

        private bool IsRed(Node x)
        {
            if (x == null)
            {
                return false;
            }
            return x.color == RED;
        }

        private int Size(Node x)
        {
            if (x == null)
                return 0;
            else
                return x.N;
        }
    }

4.旋转

在我们实现的某些操作中可能会出现红色右链接或者两条连续的红链接,但在操作完成前这些情况都会被小心地旋转并修复。旋转操作会改变红链接的指向。

一条红色的右链接被转换为左链接,称为左旋转。它对应的方法接受一条指向红黑树中的某个结点的链接作为参数。假设被指向的结点的右链接是红色的,这个方法会对树进行必要的调整并返回一个指向包含同一组键的子树且左链接为红色的根结点的链接。其代码实现,只是将用两个键中较小的作为根结点变成将较大的作为根结点。

        private Node RotateLeft(Node h)
        {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

        private Node RotateRight(Node h)
        {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

5.在旋转后重置父结点的链接

无论是左旋转还是右旋转,旋转操作都会返回一条链接。我们总是会用 RotateLeft 或 RotateRight 的返回值重置父结点或是根结点中相应的链接。返回的链接可能是左链接也可能是右链接,但是总会将它赋予父结点中的链接。这个链接可能是红色也可能是黑色 --RotateLeft 和 RotateRight 都通过将x.color 设为 h.color 保留它原来的颜色。这种简洁的代码是我们使用递归实现二叉查找树的各种方法的原因。

在插入新键时我们可以使用旋转操作保证 2-3 树和红黑树之间的一一对应,因为旋转操作可以保持红黑树的两个重要性质:有序性和完美平衡性。下面来看如何使用旋转操作来保持红黑树的另外两个重要性质:不存在两条连续的红链接和不存在红色的右链接。

6.向单个 2- 结点中插入新键

一棵只含有一个键的红黑树只含有一个 2- 结点。插入另一个键后,需要马上将它们旋转。如果新键小于老键,只需新增一个红色的结点即可。如果新键大于老键,那么新增的红色结点将会产生一条红色的右链接,需要左旋转将其旋转为红色左连接并修改根结点的链接,插入操作才算完成。两种情况的结果均为一棵和单个 3- 结点等价的红黑树,其中含有两个键,一条红链接,树的黑链接高度为 1。

7.向树底部的 2- 结点插入新键

用和二叉查找树相同的方式向一棵红黑树中插入一个新键会在树的底部新增一个结点(为了保证有序性),但总是用红链接将新节点和它的父结点相连。

8.向一棵双键树(即一个 3- 结点)中插入新键

这种情况分为三种情况:新键小于树中的两个键,两者之间,或是大于树中的两个键。每种情况都会产生一个同时连接两条红链接的结点,而我们的目的就是修正这一点:

总的来说,我们通过 0 次,1 次和 2 次旋转以及颜色的变换得到了期望的结果。这些转换是红黑树的动态变化的关键。

9.颜色变换

我们专门用一个方法 FlipColors 方法来转换一个结点的两个红色子结点的颜色。除了将子结点的颜色由红变黑之外,同时还要将父结点的颜色由黑变红。 这项操作最重要的性质在于它和旋转操作一样是局部变换,不会影响整个树的黑色平衡性。

        private void FlipColors(Node h)
        {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }

10.根结点总是黑色

根据前面的情况,颜色转换会使根结点变为红色。这也可能出现在很大的红黑树中。严格地说,红色的根结点说明根结点是一个 3- 结点的一部分,但实际情况并不是。因此我们在每次插入后都会将根结点设置为黑色。当根结点由红变黑时树的高度就会加1。

11.向树底部的 3- 结点插入新键

对于这种情况,前面的三种情况都会出现:可能是 3- 结点的右链接(只需要转换颜色),或是左链接(需要右转然后转换颜色),或是中链接(需要左旋转下层链接然后右旋转上层链接,最后变换颜色)。颜色转换会使中间结点变红。

12.将红链接在树中向上传递

每次必要的旋转之后都会进行颜色转换,这使得中结点变红。在父结点看来,处理这样一个红色的结点的方式和处理一个新插入的红色结点完全相同,即继续把红链接转移到中结点上去。下图总结的三种情况显示了在红黑树中实现 2-3 树的插入算法的关键操作所需的步骤:要在一个 3- 结点下插入新键,先临时创建一个 4- 结点,将其分解并将红链接由中间键传递给它的父结点。重复这个过程,就能将红链接在树中向上传递,直至遇到一个 2- 结点或者根结点。

总之,只要慎重地使用左旋转,右旋转和颜色转换三种操作,就能保证插入操作后红黑树和 2-3 树的一一对应。在沿着插入结点到根结点的路径向上移动时所经过的每个结点中顺序完成以下操作,就能完成插入操作:

  • 1.如果右子结点是红色且左子结点是黑色,进行左旋转;
  • 2.如果左子结点和它的左子结点都是红色,进行右转;
  • 3.如果左右子结点均为红色,进行颜色转换。

13.实现

因为保持树的平衡性所需的操作是由下至上在每个经历的结点中进行,所以实现很简单:只需要在递归调用之后完成上面所说的三种操作,这里通过三个 if 语句完成。

    public class RedBlackBST<Key, Value> : BaseSymbolTables<Key, Value>
        where Key : IComparable
    {
        private Node root;
        private  const bool RED = true;
        private const bool BLACK = false;
        private class Node
        {
            public Key key;
            public Value value;
            public Node left, right;
            public int N;
            public bool color;

            public Node(Key key,Value value,int N, bool color)
            {
                this.key = key;
                this.value = value;
                this.N = N;
                this.color = color;
            }
        }

        private bool IsRed(Node x)
        {
            if (x == null)
            {
                return false;
            }
            return x.color == RED;
        }

        private Node RotateLeft(Node h)
        {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }

        private Node RotateRight(Node h)
        {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + Size(h.left) + Size(h.right);
            return x;
        }
        private int Size(Node x)
        {
            if (x == null)
                return 0;
            else
                return x.N;
        }

        private void FlipColors(Node h)
        {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }

        public override void Put(Key key, Value value)
        {
            root = Put(root,key,value);
        }

        private Node Put(Node h, Key key, Value value)
        {
            if (h == null)
                return new Node(key,value,1,RED);

            int cmp = key.CompareTo(h.key);
            if (cmp < 0)
                h.left = Put(h.left, key, value);
            else if (cmp > 0)
                h.right = Put(h.right, key, value);
            else
                h.value = value;

            if (IsRed(h.right) && !IsRed(h.left))
                h = RotateLeft(h);
            if (IsRed(h.left) && IsRed(h.left.left))
                h = RotateRight(h);
            if (IsRed(h.left) && IsRed(h.right))
                FlipColors(h);

            h.N = Size(h.left) + Size(h.right) + 1;
            return h;
        }
    }

下图时测试用例轨迹:

3.删除操作

和插入操作一样,我们也可以定义一系列局部变换来在删除一个结点的同时保持树的完美平衡性。这个过程比较复杂,因为不仅要在为了删除一个结点而构造临时 4- 结点时沿着查找路径向下进行变换,还要分解遗留的 4- 结点时沿着查找路径向上进行变换。

1.自顶向下的 2-3-4 树

开始之前,先学习一个沿着查找路径既能向上也能向下进行变换的简单算法: 2-3-4 树的插入算法,2-3-4 树=中允许存在 4- 结点。它的插入算法沿查找路径向下变换是为了把凹征当前结点不是 4- 结点(这样树底才有空间插入新的键),沿查找路径向上进行变换是为了将之前创建的 4- 结点配平。向下变换和 2-3 树种分解 4- 结点所进行的变换相同。如果根结点是4-结点,就将它分解成3个 2- 结点,使得树高加一。在向下查找的过程中,如果遇到一个父结点是 2- 结点的 4- 结点,将 4- 结点分解成两个 2- 结点并将中间键传递给父结点,使得父结点变成 3- 结点。如果遇到一个父结点是 3- 结点的 4- 结点,将 4- 结点分解成两个 2- 结点并将中间键传递给父结点,使得父结点变为 4- 结点;不必担心遇到父结点为 4- 结点的 4- 结点,因为插入算法本身就保证了这种情况不会出现。到达树底之后,只会遇到 2- 结点或 3- 结点,所以我们可以插入新的键。

要用红黑树实现这个算法,我们需要:

将 4- 结点 表示由三个 2- 结点组成的一棵平衡的子树,根结点和两个子结点都用红链接相连;
在向下的过程中分解所有 4- 结点并进行颜色转换;
和插入操作一样,在向上的过程用旋转将 4- 结点配平。
只需移动上面算法的 Put 方法中的一行代码就能实现 2-3-4 树中的插入操作:将 ColorFlip 语句及其 if 语句一道递归调用之前(null 测试和比较操作之间)。

2.删除最小键

从树底部的 3- 结点删除键很简单,但从 2- 结点删除一个键会留下一个空链接,这样会破环树的完美平衡性。
为了保证我们不会删除一个 2- 结点,我们沿着左连接向下进行变换,确保当前结点不是 2- 结点(可能是 3- 结点,也可能是临时 4- 结点)。
首先,根结点可能有两种情况。如果根结点是 2- 结点且它的两个子结点都是 2- 结点,我们可以直接将这三个结点变成一个 4- 结点;否则我们需要保证根结点的左子结点不是 2- 结点,如有必要可以从它右侧的兄弟结点“借”一个键来。如图。在沿着左连接向下的过程中,保证一下情况之一成立:
如果当前结点的左子结点不是 2- 结点,完成;
如果当前结点的左子结点是 2- 结点而它的亲兄弟结点不是 2- 结点,将左子结点的兄弟结点中的一个键移动到左子结点中;
如果当前结点的左子结点和它的亲兄弟结点都是 2- 结点,将左子结点,父结点中的最小键和左子节点最近的兄弟结点合并成一个 4- 结点,使父结点由 3- 结点变成 2- 结点或者由 4- 结点变成 3- 结点。
在遍历的过程中执行这个过程,最后能够得到一个含有最小键的 3- 结点或者 4- 结点,然后就可以直接从中将其删除。我们再回头向上分解所有临时的 4- 结点。

3.删除操作

在查找路径上进行和删除最小键相同的变换同样可以保证在查找过程中任意当前结点均不是 2- 结点。如果被查找的键在树的底部,可以直接删除。如果不在,需要将它和它的后继结点交换,和二叉查找树
一样。

红黑树的性质

研究红黑树的性质就是要检查对应的 2-3 树并对相应的 2-3 树进行分析过程。所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别(范围查找除外)。
无论键的插入顺序如何,红黑树都几乎是完美平衡的。一棵大小为 N 的红黑树的高度不会超过 2lgN 。红黑树的最坏情况是它所对应的 2-3 树中构成最左边的路径结点全部都是 3- 结点而其余均是 2- 结点。
最左边的路径长度是只包含 2- 结点的路径长度(~lgN)的两倍。使用随机的键序列,在一棵大小为 N 的红黑树中一次查找所需的比较次数约为(1.00 lgN - 0.5),根结点到任意结点的平均路径长度 ~ 1.00lgN 。
红黑树的 Get 方法不会检查结点的颜色,因此平衡性相关的操作不会产生任何负担;因为树是平衡的,所以查找比二叉查找树更快。每个只会被插入一次,但却可能查找无数次。

到此这篇关于C#实现平衡查找树的文章就介绍到这了。希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C#实现快速排序算法

    快速排序是应用最广泛的排序算法,流行的原因是它实现简单,适用于各种不同情况的输入数据且在一般情况下比其他排序都快得多. 快速排序是原地排序(只需要一个很小的辅助栈),将长度为 N 的数组排序所需的时间和 N lg N 成正比. 1.算法 快速排序也是一种分治的排序算法.它将一个数组分成两个子数组,将两部分独立地排序. 快速排序和归并排序是互补:归并排序是将数组分成两个子数组分别排序,并将有序数组归并,这样数组就是有序的了:而快速排序将数组通过切分变成部分有序数组,然后拆成成两个子数组,当两个子数

  • C#实现二叉查找树

    目录 1.实现API 1.数据结构 2.查找 3.插入 4.分析 有序性相关的方法和删除操作 1.最大键和最小键 2.向上取整和向下取整 3.选择操作 4.排名 5.删除最大键和删除最小键 6.删除操作 7.范围查找 8.性能分析 对于符号表,要支持高效的插入操作,就需要一种链式结构.但单链表无法使用二分查找,因为二分查找的高效来自于能够快速通过索引取得任何子数组的中间元素,链表只能遍历(详细描述).为了将二分查找的效率和链表的灵活性结合,需要更复杂的数据结构:二叉查找树.具体来说,就是使用每个

  • C#算法之散列表

    目录 1.散列函数 正整数 浮点数 字符串 组合键 将 HashCode() 的返回值转化为一个数组索引 自定义的 HashCode 软缓存 2.基于拉链法的散列表 散列表的大小 删除操作 有序性相关的操作 3.基于线性探测法的散列表 删除操作 键簇 线性探测法的性能分析 调整数组大小 拉链法 均摊分析 4.内存的使用 如果所有的键都是小整数,我们可以使用一个数组来实现无序的符号表,将键作为数组的索引而数组中键 i 处存储的就是它对应的值.散列表就是用来处理这种情况,它是简易方法的扩展并能够处理

  • C#实现希尔排序

    对于大规模乱序的数组,插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组地一段移动到另一端.希尔排序改进了插入排序,交换不相邻地元素以对数组地局部进行排序,最终用插入排序将局部有序的数组排序. 希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的.这样的数组成为 h 有序数组.换句话说,一个 h 有序数组就是 h 个相互独立的有序数组组合在一起的一个数组. 在进行排序时,刚开始 h 很大,就能将元素移动到很远的地方,为实现更小的 h 有序创造方便.h 递减到 1 时,相当于

  • C#使用符号表实现查找算法

    高效检索海量信息(经典查找算法)是现代信息世界的基础设施.我们使用符号表描述一张抽象的表格,将信息(值)存储在其中,然后按照指定的键来搜索并获取这些信息.键和值的具体意义取决于不同的应用.符号表中可能会保存很多键和很多信息,因此实现一张高效的符号表是很重要的任务. 符号表有时被称为字典,有时被称为索引. 1.符号表 符号表是一种存储键值对的数据结构,支持两种操作:插入(put),即将一组新的键值对存入表中:查找(get),即根据给定的键得到相应的值.符号表最主要的目的就是将一个健和一个值联系起来

  • C#实现优先队列和堆排序

    目录 优先队列 1.API 2.初级实现 3.堆的定义 二叉堆表示法 4.堆的算法 上浮(由下至上的堆的有序化) 下沉(由上至下的堆的有序化) 改进 堆排序 1.堆的构造 2.下沉排序 先下沉后上浮 优先队列 许多应用程序都需要处理有序的元素,但不一定要求它们全部有序,或是不一定要一次就将它们排序.很多情况下是收集一些元素,处理当前键值最大的元素,然后再收集更多的元素,再处理当前键值最大的元素.这种情况下,需要的数据结构支持两种操作:删除最大的元素和插入元素.这种数据结构类型叫优先队列. 这里,

  • C#实现平衡查找树

    目录 1. 2-3查找树 1.查找 2.向 2- 结点中插入新键 3.向一棵只含有一个 3- 结点的树中插入新键 4.向一个父结点为 2- 结点的 3- 结点中插入新键 5.向一个父结点为 3- 结点的 3- 结点插入新键 6.分解根结点 7.局部变换 8.全局性质 2.红黑二叉查找树 1.定义 2.一一对应 3.颜色表示 4.旋转 5.在旋转后重置父结点的链接 6.向单个 2- 结点中插入新键 7.向树底部的 2- 结点插入新键 8.向一棵双键树(即一个 3- 结点)中插入新键 9.颜色变换

  • LintCode-排序列表转换为二分查找树分析及实例

    给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树 您在真实的面试中是否遇到过这个题? 分析:就是一个简单的递归,只是需要有些链表的操作而已 代码: /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } * Defin

  • C# 递归查找树状目录实现方法

    1.递归查找树状目录 复制代码 代码如下: public partial class Form1 : Form    {        string path = @"F:\学习文件";//递归查找树状目录        public Form1()        {递归查找树状目录            InitializeComponent();        }        private void Form1_Load(object sender, EventArgs e) 

  • 判断整数序列是否为二元查找树的后序遍历结果的解决方法

    题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果.如果是返回true,否则返回false.例如输入5.7.6.9.11.10.8,由于这一整数序列是如下树的后序遍历结果.    8    / \  6   10 / \    / \ 5  7 9 11因此返回true.如果输入7.4.6.5,没有哪棵树的后序遍历的结果是这个序列,因此返回false.本题网上已经有用递归单纯判断的解法. 个人解法: 先得到序列对应的中序序列, 然后看中序序列是否从小到大有序, 得出判断. 相比

  • C语言实现输入一颗二元查找树并将该树转换为它的镜像

    本文实例讲述了C语言实现输入一颗二元查找树并将该树转换为它的镜像的方法,分享给大家供大家参考.具体实现方法如下: 采用递归方法实现代码如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> #include <iterator> #include <algorithm> using namespace std; struct Node { Node(int

  • Java实现二分查找树及其相关操作

    二分查找树(Binary Search Tree)的基本操作有搜索.求最大值.求最小值.求前驱.求后继.插入及删除. 对二分查找树的进行基本操作所花费的时间与树的高度成比例.例如有n个节点的完全二叉树,对它进行的基本操作的时间复杂度为O(logn).然而,如果树是一个有n个节点的线性的链,则在这种情况下的时间复杂度为O(n). 1.什么是二分查找树 二分查找树是一种有组织的二叉树.我们可以通过链接节点表示这样一棵树.每个节点包含键(key),数据(data),左子节点(left),右子节点(ri

  • c语言B树深入理解

    B树是为磁盘或其他直接存储设备设计的一种平衡查找树.如下图所示.每一个结点箭头指向的我们称为入度,指出去的称为出度.树结构的结点入度都是1,不然就变成图了,所以我们一般说树的度就是指树结点的出度,也就是一个结点的子结点个数.有了度的概念我们就简单定义一下B树(假设一棵树的最小度数为M):1.每个结点至少有M-1个关键码,至多有2M-1个关键码:2.除根结点和叶子结点外,每个结点至少有M个子结点,至多有2M个子结点:3.根结点至少有2个子结点,唯一例外是只有根结点的情况,此时没有子结点:4.所有叶

  • MySQL用B+树作为索引结构有什么好处

    前言 在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引).本文将从最普通的二叉查找树开始,逐步说明各种树解决的问题以及面临的新问题,从而说明MySQL为什么选择B+树作为索引结构. 一.二叉查找树(BST):不平衡 二叉查找树(BST,Binary Search Tree),也叫二叉排序树,在二叉树的基础上需要满足:任意节点的左子树上所有节点值不大于根节点的值,任意节点的右子树上所有节点值不小于根节点的值.如下是一颗BST: 当需要快速查

  • Python实现七大查找算法的示例代码

    查找算法 -- 简介 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素.     查找表(Search Table):由同一类型的数据元素构成的集合     关键字(Key):数据元素中某个数据项的值,又称为键值     主键(Primary Key):可唯一的标识某个数据元素或记录的关键字 查找表按照操作方式可分为:         1.静态查找表(Static Search Table):只做查找操作的查找表.它的主要操作是:         ①

  • 教你通过B+Tree平衡多叉树理解InnoDB引擎的聚集和非聚集索引

    目录 InnoDB引擎是通过B+Tree实现索引结构 二叉树(Binary Tree) 平衡二叉树(AVL Tree) 平衡多叉树(B-Tree) B+Tree 聚集和非聚集索引 聚集索引(clustered index) 非聚集索引(secondary index) InnoDB引擎是通过B+Tree实现索引结构 因为B+Tree是从二叉树演化而来,在这之前我们来先了解二叉树.平衡二叉树.平衡多叉树. 二叉树(Binary Tree) 简介:每个节点最多有两个子树的树结构.它有一个特点:左子树

随机推荐