在排序的二叉树中搜索的最有效方法

Question

假设我有一棵二叉树，我给树的头（左值小于右边的值），树里面有ip地址，例如：

       2.1.1.7
      /       \
     /         \
1.1.10.17      3.4.4.5

我需要编写一个函数来搜索这个特定地址。

现在我做的是中序遍历：

private HashSet<string> adr = new HashSet<string>();    
void Inorder(Node root){
  if(root.Left != null)
    Inorder(root.Left);
    adr.Add(root.Data);// <----root.Data it's an ip address (string)
  if(root.Right != null)
    Inorder(root.Right);
 }

施工方：

private Node root;// <--- points to the root of the addresses tree

public MyClass{
  Inorder(root);
}

小说：

bool FindAddress(string address){
 return adr.Contains(address);
}

但是在我的方法中我没有使用树排序的事实，你有更好的性能想法吗？ loop/recursion

Answer 1

您可以如下编写 FindAddress 函数以利用数据已排序的事实：

var node = FindAddress(IPAddress.Parse(searchAddress), assembledTree, new IPAddressCompare());

static Node FindAddress(IPAddress address, Node root, IComparer<IPAddress> addressCompare)
{        
    if (root == null) return null;
    var comp = addressCompare.Compare(IPAddress.Parse(root.Data), address);
    if (comp == 0) return root;
    if (comp < 0) return FindAddress(address, root.Left, addressCompare);
    if (comp > 0) return FindAddress(address, root.Right, addressCompare);
    return null;
}

使用自定义比较器比较两个不同的 IP 地址，方法是将它们的表示更改为 Int32，同时考虑地址开头的字节最重要。

public class IPAddressCompare : IComparer<IPAddress>
{
    public int Compare(IPAddress x, IPAddress y)
    {
        var intA = BitConverter.ToUInt32(x.GetAddressBytes().Reverse().ToArray(), 0);
        var intB = BitConverter.ToUInt32(y.GetAddressBytes().Reverse().ToArray(), 0);
        return intB.CompareTo(intA);
    }
}

完整示例：https://dotnetfiddle.net/viRy5b

Answer 2

我会使用简单的列表，并使用带比较器的二分搜索。避免创建自己的树的麻烦，性能最佳。

using System;
using System.Collections.Generic;
using System.Net;



class app
{    
    static void Main()
    {
        List<IPAddress> sortedIPs = new List<IPAddress>();

        AddToList(sortedIPs, new byte[4] { 6, 10, 54, 100 });
        AddToList(sortedIPs, new byte[4] { 143, 0, 254, 10 });
        AddToList(sortedIPs, new byte[4] { 48, 0, 0, 1 });
        AddToList(sortedIPs, new byte[4] { 0, 0, 82, 19 });
        AddToList(sortedIPs, new byte[4] { 13, 0, 254, 1 });
        AddToList(sortedIPs, new byte[4] { 63, 93, 4, 111 });
        AddToList(sortedIPs, new byte[4] { 98, 3, 74, 1 });
        AddToList(sortedIPs, new byte[4] { 98, 4, 74, 1 });
        AddToList(sortedIPs, new byte[4] { 98, 3, 14, 1 });
        AddToList(sortedIPs, new byte[4] { 98, 3, 14, 2 });
        AddToList(sortedIPs, new byte[4] { 7, 175, 25, 65 });
        AddToList(sortedIPs, new byte[4] { 46, 86, 21, 91 });

        IPAddress findAddress = new IPAddress(new byte[4] { 48, 0, 0, 1 });

        int index = sortedIPs.BinarySearch(findAddress, new IPAddressComparer());

    }

    private static void AddToList(List<IPAddress> list, byte[] address)
    {
        IPAddress a1 = new IPAddress(address);
        IPAddressComparer ipc = new IPAddressComparer();
        int index = list.BinarySearch(a1, ipc);
        if (index >= 0) throw new Exception("IP address already exists in list");
        list.Insert(~index, a1);
    }

    public class IPAddressComparer : IComparer<IPAddress>
    {
        public int Compare(IPAddress x, IPAddress y)
        {
            byte[] xb = x.GetAddressBytes();
            byte[] yb = y.GetAddressBytes();
            for (int i = 0; i < 4; i++)
            {
                int result = xb[i].CompareTo(yb[i]);
                if (result != 0) return result; 
            }
            return 0;
        }
    }

}

在排序的二叉树中搜索的最有效方法

most efficient way to search in sorted binary tree

c#

search

binary-tree